今天我们一起掌握 leetocode 的 88，89，104 题。

1. lc 88 - 合并两个有序数组

题目来源

  • 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 有足够的空间（空间大小等于 m + n）来保存 nums2 中的元素。
  • 难度：简单

1.1 法一 - 合并排序

最朴素的解法就是将两个数组合并之后再排序。复杂度差是由于这种方法没有利用两个数组本身已经有序。

1
2
3
4
5
6
7
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums1[:] = sorted(nums1[:m] + nums2[:n]) 
        return nums1[:]

复杂度：

  • 时间复杂度：O((m+n)*log(m+n))。
  • 空间复杂度：O(1)。

1.2 法二 - 双指针

一般而言，对于有序数组可以通过双指针法 达到O(n+m)的时间复杂度。

复杂度：

  • 时间复杂度：O(m+n)。
  • 空间复杂度：O(m)，复制nums1
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
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        pointer,pointer1, pointer2 = 0,0,0
        nums1_copy = nums1[:m].copy()
        # 防止 list 的 index 溢出
        nums1_copy.append(float('inf'))
        nums2.append(float('inf'))

        # 推进双指针，填充 nums1
        while pointer < m+n :
            if nums1_copy[pointer1] == float('inf'): 
                nums1[pointer] = nums2[pointer2]
                pointer2 += 1
            elif nums2[pointer2] == float('inf'): 
                nums1[pointer] = nums1_copy[pointer1]
                pointer1 += 1
            elif nums1_copy[pointer1] >= nums2[pointer2]:
                nums1[pointer] = nums2[pointer2]
                pointer2 += 1
            elif nums1_copy[pointer1] < nums2[pointer2]:
                nums1[pointer] = nums1_copy[pointer1]
                pointer1 += 1
            pointer += 1

2. lc 89 - 格雷编码

题目来源

  • 格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。格雷编码序列必须以 0 开头。
  • 难度：中等

2.1 解题思路 - 反射法 + 动态规划

通过反射的思路，能确保两个连续的数值仅有一个位数的差异。具体细节看图解。

用动态规划思想储存结果，最终返回。

2.2 时间复杂度

  • 时间复杂度： O(2^n)。因为有这么多个结果。
  • 空间复杂度： O(2^n)。

2.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
import math
class Solution:
    def grayCode(self, n: int) -> List[int]:
        if n == 0 : return [0]
        dp = [0 for _ in range(int(math.pow(2, n)))]
        dp[1] = 1
        for i in range(2,n+1):
            tmp = int(math.pow(2, i-1)) 
            new_data = dp[:tmp].copy() 
            new_data.reverse()
            new_data = [x+tmp for x in new_data]
            dp[tmp:tmp*2] = new_data
        return dp

3. lc 104 - 二叉树的最大深度

题目来源

  • 给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。
  • 难度：简单

3.1 解题思路 - 广度优先搜索(BFS)

用队列构建BFS。一层一层得查询树结点，用数据结构队列储存「当前层的所有节点」（待查询的节点），直到队列为空，说明已经找不到叶子结点。最终返回查询的步数（树的深度）。此题也可用DFS采用栈完成。但要注意如果此题如果是问图的最大深度，则一定要加入closedlist去重，以免路径成环。

时间复杂度

  • 时间复杂度：O(n) 其中 n 为二叉树的节点个数。由于是🌲，每个节点只会被访问一次。
  • 空间复杂度：O(n) 此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到O(n)。

代码

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        openlist = collections.deque()
        closedlist = set() # 因为此题为🌲，可以不加closedlist；若为图，则需要加
        cost = 0
        openlist.append(root)

        while openlist:
            openlist_size = len(openlist) # 确保遍历完同一层的节点，不能漏这步
            for i in range(openlist_size):
                node = openlist.popleft() # 注意不能写成 pop(),否则报错
                if node not in closedlist: 
                    if node.left:
                        openlist.append(node.left)
                    if node.right:
                        openlist.append(node.right)
                    closedlist.add(node)
            cost += 1

        return cost

3.2 解题思路 - 递归

如果我们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为 max(l,r) + 1

时间复杂度

  • 时间复杂度：O(n) 其中 n 为二叉树的节点个数。每个节点在递归中只被遍历一次。
  • 空间复杂度：O(depth) 其中 depth 表示二叉树的深度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

代码

1
2
3
4
5
6
7
8
9
10
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right)) + 1

参考

[1] LeetCode 数组：88 官方题解. https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetcode/