【PythonCode】力扣Leetcode36~40题Python版

前言

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

36. 有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则 ，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 空白格用 '.' 表示。

示例 1：输入：board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true
示例 2：
输入：board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'

代码实现：

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for i in range(9):
            sr, sc, ss = set(), set(), set()
            for j in range(9):
                if board[i][j] != ".":
                    if board[i][j] in sr:
                        return False
                    sr.add(board[i][j])
                if board[j][i] != ".":
                    if board[j][i] in sc:
                        return False
                    sc.add(board[j][i])
                row, col = i // 3 * 3 + j // 3, i % 3 * 3 + j % 3
                if board[row][col] != ".":
                    if board[row][col] in ss:
                        return False
                    ss.add(board[row][col])
        return True

解题思路：数独很多人都接触过，我本人大学时还参与过数学协会举办的数独比赛，平时也多次在地铁上看到人用手机玩数独游戏。数独的规则比较简单，在9*9的方格内填入数字1-9，每行中1-9只能出现一次，每列中1-9只能出现一次，将9*9的方格分成9个3*3的大方格，每个3*3的方格中1-9也只能出现一次，所以叫数独游戏。

一个数独问题初始时通常已经有部分位置被填充（参考示例图），解数独就是在满足规则的情况下，填满所有81个方格。数独已填入的部分不一定满足规则，本题要求验证已填入的数字是否满足数独规则，判断当前状态是否为一个有效的数独，而不需要解数独，也不用管数独是否有解。（部分填充的数独不一定有解，也可能有多种解，下一题将会实现解数独。）

要判断数独是否有效，需要判断所有行、列和3*3的方格中是否存在重复数字，为了保证数字不重复，可以使用集合来存储每行、每列和每个3*3方格中的数字，如果有任何一个数字与集合中的数字重复，则数独无效。如果检查的数字不在集合中，将数字添加到对应的集合中，检查到最后也没有重复数字，则数独有效。

要遍历每行、每列和每个3*3的方格中的数字，需要使用行索引 i 和列索引 j ，数独有9行、9列和9个3*3方格，所以要先找到它们与 i 和 j 的关系。先实例化一个例子，对于数独中的每一个格子 board[i][j]，当行索引i为0时，从0-8遍历列索引j，board[0][j]就是第一行，board[j][0]就是第一列。对于3*3的方格，第一个3*3方格中的位置分别是board[0][0]，board[0][1]，board[0][2]，board[1][0]，board[1][1]，board[1][2]，board[2][0]，board[2][1]，board[2][2]，此时i为0，j为0-8，将第一个3*3方格的每一个格子表示成board[row][col]，需要找到row、col与i和j的关系，最终得到的关系为row=j//3（取整除），col=j%3（取余），j为0,1,2时，对应board[0][0]，board[0][1]，board[0][2]，j为3,4,5时，对应board[1][0]，board[1][1]，board[1][2]，j为6,7,8时，对应board[2][0]，board[2][1]，board[2][2]。第一个3*3方格只用到j就能表示对应关系，要找到所有3*3方格与i和j的关系，需要更复杂的关系表达式。更一般地，对于任意i和j，每一行为board[i][j]，每一列为board[j][i]，每一个3*3方格为board[row][col]，其中row=i//3*3+j//3，col=i%3*3+j%3。（这里可以实例化每个3*3方格来找出关系）

有了上面的分析，就可以根据思路写代码了，遍历i，i为0时嵌套遍历j验证第一行、第一列、第一个3*3方格，i为1时嵌套遍历j验证第二行、第二列、第二个3*3方格，... ，直到验证完整个数独。

37. 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：
输入：
board =
[["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
输出：
[["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]]
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据保证输入数独仅有一个解

代码实现：

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def backtrack(board, i, j):
            if j == 9:
                return backtrack(board, i+1, 0)
            if i == 9:
                return True
            if board[i][j] != '.':
                return backtrack(board, i, j+1)
            for n in range(1, 10):
                c = str(n)
                if not self.is_valid(board, i, j, c):
                    continue
                board[i][j] = c
                if backtrack(board, i, j+1):
                    return True
                board[i][j] = '.'
        backtrack(board, 0, 0)

    def is_valid(self, board, row, col, c):
        for i in range(9):
            if board[row][i] == c:
                return False
            if board[i][col] == c:
                return False
            if board[(row//3)*3 + i // 3][(col//3)*3 + i % 3] == c:
                return False
        return True  

解题思路：数独的规则在题目描述和上一题中已经充分说明了，不再赘述。现在有一个部分被填充的数独，题目保证这个数独是有效的，并且有且只有一个解，本题要解数独。

解数独就是把非数字的格子用数字填满，且满足数独规则。填写的方法是枚举，对于每一个格子，都从1开始预填入数字，预填入后检查新的状态是否为有效的数独，无效则撤回重新填写。如果当前位置已经枚举完1-9，数独仍然无效，则需要撤回上一个数或撤回更多前面填的数。这种情况应该使用回溯算法，回溯法可以按深度优先策略穷举整个解空间所有可能的解（有剪枝）。参考：循序渐进，搞懂什么是回溯算法，前面的力扣17题和力扣22题也是用回溯法求解，可以结合一起看，加深理解。

按照回溯法的求解步骤，先定义回溯的解空间，根据题目的输入和输出，数独的解是一个二维数组board。

输入的二维数组board中有些值是 '.'，解数独就是将这些值换成有效的数字字符串，撤回时将数字字符串改回 '.'。由于不知道每行、每列、每个3*3方格中有多少已知的值，所以每一行的最大搜索深度是9减当前行已知数字的个数，整体的最大搜索深度是81减所有已知数字的个数，回溯法在这棵很深的搜索树中进行深度优先搜索。

求解时，按照一行一行的顺序填写数字，填满第一行再跳转到第二行。因为搜索树的深度非常大，所以必须在求解过程中尽早剪枝，所以每填一个数字前，都先检查是否满足数独规则，满足后再填入数字。

结合代码，对于二维数组board中的每一个格子board[i][j]，都提前判断数字是否可以填入。先实现一个检查能否将某个数字填入某个格子的方法，供判断时反复调用，这个方法与上一题判断数独是否有效有点区别，上一题是判断初始状态已填的数字是否有效，这里是判断某个数字能否填入某个格子。判断数字c能否填入board[i][j]时，只需要判断i行、j列、当前的3*3方格中是否已经存在数字c，存在就不能填，不存在就可以填。

然后实现回溯函数，一行一行地解，每解一行，跳转到下一行的开头，当解完9行时，整个数独求解完成。回溯过程中，如果board[i][j]的位置有初始数字，直接跳过（这可以减小搜索树深度）。从1-9依次枚举每个数字，判断数字能否填入board[i][j]，不能则跳过（剪枝），能则填入数字，继续枚举下一个位置。撤回某个数字时，将board[i][j]改回原来的 '.' 。

最后调用回溯函数，传入二维数组board，从第一个位置board[0][0]开始搜索解空间。

38. 外观数列

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

• countAndSay(1) = "1"
• countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：

1. 1
2. 11
3. 21
4. 1211
5. 111221
   解释：
   第一项是数字 1
   描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
   描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
   描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
   描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"

要描述一个数字字符串，首先要将字符串分割为最小数量的组，每个组都由连续的最多相同字符组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串 "3322251" 的描述如下图：

示例 1：
输入：n = 1
输出："1"
解释：这是一个基本样例。
示例 2：
输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"
提示：
1 <= n <= 30

代码实现：

class Solution:
    def countAndSay(self, n: int) -> str:
        prev = "1"
        for i in range(n-1):
            cur = ""
            pos = 0
            start = 0
            while pos < len(prev):
                while pos < len(prev) and prev[pos] == prev[start]:
                    pos += 1
                cur += str(pos - start) + prev[start]
                start = pos
            prev = cur
        return prev

解题思路：外观数列的第一项是字符串'1'，后面的每一项都是对前一项的描述，描述规则参考题目描述和示例。第n项要描述第n-1项，关键是识别出第n-1项中连续的相同数字字符。

根据题目对外观数列的定义，按照规则写代码，并不难。初始化一个变量prev记录第一项'1'，根据规律求第二项，第三项，...，每求出一个值都将其赋值给prev，这样可以循环继续推下一项。推下一项的关键是找连续的相同数字字符，先初始化一个空字符cur，以便不断将描述字符拼接到cur中。用一个指针start指向字符串的头，用另一个指针pos从字符串的头开始向后移动，当游标pos遇到与start不同的字符时，前面这一段字符的描述是pos-start个prev[start]字符，此时把这段描述拼接到cur中。然后将指针start移到pos的位置，pos继续向后移动，描述下一段相同的字符，如此循环直到字符串结尾。

这样从第一个字符串开始，依次推它的下一个字符串，循环推导n-1次，就可以得到第n项。

39. 组合总和

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合 ，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
提示：
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40

代码实现：

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        result = []
        def backtrack(start, curr, target):
            for i in range(start, len(candidates)):
                c = candidates[i]
                if c == target:
                    result.append(curr + [c])
                    return
                if c < target:
                    backtrack(i, curr+[c], target-c)
                if c > target:
                    return
        backtrack(0, [], target)
        return result

解题思路：根据题意，整数数组中没有重复元素，但是每个数都可以重复使用多次，题目要求从数组中找到和为target的所有组合。

要用数组中的数相加得到target，就需要不断枚举数组中的每个数，逐步相加到一起，直到和等于target，得到一种组合，再继续枚举其他情况。如果在和小于target时，再加上一个数就大于target，说明这种组合不满足，则要撤回枚举的数。很明显，本题应该使用回溯法，回溯法可以按深度优先策略穷举解空间的所有可能，可以参考上面的力扣37题。

按照回溯法的求解步骤，先定义回溯的解空间，根据题目要求，和为target的一种组合是一个数组，所有的组合又保存在一个大的数组中。根据1<=target<=40和2<=candidates[i]<=40，可以确定回溯法的搜索树深度不超过20。求解时，从数组的第一个数开始枚举，因为数字可以重复使用，可以先一直枚举第一个数，再回溯枚举后面的数，直到枚举完整个数组。

结合代码，先将数组排序，这样才能控制枚举的顺序和判断枚举结束的边界。初始化一个数组result用于保存满足要求的组合，每找到一种组合，都添加到result中。然后定义回溯函数，回溯函数中传入一个开始索引，表示回溯函数当前从数组中的第几个值开始枚举。传入一个数组和当前的目标值，用于保存当前已经枚举的组合和当前剩余目标值，每枚举一个数，都将其保存到当前数组中，剩余的目标值都是目标值减去已枚举的数字，不满足时回溯函数直接返回，组合中不添加数字，目标值不变。继续枚举下一个数时，将已枚举的组合和剩余目标值传给回溯函数。回溯函数中，如果当前枚举的值已经等于剩余目标值，则找到一种组合。如果当前枚举的值小于剩余目标值，说明数组组合还未达到目标值，继续以当前索引为开始索引，递归调用回溯函数，这样调用会先重复取前面的数，回溯过程中再取后面的数。如果当前枚举的值大于目标值，则往回回溯。

最后，调用回溯函数，传入开始索引0，从数组第一个数开始枚举，传入一个空数组用于保存当前组合，传入目标值target。

40. 组合总和 II

给定一个候选编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次 。

注意：解集不能包含重复的组合。

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出: [
[1,2,2],
[5]
]
提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

代码实现：

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        result = []
        def backtrack(start, curr, target):
            for i in range(start, len(candidates)):
                c = candidates[i]
                if i>start and candidates[i]==candidates[i-1]:
                    continue
                if c == target:
                    result.append(curr + [c])
                    return
                if c < target:
                    backtrack(i+1, curr+[c], target-c)
                if c > target:
                    return
        backtrack(0, [], target)
        return result

解题思路：本题是上一题的变体，与上一题对比，主要差别为candidates数组，上一题的数组中数字都不重复，但每个数都可以反复使用多次。本题的数组中可能有重复的数字，但数组中的每个元素只能用一次。注意，如果数组中有多个元素的数值相等，则它们分别都可以在每种组合中使用一次。此外，数组的长度、每个元素的范围、target的范围不一样，不过这不影响解题思路。

求解方法还是使用回溯法，代码也跟上一题基本相同，根据题目的条件，在回溯函数中做相应的调整。先将数组排序，因为结果不能保存重复的组合，所以当开始索引与上一次的开始索引相等时直接跳过。因为每个元素只能使用一次，所以递归调用回溯函数时，开始索引递增。其他的部分都一样。

回溯的几道题，可以结合起来一起看，更方便理解求解思路。