【PythonCode】力扣Leetcode41~45题Python版

前言

力扣Leetcode是一个集学习、刷题、竞赛等功能于一体的编程学习平台，很多计算机相关专业的学生、编程自学者、IT从业者在上面学习和刷题。
在Leetcode上刷题，可以选择各种主流的编程语言，如C++、JAVA、Python、Go等。还可以在线编程，实时执行代码，如果代码通过了平台准备的测试用例，就可以通过题目。
本系列中的文章从Leetcode的第1题开始，记录我用Python语言提交的代码和思路，供Python学习参考。

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：
输入：nums = [1,2,0]
输出：3
解释：
范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：
1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：
最小的正数 1 没有出现。
提示：
1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1

代码实现：

python">class Solution:def firstMissingPositive(self, nums: List[int]) -> int:for i in range(len(nums)):while 1 <= nums[i] <= len(nums) and nums[nums[i] - 1] != nums[i]:nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]for i in range(len(nums)):if nums[i] != i + 1:return i + 1return len(nums) + 1

解题思路：本题要找数组中缺失的第一个正整数，也就是从1开始，找到不存在于数组中的最小正整数。假如没有时间复杂度要求，可以从1开始枚举每一个正整数，并遍历数组判断其是否在数组中，直到找到一个不存在数组中的正整数。

数组的最大长度为10⁵ ，枚举的时间复杂度为O(n²)，空间复杂度为O(n)。题目要求时间复杂度为O(n)，且只能使用常数级别的额外空间，即空间复杂度为O(1)。

为了满足题目要求的时间复杂度和空间复杂度要求，需要先对数组nums做一次改造。数组中的数字一开始顺序是混乱的，我们将数字1放到数组的第一个位置（索引0），将数字2放到数组中的第二个位置（索引1），… 将数字n放到数组中的第N个位置（索引n-1），以此类推，将数组中的所有正整数都放到它对应的位置上。原数组中的数字除了正整数，还可能有0和负数，并且，前N个正整数中可能有一部分是缺失的，缺失的数字不能去“占领”它应该存在的位置，缺失的这些位置上数字不满足数字 i+1 保存在索引 i 的规律，重新遍历数组，找到第一个不符合规律的位置，就可以找到缺失的第一个正整数。

以题目中的示例2为例子，数组是[3, 4, -1, 1]，先改造数组，从索引0开始遍历数组，先将3与索引2的数字交换位置，得到[-1, 4, 3, 1]，交换后索引0的数字是-1，负数不需要找它自己的位置，继续遍历，将4与索引3的数字交换位置得到[-1, 1, 3, 4]，交换后索引1的数字是1，1还需要找它自己的位置，将1与索引0的数字交换位置得到[1, -1, 3, 4]，继续遍历，发现索引2和索引3不需要做处理，遍历结束，改造后的数组为[1, -1, 3, 4]。在改造后，从数组的第一个位置开始找，发现索引1的数字不是2，所以缺失的第一个正整数是2。

结合代码，从索引0开始遍历数组，如果当前索引的数字大小在1到数组长度之间，说明该数字在数组中有一个对应的位置，对应位置的索引为(nums[i]-1)，如果当前数字与对应位置的数字不相等，则交换它们，将当前数字“归位”。（如果与对应位置的数字相等，说明至少有两个数字的值相等，此时直接跳过。）交换之后，继续判断交换过来的数字大小是否在1到数组长度之间，如果是则继续将其“归位”，直到交换过来的数字“无位可归”，则往后遍历，当索引遍历到最大，整个数组就改造完成了。此时，从头开始遍历数组，遇到第一个索引 i 的数字不是 i+1，则 i+1 是缺失的第一个正整数。如果整个数组都满足数字与位置对应，则缺失的第一个正整数是数组长度加1，如[1, 2, 3]缺失的第一个正整数是4。

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length
1 <= n <= 2 * 10⁴
0 <= height[i] <= 10⁵

代码实现：

python"> class Solution:def trap(self, height: List[int]) -> int:result = 0pre_max = 0suf_max = 0left, right = 0, len(height)-1while left < right:pre_max = max(pre_max, height[left])suf_max = max(suf_max, height[right])if pre_max < suf_max:result += pre_max - height[left]left += 1else:result += suf_max - height[right]right -= 1return result

解题思路：题目给定一个数组，用数组中的每个数表示宽度为1的柱子的高度，柱子的高度不一样，把柱子并排放在一起，它们之间会有凹槽，要求计算凹槽能接多少雨水。

求解的关键是问题分析，将整个图形能接多少雨水拆分到每一根柱子，找到每一根柱子与接雨水的关系。在接雨水时柱子是组合在一起的，不过在计算接雨水的量时单独计算每跟柱子接了多少雨水，每跟柱子接的雨水就是该柱子上方能积多少水。当前柱子上是否能积水，取决于它两边是否有高于自身的柱子。找到当前柱子左边最高的一根柱子、右边最高的一根柱子，如果这两根柱子都高于当前柱子，那么当前柱子上会积水。只要其中一边的最高柱子不高于当前柱子，则当前柱子上不会积水（积水量为0）。如果当前柱子能积水，积水量由左右两边最高柱子中较低的一根决定（木桶原理）。因为柱子的宽度为1，柱子的高度差等于积水量。

根据上面的分析实现代码。因为需要用到柱子两边的最高柱子高度来计算积水量，所以使用双指针从数组首尾开始向中间移动。并初始化两个变量来记录左右两边最高柱子的高度，这两个高度值最开始为首尾两根柱子的高度，如果移动左指针，则将左边的最高高度与左指针指向的柱子高度相比，判断是否需要更新最高高度，移动右指针同理。因为积水量是由左右最高柱子中较低的一根柱子决定的，所以如果左边的最高柱子低于右边的最高柱子，则计算左指针指向的柱子积水量，然后移动左指针，反之。（不能从更高的一边开始，因为数组没有遍历完时，不能判断更低的那边有没有可能变大）。这样直到左右指针相遇时，计算完所有柱子的积水，计算过程中将所有积水量累加，就是本题答案。

43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:
输入: num1 = “2”, num2 = “3”
输出: “6”
示例 2:
输入: num1 = “123”, num2 = “456”
输出: “56088”
提示：
1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。

代码实现：

python">class Solution:def multiply(self, num1: str, num2: str) -> str:# return str(int(num1)*int(num2))result = 0w1 = 1for i in range(len(num1)-1, -1, -1):m = int(num1[i])w2 = 1for j in range(len(num2)-1, -1, -1):n = int(num2[j])result += m * n * w2 * w1w2 = w2 * 10w1 = w1 * 10return str(result)

解题思路：本题要计算两个字符串形式的数字的乘积，结果也转成字符串形式。实现思路类似于小学写多位数相乘的方法，从其中一个数的个位开始，依次乘以另一个数的每一位，将所有乘积写到对应位数的位置，最后将所有乘积相加。

根据这个思路，从最后一位开始遍历num1和num2，将所有数字相乘，相乘过程中，用两个变量w1，w2标记当前数字位数，对于num1和num2，取完个位则到十位，取完十位则到百位…，所以每计算一个数字，w1，w2对应增长10倍。遍历num1和num2中所有数字相乘累加就可以得到答案。

44. 通配符匹配

给你一个输入字符串 s 和一个字符模式 p，请你实现一个支持 ‘?’ 和 ‘*’ 匹配规则的通配符匹配：

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够完全匹配输入字符串（而不是部分匹配）。

示例 1：
输入：s = “aa”, p = “a”
输出：false
解释：
“a” 无法匹配 “aa” 整个字符串。
示例 2：
输入：s = “aa”, p = “*”
输出：true
解释：
‘*’ 可以匹配任意字符串。
示例 3：输入：s = “cb”, p = “?a”
输出：false
解释：
‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。
提示：
0 <= s.length, p.length <= 2000
s 仅由小写英文字母组成
p 仅由小写英文字母、‘?’ 或 ‘*’ 组成

代码实现：

python">class Solution:def isMatch(self, s: str, p: str) -> bool:m, n = len(s), len(p)dp = [[False for _ in range(m+1)] for _ in range(n+1)]dp[0][0] = Truefor i in range(1, n+1):if p[i-1] == '*':dp[i][0] = Trueelse:breakfor i in range(1, n+1):for j in range(1, m+1):if p[i-1] == '*':dp[i][j] = dp[i-1][j] or dp[i][j-1]elif p[i-1] == '?' or s[j-1] == p[i-1]:dp[i][j] = dp[i-1][j-1]return dp[n][m]

解题思路：本题与力扣第10题很相似，解题思路也一样，用动态规划。
力扣第10题可以参考：PythonCode】力扣Leetcode6~10题Python版，
动态规划可以参考：循序渐进，搞懂什么是动态规划。

字符串匹配时， ? 和 * 分别表示匹配任意一个字母和匹配任意多个连续的字母（也可以是0个）。题目中的输入是两个字符串s和p，问号和星号出现在匹配字符串p中，我们的目标是判断p能否按规则完整地匹配s。

按照动态规划的解题步骤，第一步先定义问题的状态，用dp[i][j]表示p的前i个字符和s的前j个字符能否匹配，如果字符串p的长度为n，字符串s的长度为m，则dp[n][m]就是问题的答案。

第二步为列出状态转移方程，如果p[i]==s[j]或p[i]==?，说明p的第i个字符和s的第j个字符可以匹配，那么就看前面的字符是否可以匹配，状态转移方程：dp[i][j]=dp[i−1][j−1]。如果p[i]==‘*’，星号可以匹配任意多个字符，分为两种情况，如果不使用星号（匹配0个字符），状态转移方程：dp[i][j]=dp[i-1][j]，如果使用星号（匹配1个或多个字符），状态转移方程：dp[i][j]=dp[i][j-1]。注意，这里使用星号后，状态转移方程中p的索引i没有变，星号匹配s[j]后，还可以根据情况判断是否继续匹配s[j-1]，所以可以使用多次。

第三步为状态初始化，先初始化一个长度为n+1乘m+1的dp数组，如果字符串s和字符串p都是空字符串，可以匹配，初始化为：dp[0][0]=True。因为p中的星号可以表示0次，所以如果s为空，p中的字符全为星号，或p的前i个字符全为星号，dp[i][0]为True。

关于初始化，还有一点注意事项，因为初始化dp[0][0]是字符串s和p都为空，所以字符串非空时，dp[i][j]中的i和j是从1开始的，而字符串的索引是从0开始的，所以索引要比状态编号减一，也就是说，上面的分析中，在代码中s或p的索引要再减1。同时，因为状态编号从1开始，所以代码需要遍历到m+1和n+1，这也是dp数组大小为n+1乘m+1的原因。

45. 跳跃游戏 II

给定一个长度为 n 的 0索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释:
跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
1 <= nums.length <= 10^4
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]

代码实现：

python">class Solution:def jump(self, nums: List[int]) -> int:max_pos, steps, end = 0, 0, 0for i in range(len(nums)):max_pos = max(max_pos, i + nums[i])if i == end and end != len(nums)-1:end = max_possteps += 1return steps

解题思路：题目要求用最少的跳跃次数从数组开头跳到数组结尾，所以每次跳跃都要跳到尽可能远的位置，这就符合贪心算法的策略。贪心算法参考：循序渐进，搞懂什么是贪心算法

根据题意，在位置 i 时，可以跳跃到的最远位置为i+nums[i]。不过在跳跃多步时，并不是每一步都直接跳到最远位置，可能最远位置的数值很小，下一步能跳的距离很短，不是最优解。具体看一个例子。以[2, 3, 1, 4, 3, 6, 2, 1]为例，在索引0时，可以跳跃的最远距离是2，因此可以选择跳到索引1或索引2，当前这一步可以跳到的最远位置为索引2，但如果考虑下一步，跳到索引1下一步最远能跳到索引4，而跳到索引2下一步只能跳到索引3。而如果再继续分析，不管第一步跳到索引1还是跳到索引2，最终结果都一样，跳到终点需要3步。

在这里插入图片描述

可以看出，如果综合考虑多步，当前直接跳到最远位置可能更好，也可能更坏，还有可能不影响总步数。因此，如何定义贪心策略非常重要。

为了更一般地表示贪心策略，在数组的任意位置，都计算从当前位置跳跃一次能到达的最远位置，与之前的位置能跳到的最远位置比较，看是否能到达更远的位置。同时，因为要使总步数最少，所以，记录跳跃步数的方式非常关键。在某个位置时，之前的跳跃步数可以跳到当前位置，在遍历数组的每个位置时，如果索引位置还在上一次跳跃能到达的范围内部，则跳跃次数不增加，当前索引到达上一次跳跃的终点时，继续向前就要再次向前跳跃，跳跃步数加一。

结合前面的分析实现代码，初始化变量max_pos，记录在某个位置时，之前的跳跃或从当前位置跳跃能到达的最远位置。初始化变量steps记录跳到当前位置时使用的最少步数。初始化变量end记录上一次跳跃能到达的终点。遍历数组，在每个位置都计算之前及当前索引能跳的最远位置，不断更新max_pos，如果遍历到了上一步跳跃的终点，则需要再往前跳一步，新的一步最远能跳到max_pos处，更新end和steps。

注意事项：

代码中遍历数组，依次求到达每个位置的最小步数，遍历到数组末尾，就可以求出跳到数组末尾的最小步数，这正好匹配贪心算法的解题思路，但是不能把遍历数组索引与跳跃次数混淆了。
到达一个位置的最少步数是从该位置向前跳跃前的总步数，因此，如果上一次跳跃的终点已经是数组的末尾，说明上一次跳跃刚好能到达数组的最后一个位置。在最后一个位置不用再向前跳了。
题目保证生成的测试用例可以到达数组末尾，所以不需要加判断，能到达末尾，必然也能到达任意一个位置。《力扣55题跳跃游戏》要求实现判断能否跳到终点的功能。（本系列按顺序更新，后面更新到第55题可以结合一起看。）