目录
1. 递归函数与回溯深搜的基础知识
2. 求子集 (LeetCode 78)
3. 求子集2 (LeetCode 90)
4. 组合数之和(LeetCode 39,40)
5. 生成括号(LeetCode 22)
6. N皇后(LeetCode 51,52)
7. 火柴棍摆正方形(LeetCode 473)
1. 递归函数与回溯深搜的基础知识
递归是指在函数内部调用自身本身的方法。能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。
回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
2. 求子集 (LeetCode 78 Subsets)
2.1题目
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
2.2思路
初始化,[ ]的子集为[ [ ] ]
nums[ : n]的子集为所有nums[ : n-1]的子集 加上所有nums[ : n-1]的子集+元素nums[n-1]
2.3代码
class Solution(object): def subsets(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ size = len(nums) return self.solve(nums, size) def solve(self, nums, n): if n == 0: return [[]] temp = self.solve(nums[:n-1], n-1) ans = temp[:] for i in temp: ans.append(i + [nums[n-1]]) return ans
3. 求子集2 (LeetCode 90 Subsets II)
3.1题目
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
3.2思路
在上一题思路的基础上,当nums[i]=nums[i-1]时,添加子集时只需在上一步增加的子集基础上进行添加nums[i],而不需要对所有子集进行添加nums[i]。故在递归返回结果时,返回两个结果,一个是所有子集,还有一个是该步骤中添加的子集的集合。
3.3代码
class Solution(object): def subsetsWithDup(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ nums.sort() size = len(nums) return self.solve(nums, size)[0] def solve(self, nums, n): if n == 0: return [[]],[[]] if n == 1: return [[],[nums[n-1]]],[[nums[n-1]]] temp = self.solve(nums[:n-1], n-1) ans = temp[0][:] l = len(ans) if nums[n-1] == nums[n-2]: for i in temp[1]: ans.append(i + [nums[n-1]]) else: for i in temp[0]: ans.append(i + [nums[n-1]]) return ans,ans[l:]
4. 组合数之和(LeetCode 39,40 )
4.1题目
LeetCode 39 Combination Sum
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]
LeetCode 40 Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
4.2思路
LeetCode 39 Combination Sum
(1)对给定的数字集合进行排序
(2)target=T,从数组中找一个数n,target= T-n,如果target= 0,则寻找成功添加结果,如果taget比候选数字中的最小值还小,则寻找失败,不添加
(3)注意:按从小到大的顺序进行查找,如果某数已找到,则在找下一个时,不包括该数
LeetCode 40 Combination Sum II
该题与上一题相比,区别在于,给定的集合列表中数字可能重复,目标集合中的数字只能使用给定集合中的数字,并且每个数字只能使用一次。注意,由于存在重复的数字,故需要保证结果中的路径集合没有重复。所以当出现candidates[i]==candidates[i-1],跳过。
4.3代码
LeetCode 39 Combination Sum
class Solution(object): def combinationSum(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ candidates.sort() self.ans = [] self.solve(candidates, target, 0 ,[]) return self.ans def solve(self, candidates, target, start, path): if target == 0: self.ans.append(path) return if target < 0: return size = len(candidates) for i in range(start, size): if candidates[i] > target: return self.solve(candidates, target - candidates[i], i, path + [candidates[i]])
LeetCode 40 Combination Sum II
class Solution(object): def combinationSum2(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ candidates.sort() self.ans = [] self.solve(candidates, target, 0, []) return self.ans def solve(self, candidates, target, start, path): if target == 0: self.ans.append(path) return if target < 0: return size = len(candidates) for i in range(start, size): if i != start and candidates[i] == candidates[i-1]: continue self.solve(candidates, target - candidates[i], i + 1, path + [candidates[i]])
5. 生成括号(LeetCode 22 Generate Parentheses)
5.1题目
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]
5.2思路
在任意位置,左括号的个数要大于等于右括号的个数,如果左括号的个数有剩余,则+'(‘,递归,如果右括号有剩余,且小于左括号的的个数,则 +‘)‘,最后左右括号都不剩则排列结束。
5.3代码
class Solution(object): def generateParenthesis(self, n): """ :type n: int :rtype: List[str] """ self.res = [] self.generateParenthesisIter('',n, n) return self.res def generateParenthesisIter(self, mstr, r, l): if r == 0 and l ==0: self.res.append(mstr) if l > 0: self.generateParenthesisIter(mstr+'(', r, l-1) if r > 0 and r > l: self.generateParenthesisIter(mstr+')', r-1, l)
6. N皇后(LeetCode 51 ,52)
6.1题目
LeetCode 51 N-Queens
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where ‘Q' and ‘.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[
[“.Q..”, // Solution 1
“…Q”,
“Q…”,
“..Q.”],[“..Q.”, // Solution 2
“Q…”,
“…Q”,
“.Q..”]
]
LeetCode 52 N-Queens II
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
6.2思路
LeetCode 51 N-Queens
n*n的板上放置n个皇后,n个皇后不能发生攻击,即行/列/斜没有其他皇后,要求给出所有解决方案。每次在棋盘上的当前位置放置一个皇后,当不与前面行的皇后发生冲突时,则可以递归处理下面行的皇后。因为有n行n列,n个皇后,故每行可以放一个皇后,每一列也只能放置一个皇后。通过检查第k个皇后能否被放置在第j列进行判断(不与其他皇后在同行,同列,同斜行)。使用一个长度为n的列表记录第k行皇后放置的列位置。
LeetCode 52 N-Queens II
和上一题思路一样,返回结果的长度即可
6.3代码
LeetCode 51 N-Queens
class Solution(object): def solveNQueens(self, n): """ :type n: int :rtype: List[List[str]] """ self.ans = [] self.board = [-1 for i in range(n)] self.dfs(0, [], n) return self.ans def isQueen(self, krow, jcolumn): for i in range(krow): if self.board[i] == jcolumn or abs(krow-i) == abs(self.board[i] - jcolumn): return False return True def dfs(self, krow, rowlist, n): if krow == n: self.ans.append(rowlist) for i in range(n): if self.isQueen(krow,i): self.board[krow] = i self.dfs(krow + 1,rowlist + ['.' * i + 'Q' + '.' * (n-i-1)],n)
LeetCode 52 N-Queens II
class Solution(object): def totalNQueens(self, n): """ :type n: int :rtype: int """ self.ans = [] self.board = [-1 for i in range(n)] self.dfs(0, [], n) return len(self.ans) def isQueen(self, krow, jcolumn): for i in range(krow): if self.board[i] == jcolumn or abs(krow-i) == abs(self.board[i] - jcolumn): return False return True def dfs(self, krow, rowlist, n): if krow == n: self.ans.append(rowlist) for i in range(n): if self.isQueen(krow,i): self.board[krow] = i self.dfs(krow + 1,rowlist + ['.' * i + 'Q' + '.' * (n-i-1)],n)
7. 火柴棍摆正方形(LeetCode 473 Matchsticks to Square)
7.1题目
Remember the story of Little Match Girl"htmlcode">
class Solution(object): def makesquare(self, nums): """ :type nums: List[int] :rtype: bool """ total = sum(nums) if total%4 != 0 or len(nums)<4: return False size = total/4 nums.sort(reverse=True) used = [False]*len(nums) def dfs(i, expect): if i >= len(nums): return expect%size == 0 if used[i]: return dfs(i+1, expect) used[i] = True if nums[i] == expect: return True if nums[i] < expect: expect -= nums[i] available = [j for j in range(i+1, len(nums)) if not used[j]] for x in available: if dfs(x, expect): return True used[i] = False return False for i in range(len(nums)): if not dfs(i, size): return False return True以上这篇基于Python数据结构之递归与回溯搜索就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持。
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
更新日志
- 凤飞飞《我们的主题曲》飞跃制作[正版原抓WAV+CUE]
- 刘嘉亮《亮情歌2》[WAV+CUE][1G]
- 红馆40·谭咏麟《歌者恋歌浓情30年演唱会》3CD[低速原抓WAV+CUE][1.8G]
- 刘纬武《睡眠宝宝竖琴童谣 吉卜力工作室 白噪音安抚》[320K/MP3][193.25MB]
- 【轻音乐】曼托凡尼乐团《精选辑》2CD.1998[FLAC+CUE整轨]
- 邝美云《心中有爱》1989年香港DMIJP版1MTO东芝首版[WAV+CUE]
- 群星《情叹-发烧女声DSD》天籁女声发烧碟[WAV+CUE]
- 刘纬武《睡眠宝宝竖琴童谣 吉卜力工作室 白噪音安抚》[FLAC/分轨][748.03MB]
- 理想混蛋《Origin Sessions》[320K/MP3][37.47MB]
- 公馆青少年《我其实一点都不酷》[320K/MP3][78.78MB]
- 群星《情叹-发烧男声DSD》最值得珍藏的完美男声[WAV+CUE]
- 群星《国韵飘香·贵妃醉酒HQCD黑胶王》2CD[WAV]
- 卫兰《DAUGHTER》【低速原抓WAV+CUE】
- 公馆青少年《我其实一点都不酷》[FLAC/分轨][398.22MB]
- ZWEI《迟暮的花 (Explicit)》[320K/MP3][57.16MB]