【PythonCode】力扣Leetcode36~40题Python版
前言
力扣Leetcode是一个集学习、刷题、竞赛等功能于一体的编程学习平台,很多计算机相关专业的学生、编程自学者、IT从业者在上面学习和刷题。
在Leetcode上刷题,可以选择各种主流的编程语言,如C++、JAVA、Python、Go等。还可以在线编程,实时执行代码,如果代码通过了平台准备的测试用例,就可以通过题目。
本系列中的文章从Leetcode的第1题开始,记录我用Python语言提交的代码和思路,供Python学习参考。
36. 有效的数独
请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则 ,验证已经填入的数字是否有效即可。
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 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 Falsesr.add(board[i][j])if board[j][i] != ".":if board[j][i] in sc:return Falsesc.add(board[j][i])row, col = i // 3 * 3 + j // 3, i % 3 * 3 + j % 3if board[row][col] != ".":if board[row][col] in ss:return Falsess.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-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 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 Trueif 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):continueboard[i][j] = cif backtrack(board, i, j+1):return Trueboard[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 Falseif board[i][col] == c:return Falseif board[(row//3)*3 + i // 3][(col//3)*3 + i % 3] == c:return Falsereturn 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
- 11
- 21
- 1211
- 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 = 0start = 0while pos < len(prev):while pos < len(prev) and prev[pos] == prev[start]:pos += 1cur += str(pos - start) + prev[start]start = posprev = curreturn 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])returnif c < target:backtrack(i, curr+[c], target-c)if c > target:returnbacktrack(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]:continueif c == target:result.append(curr + [c])returnif c < target:backtrack(i+1, curr+[c], target-c)if c > target:returnbacktrack(0, [], target)return result
解题思路:本题是上一题的变体,与上一题对比,主要差别为candidates数组,上一题的数组中数字都不重复,但每个数都可以反复使用多次。本题的数组中可能有重复的数字,但数组中的每个元素只能用一次。注意,如果数组中有多个元素的数值相等,则它们分别都可以在每种组合中使用一次。此外,数组的长度、每个元素的范围、target的范围不一样,不过这不影响解题思路。
求解方法还是使用回溯法,代码也跟上一题基本相同,根据题目的条件,在回溯函数中做相应的调整。先将数组排序,因为结果不能保存重复的组合,所以当开始索引与上一次的开始索引相等时直接跳过。因为每个元素只能使用一次,所以递归调用回溯函数时,开始索引递增。其他的部分都一样。
回溯的几道题,可以结合起来一起看,更方便理解求解思路。
相关阅读
【PythonCode】力扣Leetcode31~35题Python版
📢欢迎 点赞👍 收藏⭐ 评论📝 关注❤ 如有错误敬请指正!
☟ 学Python,点击下方名片关注我。☟