查找排序部分习题 242. 有效的字母异位词 74. 搜索二维矩阵 1. 两数之和 167.两数之和 II

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

class Solution(object):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

class Solution(object):def isAnagram(self, s, t):""":type s: str:type t: str:rtype: bool"""return sorted(list(s)) == sorted(list(t))# sorted()函数返回重新排序的列表，与sort()函数的区别在于sort()函数是list列表中的函数，而sorted()函数可以对所有可迭代对象进行排序操作。并且用sort()函数对列表排序时会影响列表本身，而sorted()函数则不会。

class Solution(object):def isAnagram(self, s, t):""":type s: str:type t: str:rtype: bool"""# 两个字典dict1 = {}  # {'a':1 'b':2}dict2 = {}for ch in s:dict1[ch] = dict1.get(ch, 0) + 1for ch in t:dict2[ch] = dict2.get(ch, 0) + 1return dict1 == dict2

74. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
线性查找 or 二分查找

class Solution(object):def searchMatrix(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""for line in matrix:if target in line:return Truereturn False

class Solution(object):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 = 0right = w * h - 1"""0 1  2 34 5  6 78 9 10 11第9个位置，num//4行，num%4列i = num // 4j = num % 4"""while left <= right:  #  二分查找代码  候选区有值mid = (left + right) // 2i = mid // wj = mid % wif matrix[i][j] == target:return Trueelif matrix[i][j] > target:  # 待查找的值在mid左侧right = mid - 1else:  # matrix[mid] < target  待查找的值在mid右侧left = mid + 1else:return False

1. 两数之和 167.两数之和 II → 输入无序/有序数组

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

class Solution(object):def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""n = len(nums)for i in range(n):for j in range(i):if nums[i] + nums[j] == target:return sorted([i,j])

若为有序数组，可二分查找

class Solution(object):def binary_search(self, li, left, right, val):  # 二份查找函数# left = 0# right = len(li) - 1while left <= right:  # 候选区有值mid = (left + right) // 2if li[mid] == val:return midelif li[mid] > val:  # 待查找的值在mid左侧right = mid - 1else:  # li[mid] < val  待查找的值在mid右侧left = mid + 1else:return Nonedef twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""for i in range(len(nums)):a = nums[i]b = target - aif b >= a:j = self.binary_search(nums, i + 1, len(nums) - 1, b)else:j = self.binary_search(nums, 0, i - 1, b)if j:breakreturn sorted([i+1, j+1])  # 题目需要输出index

无序列表的二分查找

class Solution(object):def binary_search(self, li, left, right, val):  # 二份查找函数# left = 0# right = len(li) - 1while left <= right:  # 候选区有值mid = (left + right) // 2if li[mid][0] == val:return midelif li[mid][0] > val:  # 待查找的值在mid左侧right = mid - 1else:  # li[mid] < val  待查找的值在mid右侧left = mid + 1else:return Nonedef twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""new_nums = [[num, i] for i, num in enumerate(nums)]  # 二维列表 每一行有 数字num 下标inew_nums.sort(key = lambda x:x[0]) # 按照数num排序  new_nums[i][0]是数，new_nums[i][1]是原来的下标for i in range(len(new_nums)):a = new_nums[i][0]b = target - aif b >= 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:breakreturn sorted([new_nums[i][1], new_nums[j][1]])