剑指Offer（第二版）算法笔记

发布于 2022-07-11  36 次阅读

数组中重复的数字

Difficulty: Easy
Link: https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
Tag: Array, Classic

Hash

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        s = set()
        for i in nums:
            if i in s:
                return i
            s.add(i)

能用Set/Map的时候避免Dict/HashMap

Time Complexity: O(N)

Space Complexity: O(N)

In-Place Sorting

暴力法对题目的信息利用不完全，题目给出了长度为n的数组内的所有数字都在0 ~ n-1的范围内。因此如果没有重复元素，数组下标和对应值必然是一一对应的。否则在排序过程中一定能找到重复值。

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        i = 0
        while i < len(nums):
            if nums[i] == i:
                i += 1
                continue
            if nums[i] == nums[nums[i]]:
                return nums[i]
            nums[nums[i]], nums[i] = nums[i], nums[nums[i]]

Time Complexity: O(N) 每一次swap一定会将一个数字放到其对应的下标位置，不涉及反复比较过程

Space Complexity: O(1): In-Place

特别注意一下最后一行的同时赋值：

nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
# instead of
# nums[i], nums[nums[i] = nums[nums[i]], nums[i]

Python的同时赋值实际上是把等号右边的值同时存储在一个tuple里，但在左边赋值的时候是按照从左到右的顺序赋值的，因此下面的赋值语句先改动了nums[i]，会导致对nums[num[i]]的引用发生变化，造成赋值错误。

二维数组的查找

Difficulty: Medium
Link: https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
No: 240
Tag: Queue, Search

Brute Force

遍历二维数组搜索

Time Complexity: O(NM)

Tiny Little Better

纵向遍历，横向二分

Time Complexity: O(NlogM)

Binary-Tree

数组是沿着左上角到右下角递增的，但按照这个方向在每个元素只能排除掉两个方向。换个思路从二维数组的右上角开始搜索，小则向左，大则向右（像二叉树）。每次可以唯一确定一个查找方向。

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        i, j = len(matrix) - 1, 0
        while i >= 0 and j < len(matrix[0]):
            if matrix[i][j] < target:
                j += 1
            elif matrix[i][j] > target: 
                i -= 1
            else: 
                return True
        return False

Time Complexity: O(N+M)

重建二叉树（前序遍历、中序遍历）

Created Time: July 11, 2022 11:26 PM
Difficulty: Medium
Last Edited Time: July 13, 2022 10:36 PM
Link: https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/
No: 105
Tag: Tree

核心思想——分治

树本身属于规模化数据结构，可以考虑采用分治策略解题。

根据前序遍历和中序遍历的特点，我们可以把其做如下分割：

前序遍历：[ 根节点 | 根节点左子树 | 根节点右子树 ]

中序遍历：[ 根节点左子树 | 根节点 | 根节点右子树 ]

每一个segment的长度都可能为0（边界情况），为方便考虑问题暂且假设每一个非叶子节点都有两个子节点。边界情况将后续讨论。

根据前序遍历，可以找到唯一确定的根节点、根节点的左儿子（如果存在一定是当前节点右边的），但不能确定右边的部分在哪里进行切割（左子树有多长）。此外知道：如果可以切分，根节点右子树部分的第一个节点一定是当前节点的右儿子（前序遍历的特性）。

根据中序遍历，如果根节点的下标确定，可以找到左右子树的长度，即可带回上一步进行分治。

分治算法：

定义递归函数recur(root, left, right)

  • 参数：根节点在前序遍历的下标root，当前root树在中序遍历的左边界left，右边界right
  • 递归过程
    • 取中序遍历当前root值的下标idx
    • 左子树: recur(root + 1, left, idx - 1)
    • 右子树: recur(root + idx -left + 1, idx + 1, right)
      • root + idx - left + 1 为当前节点下标 + 左子树长度 + 1
  • 边界条件: left > right
    • 这样也同时解决了子节点不满的情况，若左节点为空，则左子树递归部分的left仍为当前idx，右边界idx - 1一定小于left。 右节点为空同理。

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def solver(root, left, right):
            if left > right: return
            val = preorder[root]
            idx = in_order_idx[val]
            node = TreeNode(val)
            node.left = solver(root + 1, left, idx - 1)
            node.right = solver(root + idx - left + 1, idx + 1, right)
            return node

        in_order_idx = {}
        for i in range(len(inorder)):
            in_order_idx[inorder[i]] = i
        return solver(0, 0, len(preorder) - 1)

用两个栈实现一个队列

Created Time: July 13, 2022 10:50 PM
Difficulty: Easy
Last Edited Time: July 13, 2022 10:59 PM
Link: https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
No: 105
Tag: Queue, Stack

核心思路

两个栈一个负责入队，一个负责出队，每次出队时先把入队栈里的元素都弹出并且压入出队栈。

可以把入队栈理解成一个缓存？差不多是这个意思。

class CQueue:
    def __init__(self):
        self.a, self.b = [], []
    def appendTail(self, value: int) -> None:
        self.a.append(value)
    def deleteHead(self) -> int:
        if self.b:
            return self.b.pop()
        if not self.a:
            return -1
        while self.a:
            self.b.append(self.a.pop())
        return self.b.pop()


# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

寻找旋转排序数组中的最小值 II

Created Time: July 13, 2022 11:15 PM
Difficulty: Hard
Last Edited Time: July 13, 2022 11:21 PM
Link: https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/
No: 154
Tag: Two Pointers

核心思路

一个比较直白的二分查找，旋转后，轴左边的任意一个数字均比右边的数字大，利用这个特性做二分缩小范围即可。

难点在于和153相比，数字可重复，这时候需要一格一格地缩小查找范围。（因此最坏情况下会出现O(N) 的时间复杂度)

Amortized Time Complexity: O(logN)

Worst Case: O(N)

class Solution:
    def minArray(self, numbers: [int]) -> int:
        i, j = 0, len(numbers) - 1
        while i < j:
            m = (i + j) // 2
            if numbers[m] > numbers[j]:
                i = m + 1
            elif numbers[m] < numbers[j]: 
                j = m
            else:
                j -= 1
        return numbers[i]