查找排序部分习题 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
1
2
3
4
5
6
7
8
9
10
11
12

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()函数则不会。
1
2
3
4
5
6
7
8
9

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) + 1
        for ch in t:
            dict2[ch] = dict2.get(ch, 0) + 1
        return dict1 == dict2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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 True
        return False
1
2
3
4
5
6
7
8
9
10
11

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 = 0
        right = w * h - 1
        """
        0 1  2 3
        4 5  6 7
        8 9 10 11
        第9个位置，num//4行，num%4列
        i = num // 4
        j = num % 4
        """
        while left <= right:  #  二分查找代码  候选区有值
            mid = (left + right) // 2
            i = mid // w
            j = mid % w
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:  # 待查找的值在mid左侧
                right = mid - 1
            else:  # matrix[mid] < target  待查找的值在mid右侧
                left = mid + 1
        else:
            return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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])
1
2
3
4
5
6
7
8
9
10
11
12

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

class Solution(object):
    def binary_search(self, li, left, right, val):  # 二份查找函数
        # left = 0
        # right = len(li) - 1
        while left <= right:  # 候选区有值
            mid = (left + right) // 2
            if li[mid] == val:
                return mid
            elif li[mid] > val:  # 待查找的值在mid左侧
                right = mid - 1
            else:  # li[mid] < val  待查找的值在mid右侧
                left = mid + 1
        else:
            return None
    def 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 - a
            if 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:
                break
        return sorted([i+1, j+1])  # 题目需要输出index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

无序列表的二分查找

class Solution(object):
    def binary_search(self, li, left, right, val):  # 二份查找函数
        # left = 0
        # right = len(li) - 1
        while left <= right:  # 候选区有值
            mid = (left + right) // 2
            if li[mid][0] == val:
                return mid
            elif li[mid][0] > val:  # 待查找的值在mid左侧
                right = mid - 1
            else:  # li[mid] < val  待查找的值在mid右侧
                left = mid + 1
        else:
            return None
    def 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 下标i
        new_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 - a
            if 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:
                break
        return sorted([new_nums[i][1], new_nums[j][1]])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34