LeetCode 剑指Offer

剑指 Offer 04. 二维数组中的查找

题目描述

​ 在一个n * m的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

  • 实例：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    现有矩阵 matrix 如下：
    [
      [1,   4,  7, 11, 15],
      [2,   5,  8, 12, 19],
      [3,   6,  9, 16, 22],
      [10, 13, 14, 17, 24],
      [18, 21, 23, 26, 30]
    ]

    给定 target = 5，返回 true。
    给定 target = 20，返回 false。

  • 提示

    • 0 <= n <= 1000
    • 0 <= m <= 1000

解题思路

  • 解题思路:

    1. 直接遍历 —— 时间复杂度O(nm)， 空间复杂度O(1)；

    2. 每行二分查找 —— 时间复杂度O(nlogm)， 空间复杂度O(1)；

    3. Z字查找/二叉排序树 —— 时间复杂度O(n+m)， 空间复杂度O(1)。

      二叉排序树构建过程，将第一行的最后一列作为二叉树的根节点。

      Picture1.png

      ​ 此时，树的左孩子永远比父节点小，右孩子会比父节点大。

      ​ 遍历过程中，若当前节点的值小于目标值target，则遍历该节点的右孩子；当大于target则遍历左孩子，若相等则返回True。当i<0或j>=len(matrix)时仍未找到，说明不存在target，返回False。

      ​ 由于是将数组视为二叉树，所以当i--的时候，相当于遍历左子树，当j++时遍历右子树。

实现代码

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
class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        # 直接遍历 O(nm) O(1)
        # for row in matrix:
        #     for item in row:
        #         if item == target:
        #             return True
        # return False

        # 二分查找 O(nlogm) O(1)
        # for row in matrix:
        #     left, right = 0, len(row) - 1
        #     while left <= right:
        #         mid = (left + right) // 2
        #         if row[mid] == target:
        #             return True
        #         elif row[mid] < target:
        #             left = mid + 1
        #         else:
        #             right = mid - 1
        # return False

        # 搜索二叉树/Z字查找 O(m+n) O(1)
        if len(matrix) == 0:
            return False
        root_i, root_j =  len(matrix[0])-1,0
        while root_i>=0 and root_j<= len(matrix)-1:
            if matrix[root_j][root_i] == target:
                return True
            elif matrix[root_j][root_i] < target:
                root_j += 1
            else:
                root_i -= 1
        return False

剑指 Offer 11. 旋转数组的最小数字（简单)

154. 寻找旋转排序数组中的最小值 II(困难)

题目描述

​ 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

​ 给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

​ 注意，数组[a[0], a[1], a[2], ..., a[n-1]]旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。

  • 示例

    1
    2
    3
    4
    5
    输入：numbers = [3,4,5,1,2]
    输出：1

    输入：numbers = [2,2,2,0,1]
    输出：0

  • 提示

    • n == numbers.length
    • 1 <= n <= 5000
    • -5000 <= numbers[i] <= 5000
    • numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

解题思路

  1. 调用API….. min,sorted…[当然不给用] 时间复杂度O(n)

  2. 二分查找 时间复杂度O(logn)

    使用左右指针l,r记录首位位置，m为中间位置。

    最小值一定在右排序数组中。

    • 当nums[m]<nums[r]，说明此时m一定是在右排序数组中，因此l = m + 1，在m的右边继续搜索；

    • 当nums[m]>nums[r]，说明此时m一定在左排序数组中，因此r = m, 在m的左边搜索；

    • 当nums[m]==nums[r]，无法判断m在哪一边，但是此时可以缩小数组的范围，令r = r - 1，此操作可能导致旋转点被去除，但是去除旋转点同时可以理解为在一个没有进行旋转的数组进行搜索，所以r=r-1操作可行。

==为什么不能与左侧端点l进行比较呢？==

​ 原因在于： r的初始位置一定是在右排序数组中，而l的初始位置无法确定在哪个排序数组中

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def minArray(self, numbers: List[int]) -> int:
        # 排序返回第一个
        # numbers = sorted(numbers)
        # return numbers[0]

        # ...min
        # return min(numbers)

        # 二分
        l,r = 0, len(numbers)-1
        while l<r:
            m = (l + r) // 2
            if numbers[m] > numbers[r]:
                l = m + 1
            elif numbers[m] == numbers[r]:
                r = r - 1
            else: # 小于
                r = m
        return numbers[l]

剑指 Offer 50. 第一个只出现一次的字符

题目描述

​ 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

  • 示例

    1
    2
    3
    4
    5
    输入：s = "abaccdeff"
    输出：'b'

    输入：s = "" 
    输出：' '

  • 提示

    • 0 <= s 的长度 <= 50000

解题思路

  1. hash map

代码实现

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
class Solution:
    def firstUniqChar(self, s: str) -> str:
        # if not len(s):
        #     return " "
        # hashmap = {}
        # for c in s:
        #     if c not in hashmap:
        #         hashmap[c] = 1
        #     else:
        #         hashmap[c] = -1
        # for key, val in hashmap.items():
        #     if val == 1:
        #         return key
        # return " "

        # 优化
        # 不存出现的频次而是存True or False
        if not len(s):
            return " "
        hashmap = {}
        for c in s:
            if c not in hashmap:
                hashmap[c] = True
            else:
                hashmap[c] = False
        for key, val in hashmap.items():
            if val:
                return key
        return " "