LeetCode Cookbook 数组习题（3）

LeetCode Cookbook 数组习题（3）

  篇接上回，开始！

78. 子集*

题目链接：78. 子集
题目大意：给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

• 两种解法 回溯的方法 helper（）
• 中间结果的显示
• [[]]
• [[], [1]]
• [[], [1], [1, 2]]
• [[], [1], [1, 2], [1, 2, 3]]
• [[], [1], [1, 2], [1, 2, 3], [1, 3]]
• [[], [1], [1, 2], [1, 2, 3], [1, 3], [2]]
• [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]]
• [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)

        def helper(i: int,tmp: List[int]) -> None:
            ans.append(tmp)
            for j in range(i,n):
                helper(j+1,tmp+[nums[j]])
        helper(0,[])
        return ans
1
2
3
4
5
6
7
8
9
10
11

491. 递增子序列

题目链接：491. 递增子序列
题目大意：给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

• 在 78. 子集 的版本上进行改进
• 添加 长度 和 非递减条件
• 同时添加 回溯函数的循环中添加 去重操作

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)
        def helper(i: int,tmp: List[int]) -> None:
            # 添加终止条件的判断
            # 子集长度大于2 录用
            if len(tmp) > 1:
                # 满足 非递减要求
                if tmp[-1] >= tmp[-2]:
                    ans.append(tmp)
                else:
                    return
            # 谨慎使用 会造成测试超时！
            # print(ans)
            # 添加去重操作
            for j in range(i,n): 
                if nums[j] in nums[i:j]:
                    continue
                helper(j+1,tmp+[nums[j]])
        helper(0,[])
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

90. 子集 II

题目链接：90. 子集 II
题目大意：给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

解题思路：

• 相比于78. 子集的回溯结构内的循环加上 if nums[j] in nums[i:j]: continue
• • 在开始回溯之前 nums.sort() 一下

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)
        nums.sort()
        def helper(i:int,tmp: List[int]) -> None:
            ans.append(tmp)
            for j in range(i,n):
                if nums[j] in nums[i:j]:
                    continue
                helper(j+1,tmp+[nums[j]])
        
        helper(0,[])
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14

79. 单词搜索*

题目链接：79. 单词搜索
题目大意：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

解题思路：与417. 太平洋大西洋水流问题相近

• 这些题很不容易快速地写出来 记忆是最好的办法 不过硬背不是一个好方法
• 这道题是78. 子集 与 491. 递增子序列的高级进阶版本
• 回溯主要难点就在于条件的设置,参照我的这篇题解 491. 递增子序列：78. 子集 的进阶版本的回溯方法可以看出本题的条件设置主要是：
• （1）单个字符串的正误判断和数量判断，这直接决定了返回的False与True；
• （2）方向的设定，这道题相对于417. 太平洋大西洋水流问题更加精明一些，至少在这一步 for di,dj in directions:非常写意！同时注意directions的创建。
• （3）去重的设置，这是一个老生常谈的话题了，有些人喜欢用 visited 不过我更偏向于 seen，切记这是集合形式 set()。

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # 移动方向 上 下 左 右
        directions = [(0,-1),(0,1),(-1,0),(1,0)]
        

        def helper(i: int,j: int, k: int) -> bool:
            if board[i][j] != word[k]: return False
            if len(word) ==  k+1: return True

            # 记录走过的路径，去重复操作
            seen.add((i,j))
            result = False
            for di,dj in directions:
                iNew,jNew = i+di,j+dj
                if 0<=iNew<m and 0<=jNew<n:
                    if (iNew,jNew) not in seen:
                        if helper(iNew,jNew,k+1):
                            result = True
                            break
            seen.remove((i,j))
            return result
        
        m,n = len(board),len(board[0])
        seen = set()
        for i in range(m):
            for j in range(n):
                if helper(i,j,0):
                    return True
        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

81. 搜索旋转排序数组 II

题目链接：81. 搜索旋转排序数组 II
题目大意：已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。在传递给函数之前，nums 在预先未知的某个下标 **k（0 <= k < nums.length）**上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。 给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。 你必须尽可能减少整个操作步骤。

解题思路： 33. 搜索旋转排序数组 的区别在于 nums[0] 换成了 nums[L] 同时需要注意去重操作 if nums[mid] == nums[L]: L += 1

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        # nums_new = set(nums) 
        # return False if target not in nums_new else True

        n = len(nums)
        if target not in nums: return False
        if n == 1:  return nums[0] == target
        L,R = 0,n-1
        while L <= R:
            mid = L + (R-L)//2
            if nums[mid] == target: return True
            if nums[mid] == nums[L]: 
                L += 1
            elif nums[L] <= nums[mid]:
                if nums[L] <= target < nums[mid]:
                    R = mid-1
                else:
                    L = mid+1
            else:
                if nums[mid] < target <= nums[n-1]:
                    L = mid+1
                else:
                    R = mid-1
        print(L,R)
        return False if nums[L] != target else True
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

84. 柱状图中最大的矩形 **

题目链接：84. 柱状图中最大的矩形
题目大意：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
解题思路： 非常不错的一道题，很TM的恶心！！！ 单调栈，有关的讲解，非常的多，不过还是要看代码和过程量来分析，这道题的要点就是：

1. 与42. 接雨水有很大的不同，注意这里是实体柱，每一个0都非常的让人头疼，尝试过分段处理，但非常不理想，也很不好实施；
2. 记住计算的长方形面积的宽度分别为每一根柱子的高度的情况，也就是转化成求长方形长度上，在通透些，求长方形左右下标上！
3. 其他的没什么了，看代码，学习！这里附上自己调试过程中的一些量，非常有助于理解。

• 实例如下图所示：
  

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        heights = [0] + heights + [0]
        res = 0
        # print('heights:',heights)
        for i in range(len(heights)):
            # print(stack)
            while stack and heights[stack[-1]] > heights[i]:
                tmp = stack.pop()
                # print('i:',i,'tmp:' ,tmp,'heights[tmp]',heights[tmp])
                # print('area:',((i- 1) - stack[-1]) * heights[tmp])
                res = max(res, ((i- 1) - stack[-1]) * heights[tmp])
                # print(res)
            stack.append(i)
        return res 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

88. 合并两个有序数组

题目链接：88. 合并两个有序数组
题目大意：给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

解题思路： 挺有趣的 从nums1的尾巴尖向上赋值。

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.
        """
        # 要放的数字指针
        p1,p2 = m-1,n-1
        k = m+n-1
        while p1>=0 or p2>=0:
            if p1 == -1:
                nums1[k] = nums2[p2]
                p2 -= 1
            elif p2 == -1:
                nums1[k] = nums1[p1]
                p1 -= 1
            elif nums1[p1] > nums2[p2]:
                nums1[k] = nums1[p1]
                p1 -= 1
            else:
                nums1[k] = nums2[p2]
                p2 -= 1
            k -= 1     
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

105. 从前序与中序遍历序列构造二叉树 **

题目链接：105. 从前序与中序遍历序列构造二叉树
题目大意：给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点

解题思路： 都在代码中注释了，复习了一下，前序和中序遍历。

（一） GF的迭代稍微复杂些，但非常有助于理解

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    
        def myBuildTree(preorder_L: int,preorder_R: int,inorder_L: int,inorder_R: int) -> Optional[TreeNode]:
            if preorder_L > preorder_R:
                return None

            # 前序遍历第一个节点是根节点
            preorder_root = preorder_L
            # 中序遍历定位根节点
            # print(preorder_L,preorder_R)
            inorder_root = index[preorder[preorder_root]]

            # 建立根节点
            root = TreeNode(preorder[preorder_root])
            # 计算左子树根结点个数
            size_left_subTree = inorder_root - inorder_L
            # 先序遍历中 左边界+1 后的 size_left_subTree 个元素对应
            # 中序遍历中 左边界开始 到 根节点定位-1
            root.left = myBuildTree(preorder_L+1,preorder_L+size_left_subTree,inorder_L,inorder_root-1)
            # 先序遍历中 左边界+1+size_left_subTree 到 右边界 的元素对应
            # 中序遍历中 根节点定位+1 到 右边界元素
            root.right = myBuildTree(preorder_L+size_left_subTree+1,preorder_R,inorder_root+1,inorder_R)
            return root

        n = len(preorder)
        # 构造哈希映射，有助于快速定位根节点
        index = {element:i for i,element in enumerate(inorder)}
        return myBuildTree(0,n-1,0,n-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
35

（二） 简化后的迭代

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        
        def helper(in_L,in_R):
            # end condition
            if in_L>in_R: return None

            val = preorder.pop(0)
            root  = TreeNode(val)
            in_Root = index[val]
            # 前序遍历 先左子树 后右子树
            root.left = helper(in_L,in_Root-1)
            root.right = helper(in_Root+1,in_R)
            return root
        index = {element:i for i,element in enumerate(inorder)}  
        return helper(0,len(inorder)-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

106. 从中序与后序遍历序列构造二叉树

题目链接：106. 从中序与后序遍历序列构造二叉树
题目大意：给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

解题思路：105. 从前序与中序遍历序列构造二叉树 思路一致 注意后序遍历 先右子树 后左子树

# 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 buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        
        def helper(in_L: int,in_R: int) -> Optional[TreeNode]:
            if in_L>in_R: return None       # 终止条件
            val = postorder.pop()           # 有后序遍历找到根节点的值
            root = TreeNode(val)            # 根节点进行封装
            in_Root = index[val]            # 找到根节点在中序遍历中的位置
            # 后序遍历 先右子树 之后左子树
            root.right = helper(in_Root+1,in_R)
            root.left = helper(in_L,in_Root-1)
            return root

        index = {element:i for i,element in enumerate(inorder)}
        return helper(0,len(inorder)-1)          
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

118. 杨辉三角

题目链接：118. 杨辉三角
题目大意：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

解题思路： 此题不难，关键是在做的过程中搞清楚 这是一个二维数组 的增改。

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        
        # 精炼一点
        '''
        ans = list()
        for i in range(numRows):
            tmp  = list()
            for j in range(0,i+1):
                if j==0 or j==i:
                    tmp.append(1)
                else:
                    tmp.append(ans[i-1][j-1]+ans[i-1][j])
            ans.append(tmp)
        return ans

        '''        
        
        # 有点随意的
        ans = []
        ans += [[1]]
        if numRows == 1: return ans
        ans += [[1,1]]        
        if numRows == 2: return ans
        for i in range(1,numRows-1):
            tmp = []
            # print(ans[i])
            for a,b in zip(ans[i][0:i+1],ans[i][1:i+2]):
                tmp += [a+b]
            ans += [[1] + tmp + [1]]
        return ans   
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

119. 杨辉三角 II

题目链接：119. 杨辉三角 II
题目大意：给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

解题思路： 背一下吧，是组合中的一些公式。

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        ans = [1]
        for i in range(1,rowIndex+1):
            ans.append(ans[-1]*(rowIndex-i+1)//i)
        return ans    
1
2
3
4
5
6

120. 三角形最小路径和 *

题目链接：120. 三角形最小路径和
题目大意：给定一个三角形 triangle ，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

• [2]
• [3,4]
• [6,5,7]
• [4,1,8,3]

解题思路： 不清楚LC的评价体系是如何，但这道题确实值得多刷两遍，是一道非常经典的动态规划题！

• 从底部往上走，在自身数组上进行维护 triangle[i][j] = triangle[i][j]+min(triangle[i+1][j],triangle[i+1][j+1])

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        m = len(triangle)
        print(m-2)
        for i in range(m-2,-1,-1):
            # for j in range(i,-1,-1):
            for j in range(len(triangle[i])):
                triangle[i][j] = triangle[i][j]+min(triangle[i+1][j],triangle[i+1][j+1])
        return triangle[0][0]
1
2
3
4
5
6
7
8
9

121. 买卖股票的最佳时机 *

题目链接：121. 买卖股票的最佳时机
题目大意：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

解题思路： 动态规划 很不错的题！

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        ans,minNum = 0,prices[0]
        for i in range(1,n):
            if prices[i] - minNum > ans:
                ans = prices[i] - minNum
            if prices[i] < minNum:
                minNum = prices[i]
        return ans
1
2
3
4
5
6
7
8
9
10

总结

  不想写过长的结尾了，这一套题大部分都是 回溯或者说递归类型的题，其中：78. 子集、84. 柱状图中最大的矩形，以及动态规划的题：118. 杨辉三角、120. 三角形最小路径和，这些题技巧性很强需要经常复习总结归纳，现在发现写代码不仅需要解题的思路，更重要是选用什么样的程序结构以及变量的容器选取，这些都很重要，并且与所使用的语言息息相关，不多说了，努力，奋斗！