算法——查找排序相关面试题和leetcode使用
2021-05-18 00:29
标签：leetcode ret script turn solution none ble arch problem 排序方法简写如下： 列表有下列特性： （1）解法一：线性查找查找，O(mn) （2）解法二：二分查找O(logn) 保证肯定仅有一个结果。 leetcode地址：https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/ 例如，列表[1,2,5,4]与目标整数3，1+2=3，结果为(0,1). （1）方法一：通过二分查找，找到需要的数字。时间复杂度：O(nlogn) 首先确定第一个数，再通过给定整数确定要查找的数，通过二分查找到需要的数。 （2）方法二：针对已经排好序的列表 leetcode地址：https://leetcode.com/problems/two-sum/description/ 算法——查找排序相关面试题和leetcode使用 标签：leetcode ret script turn solution none ble arch problem 原文地址：https://www.cnblogs.com/xiugeng/p/9745743.html1、给两个字符串s和t，判断t是否为s的重新排列后组成的单词。
（1）解法一：排序，O(n*logn)
class Solution:
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
ss = list(s)
tt = list(t)
ss.sort()
tt.sort()
return ss == tt
"""
输入："anagram"、"nagaram"
输出：true
Runtime: 32 ms
"""
class Solution:
def isAnagram(self, s, t):
return sorted(list(s)) == sorted(list(t))
（2）解法二：判断字母数量一致，时间复杂度O(n)
class Solution:
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
dict1 = {} # 用字典来维护字符的数量
dict2 = {}
for ch in s:
dict1[ch] = dict1.get(ch, 0) + 1 # 没有就新建，有就加1
for ch in t:
dict2[ch] = dict2.get(ch, 0) + 1
return dict1 == dict2
"""
输入："anagram"，"nagaram"
输出：true
Runtime: 32 ms
"""
2、给定一个m*n的二维列表，查找一个数是否存在。
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
for line in matrix:
if target in line:
return True
return False
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
h = len(matrix) # 高
if h == 0:
return False
w = len(matrix[0]) # 列
if w == 0:
return False
left = 0
right = w * h - 1
while left target:
right = mid - 1
else:
left = mid + 1
else:
return False
3、给定一个列表和一个整数，设计算法找到两个数的下标，使得两个数之和为给定的整数。
class Solution:
def binary_search(self, li, left, right,val):
"""
二分查找
:param li: 输入的列表
:param val: 输入的待查找的值
:return:
"""
while left val:
# 待查找的值在mid左侧
right = mid - 1 # 更新候选区
else: # li[mid] = a:
j = self.binary_search(nums, i+1, len(nums)-1, b)
else:
j = self.binary_search(nums, 0, i-1, b)
if j:
break
return sorted([i+1,j+1])
class Solution:
def binary_search(self, li, left, right,val):
"""
二分查找
:param li: 输入的列表
:param val: 输入的待查找的值
:return:
"""
while left val:
# 待查找的值在mid左侧
right = mid - 1 # 更新候选区
else: # li[mid] = a:
j = self.binary_search(new_nums, i+1, len(new_nums)-1, b)
else:
j = self.binary_search(new_nums, 0, i-1, b)
if j:
break
return sorted([new_nums[i][1], new_nums[j][1]])