Day 31 卡玛笔记

这是基于代码随想录的每日打卡

491. 非递减子序列

给你一个整数数组 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]]

---

回溯法

class Solution:def __init__(self):self.res=[]self.path=[]def traversal(self,nums,startIndex):if len(self.path)>=2:self.res.append(self.path[:])if startIndex==len(nums):return# 本层的集合，用来去重uset=set()for i in range(startIndex,len(nums)):if self.path and nums[i]<self.path[-1] or nums[i] in uset:continueself.path.append(nums[i])uset.add(nums[i])   # 记录用过的元素self.traversal(nums,i+1)self.path.pop()def findSubsequences(self, nums: List[int]) -> List[List[int]]:self.traversal(nums,0)return self.res

运行结果

---

46. 全排列

给定一个不含重复数字的数组 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]]

---

回溯法

class Solution:def __init__(self):self.res=[]self.path=[]def traversal(self,nums):if len(self.path)==len(nums):self.res.append(self.path[:])for i in range(len(nums)):if self.path and nums[i] in self.path:continueself.path.append(nums[i])self.traversal(nums)self.path.pop()def permute(self, nums: List[int]) -> List[List[int]]:self.traversal(nums)return self.res

运行结果

---

47. 全排列 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]]

---

回溯法

class Solution:def __init__(self):self.res=[]self.path=[]def traversal(self,nums,used):if len(self.path)==len(nums):self.res.append(self.path[:])for i in range(len(nums)):# 树层上去重if i>0 and nums[i]==nums[i-1] and used[i-1]==False:continue# 树枝上去重if used[i]:continueself.path.append(nums[i])used[i]=Trueself.traversal(nums,used)self.path.pop()used[i]=Falsedef permuteUnique(self, nums: List[int]) -> List[List[int]]:nums.sort()self.traversal(nums,[False]*len(nums))return self.res

运行结果

---

51. 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"]]

---

回溯法

class Solution:def __init__(self):self.res=[]def traversal(self,row,n,chessboard):# 终止条件if row==n:ans=[''.join(i) for i in chessboard]self.res.append(ans)return# 单层逻辑for i in range(n):if self.isValid(chessboard,row,i):chessboard[row][i]='Q'row+=1self.traversal(row,n,chessboard)# 回溯row-=1chessboard[row][i]='.'else:continuedef isValid(self,chessboard,row,col):# 查看列是否存在皇后for i in range(row):if chessboard[i][col]!='.':return False# 查看左上角是否存在皇后row1=row-1col1=col-1while row1>=0 and col1>=0:if chessboard[row1][col1]!='.':return Falserow1-=1col1-=1# 查看右上角是否存在皇后row2=row-1col2=col+1while row2>=0 and col2<len(chessboard):if chessboard[row2][col2]!='.':return Falserow2-=1col2+=1# 所有都符合，返回Truereturn Truedef solveNQueens(self, n: int) -> List[List[str]]:chessboard = [['.' for _ in range(n)] for _ in range(n)]self.traversal(0,n,chessboard)return self.res

运行结果