河南省百城建设提质网站,wordpress 登陆api,深圳专业网站建设企,wordpress调用服务器文件参考文献 代码随想录
一、非递减子序列
给你一个整数数组 nums #xff0c;找出并返回所有该数组中不同的递增子序列#xff0c;递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素#xff0c;如出现两个整数相等#xff0c;也可以视作…
参考文献 代码随想录
一、非递减子序列
给你一个整数数组 nums 找出并返回所有该数组中不同的递增子序列递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素如出现两个整数相等也可以视作递增序列的一种特殊情况。 示例 1
输入nums [4,6,7,7]
输出[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]示例 2
输入nums [4,4,3,2,1]
输出[[4,4]]提示
1 nums.length 15-100 nums[i] 100
问题分析 这里在终止条件的时候不能使用return因为如果你使用了那么后面符合调价的都会被你给pass主要是单层循环的逻辑的去重这里的去重主要是判断每次去的时候是否被使用过如果使用过那么就不用了因为之前已经取过了。
单层搜索逻辑 在图中可以看出同一父节点下的同层上使用过的元素就不能再使用了
class Solution(object):def __init__(self):self.result []def findSubsequences(self, nums)::type nums: List[int]:rtype: List[List[int]]self.backtraking(nums, [], 0)return self.resultdef backtraking(self, nums, li, startIndex):if len(li) 1:self.result.append(li)# 注意这里不要加return要取树上的节点used set()for i in range(startIndex, len(nums)):if len(li) 0 and nums[i] li[-1] or nums[i] in used:continueused.add(nums[i])self.backtraking(nums, li [nums[i]], i 1)
二、全排列
给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1
输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2
输入nums [0,1]
输出[[0,1],[1,0]]示例 3
输入nums [1]
输出[[1]]提示
1 nums.length 6-10 nums[i] 10nums 中的所有整数 互不相同
class Solution(object):def __init__(self):self.result []def permute(self, nums)::type nums: List[int]:rtype: List[List[int]]self.backtraking(nums, [])return self.resultdef backtraking(self, nums, li):if len(li) len(nums):self.result.append(li[:])returnfor i in range(len(nums)):if nums[i] in li: # 为了最后结果没有重复的元素continueself.backtraking(nums, li [nums[i]])
三、全排列 II
给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。 示例 1
输入nums [1,1,2]
输出
[[1,1,2],[1,2,1],[2,1,1]]示例 2
输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]提示
1 nums.length 8-10 nums[i] 10
class Solution(object):def __init__(self):self.result []def permuteUnique(self, nums)::type nums: List[int]:rtype: List[List[int]]nums.sort()self.backtraking(nums, [], [False] * len(nums))return self.resultdef backtraking(self, nums, li, used):if len(li) len(nums):self.result.append(li[:])returnfor i in range(len(nums)):if i 0 and nums[i] nums[i - 1] and used[i - 1] False:continueif used[i]:continueused[i] Trueself.backtraking(nums, li [nums[i]], used)used[i] False拓展
大家发现去重最为关键的代码为
if (i 0 nums[i] nums[i - 1] used[i - 1] false) {continue;
}如果改成 used[i - 1] true 也是正确的!去重代码如下
if (i 0 nums[i] nums[i - 1] used[i - 1] true) {continue;
}这是为什么呢就是上面我刚说的如果要对树层中前一位去重就用used[i - 1] false如果要对树枝前一位去重用used[i - 1] true。
对于排列问题树层上去重和树枝上去重都是可以的但是树层上去重效率更高
这么说是不是有点抽象
来来来我就用输入: [1,1,1] 来举一个例子。
树层上去重(used[i - 1] false)的树形结构如下 树枝上去重used[i - 1] true的树型结构如下 大家应该很清晰的看到树层上对前一位去重非常彻底效率很高树枝上对前一位去重虽然最后可以得到答案但是做了很多无用搜索
四、重新安排行程
给你一份航线列表 tickets 其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK肯尼迪国际机场出发的先生所以该行程必须从 JFK 开始。如果存在多种有效的行程请你按字典排序返回最小的行程组合。
例如行程 [JFK, LGA] 与 [JFK, LGB] 相比就更小排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。 示例 1 输入tickets [[MUC,LHR],[JFK,MUC],[SFO,SJC],[LHR,SFO]]
输出[JFK,MUC,LHR,SFO,SJC]示例 2 输入tickets [[JFK,SFO],[JFK,ATL],[SFO,ATL],[ATL,JFK],[ATL,SFO]]
输出[JFK,ATL,JFK,SFO,ATL,SFO]
解释另一种有效的行程是 [JFK,SFO,ATL,JFK,ATL,SFO] 但是它字典排序更大更靠后。提示
1 tickets.length 300tickets[i].length 2fromi.length 3toi.length 3fromi 和 toi 由大写英文字母组成fromi ! toi
问题分析 这里可以使用深搜首先你要排序按字母排序然后从出发点开始一直往下搜到底最后返回结果即可。
class Solution:def findItinerary(self, tickets: List[List[str]]) - List[str]:self.adj {}# 根据航班每一站的重点字母顺序排序tickets.sort(keylambda x:x[1])# 罗列每一站的下一个可选项for u,v in tickets:if u in self.adj: self.adj[u].append(v)else: self.adj[u] [v]# 从JFK出发self.result []self.dfs(JFK) return self.result[::-1] def dfs(self, s):while s in self.adj and len(self.adj[s]) 0: # 有落脚点len(self.adj[s]) 0# 找到s能到哪里选能到的第一个机场v self.adj[s][0] # 在之后的可选项机场中去掉这个机场防止死循环self.adj[s].pop(0) # 从当前的新出发点开始self.dfs(v) self.result.append(s)
五、N 皇后
按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。 示例 1 输入n 4
输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]
解释如上图所示4 皇后问题存在两个不同的解法。示例 2
输入n 1
输出[[Q]]提示
1 n 9
问题分析 考虑的是如何遍历 二维棋盘之前的做的只是1为的单层处理的是每行的列 然后递归处理的是行那么如何 终止 呢是不是遍历到了最后一行那么就是收集结果的时候为什么 一定是正确的呢需要在单层逻辑里做处理分别处理那为什么不做行的处理因为递归的时候已经处理了行的位置所以我们只需要处理列和左上角和右上角注意边间。
class Solution(object):def __init__(self):self.result []def solveNQueens(self, n)::type n: int:rtype: List[List[str]]chessborad [. * n for _ in range(n)] # 初始化棋盘self.backtracking(n, 0, chessborad)return self.resultdef backtracking(self, n, row, chessborad):if row n: # 说明已经到叶子节点了self.result.append(chessborad[:])returnfor col in range(n):if self.isValid(row, col, chessborad):chessborad[row] chessborad[row][:col] Q chessborad[row][col 1:]self.backtracking(n, row 1, chessborad)chessborad[row] chessborad[row][:col] . chessborad[row][col 1:]def isValid(self, row, col, chessborad):# 检测列for i in range(row):if chessborad[i][col] Q:return False# 检查45度角是否有(左上方)i, j row - 1, col - 1while i 0 and j 0:if chessborad[i][j] Q:return Falsei - 1j - 1# 检测右上方i, j row - 1, col 1while i 0 and j len(chessborad):if chessborad[i][j] Q:return Falsei - 1j 1return True六、解数独
编写一个程序通过填充空格来解决数独问题。
数独的解法需 遵循如下规则
数字 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 9board[i].length 9board[i][j] 是一位数字或者 .题目数据 保证 输入数独仅有一个解
问题分析
本题就不一样了本题中棋盘的每一个位置都要放一个数字而N皇后是一行只放一个皇后并检查数字是否合法解数独的树形结构要比N皇后更宽更深。
因为这个树形结构太大了我抽取一部分如图所示 #回溯三部曲
递归函数以及参数
递归函数的返回值需要是bool类型为什么呢
因为解数独找到一个符合的条件就在树的叶子节点上立刻就返回相当于找从根节点到叶子节点一条唯一路径所以需要使用bool返回值。
代码如下
bool backtracking(vectorvectorchar board)递归终止条件
本题递归不用终止条件解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。
不用终止条件会不会死循环
递归的下一层的棋盘一定比上一层的棋盘多一个数等数填满了棋盘自然就终止填满当然好了说明找到结果了所以不需要终止条件
那么有没有永远填不满的情况呢
这个问题我在递归单层搜索逻辑里再来讲
递归单层搜索逻辑 在树形图中可以看出我们需要的是一个二维的递归 一行一列
一个for循环遍历棋盘的行一个for循环遍历棋盘的列一行一列确定下来之后递归遍历这个位置放9个数字的可能性
代码如下详细看注释
bool backtracking(vectorvectorchar board) {for (int i 0; i board.size(); i) { // 遍历行for (int j 0; j board[0].size(); j) { // 遍历列if (board[i][j] ! .) continue;for (char k 1; k 9; k) { // (i, j) 这个位置放k是否合适if (isValid(i, j, k, board)) {board[i][j] k; // 放置kif (backtracking(board)) return true; // 如果找到合适一组立刻返回board[i][j] .; // 回溯撤销k}}return false; // 9个数都试完了都不行那么就返回false}}return true; // 遍历完没有返回false说明找到了合适棋盘位置了
}注意这里return false的地方这里放return false 是有讲究的。
因为如果一行一列确定下来了这里尝试了9个数都不行说明这个棋盘找不到解决数独问题的解
那么会直接返回 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去
#判断棋盘是否合法
判断棋盘是否合法有如下三个维度
同行是否重复同列是否重复9宫格里是否重复
代码如下
bool isValid(int row, int col, char val, vectorvectorchar board) {for (int i 0; i 9; i) { // 判断行里是否重复if (board[row][i] val) {return false;}}for (int j 0; j 9; j) { // 判断列里是否重复if (board[j][col] val) {return false;}}int startRow (row / 3) * 3;int startCol (col / 3) * 3;for (int i startRow; i startRow 3; i) { // 判断9方格里是否重复for (int j startCol; j startCol 3; j) {if (board[i][j] val ) {return false;}}}return true;
}
class Solution(object):def solveSudoku(self, board)::type board: List[List[str]]:rtype: None Do not return anything, modify board in-place instead.self.barktarking(board)def barktarking(self, board):# 若有解返回True否则返回Falsefor i in range(len(board)):for j in range(len(board[0])):# 若空格内已有数字跳过if board[i][j] ! .: continuefor k in range(1, 10): #在1到9中寻找合适的数字if self.isValid(i, j, k, board):board[i][j] str(k)if self.barktarking(board):return Trueboard[i][j] .return False # 如果无解那么直接返回falsereturn Truedef isValid(self,row ,col ,k ,board):# 判断 同一行是否冲突for i in range(9):if board[row][i] str(k):return False# 判读同一列是否有冲突 for j in range(9):if board[j][col] str(k):return False# 判断同一9规格是否有冲突# 获取坐标 是属于第一个九宫格的开始位置 start_row (row // 3) * 3start_col (col // 3) * 3for i in range(start_row, start_row 3):for j in range(start_col, start_col 3):if board[i][j] str(k):return Falsereturn True
回溯总结
切割问题
在回溯算法分割回文串 (opens new window)中我们开始讲解切割问题虽然最后代码看起来好像是一道模板题但是从分析到学会套用这个模板是比较难的。
我列出如下几个难点
切割问题其实类似组合问题如何模拟那些切割线切割问题中递归如何终止在递归循环中如何截取子串如何判断回文
如果想到了用求解组合问题的思路来解决 切割问题本题就成功一大半了接下来就可以对着模板照葫芦画瓢。
但后序如何模拟切割线如何终止如何截取子串其实都不好想最后判断回文算是最简单的了。
所以本题应该是一个道hard题目了。
除了这些难点本题还有细节例如切割过的地方不能重复切割所以递归函数需要传入i 1。
树形结构如下 去重问题
以上我都是统一使用used数组来去重的其实使用set也可以用来去重
在本周小结回溯算法系列三续集 (opens new window)中给出了子集、组合、排列问题使用set来去重的解法以及具体代码并纠正一些同学的常见错误写法。
同时详细分析了 使用used数组去重 和 使用set去重 两种写法的性能差异
使用set去重的版本相对于used数组的版本效率都要低很多大家在leetcode上提交能明显发现。
原因在回溯算法递增子序列 (opens new window)中也分析过主要是因为程序运行的时候对unordered_set 频繁的insertunordered_set需要做哈希映射也就是把key通过hash function映射为唯一的哈希值相对费时间而且insert的时候其底层的符号表也要做相应的扩充也是费时的。
而使用used数组在时间复杂度上几乎没有额外负担
使用set去重不仅时间复杂度高了空间复杂度也高了在本周小结回溯算法系列三 (opens new window)中分析过组合子集排列问题的空间复杂度都是O(n)但如果使用set去重空间复杂度就变成了O(n^2)因为每一层递归都有一个set集合系统栈空间是n每一个空间都有set集合。
那有同学可能疑惑 用used数组也是占用O(n)的空间啊
used数组可是全局变量每层与每层之间公用一个used数组所以空间复杂度是O(n n)最终空间复杂度还是O(n)。
#重新安排行程图论额外拓展
之前说过有递归的地方就有回溯深度优先搜索也是用递归来实现的所以往往伴随着回溯。
在回溯算法重新安排行程 (opens new window)其实也算是图论里深搜的题目但是我用回溯法的套路来讲解这道题目算是给大家拓展一下思路原来回溯法还可以这么玩
以输入[[JFK, KUL], [JFK, NRT], [NRT, JFK]为例抽象为树形结构如下 本题可以算是一道hard的题目了关于本题的难点我在文中已经详细列出。
如果单纯的回溯搜索深搜并不难难还难在容器的选择和使用上
本题其实是一道深度优先搜索的题目但是我完全使用回溯法的思路来讲解这道题题目算是给大家拓展一下思维方式其实深搜和回溯也是分不开的毕竟最终都是用递归。
#棋盘问题
#N皇后问题
在回溯算法N皇后问题 (opens new window)中终于迎来了传说中的N皇后。
下面我用一个3 * 3 的棋盘将搜索过程抽象为一棵树如图 从图中可以看出二维矩阵中矩阵的高就是这棵树的高度矩阵的宽就是树形结构中每一个节点的宽度。
那么我们用皇后们的约束条件来回溯搜索这棵树只要搜索到了树的叶子节点说明就找到了皇后们的合理位置了。
如果从来没有接触过N皇后问题的同学看着这样的题会感觉无从下手可能知道要用回溯法但也不知道该怎么去搜。
这里我明确给出了棋盘的宽度就是for循环的长度递归的深度就是棋盘的高度这样就可以套进回溯法的模板里了。
相信看完本篇回溯算法N皇后问题 (opens new window)也没那么难了传说已经不是传说了。
#解数独问题
在回溯算法解数独 (opens new window)中要征服回溯法的最后一道山峰。
解数独应该是棋盘很难的题目了比N皇后还要复杂一些但只要理解 “二维递归”这个过程其实发现就没那么难了。
大家已经跟着「代码随想录」刷过了如下回溯法题目例如77.组合组合问题 (opens new window)131.分割回文串分割问题 (opens new window)78.子集子集问题 (opens new window)46.全排列排列问题 (opens new window)以及51.N皇后N皇后问题 (opens new window)其实这些题目都是一维递归。
其中N皇后问题 (opens new window)是因为每一行每一列只放一个皇后只需要一层for循环遍历一行递归来遍历列然后一行一列确定皇后的唯一位置。
本题就不一样了本题中棋盘的每一个位置都要放一个数字并检查数字是否合法解数独的树形结构要比N皇后更宽更深。
因为这个树形结构太大了我抽取一部分如图所示 解数独可以说是非常难的题目了如果还一直停留在一维递归的逻辑中这道题目可以让大家瞬间崩溃。
所以我在回溯算法解数独 (opens new window)中开篇就提到了二维递归这也是我自创词汇希望可以帮助大家理解解数独的搜索过程。
一波分析之后在看代码会发现其实也不难唯一难点就是理解二维递归的思维逻辑。
这样解数独这么难的问题也被我们攻克了。
