基于Python数据结构之递归与回溯搜索

2023-07-31 14:34:03 63

1.递归函数与回溯深搜的基础知识

2.求子集(LeetCode78)

3.求子集2(LeetCode90)

4.组合数之和(LeetCode39，40)

5.生成括号(LeetCode22)

6.N皇后(LeetCode51，52)

7.火柴棍摆正方形(LeetCode473)

1.递归函数与回溯深搜的基础知识

递归是指在函数内部调用自身本身的方法。能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

2.求子集(LeetCode78Subsets)

2.1题目

Givenasetofdistinctintegers,nums,returnallpossiblesubsets(thepowerset).
Note:Thesolutionsetmustnotcontainduplicatesubsets.

Forexample,
Ifnums=[1,2,3],asolutionis:
[
[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代码

classSolution(object):
defsubsets(self,nums):
"""
:typenums:List[int]
:rtype:List[List[int]]
"""
size=len(nums)
returnself.solve(nums,size)
defsolve(self,nums,n):
ifn==0:
return[[]]
temp=self.solve(nums[:n-1],n-1)
ans=temp[:]
foriintemp:
ans.append(i+[nums[n-1]])
returnans

3.求子集2(LeetCode90SubsetsII)

3.1题目

Givenacollectionofintegersthatmightcontainduplicates,nums,returnallpossiblesubsets(thepowerset).
Note:Thesolutionsetmustnotcontainduplicatesubsets.

Forexample,
Ifnums=[1,2,2],asolutionis:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

3.2思路

在上一题思路的基础上，当nums[i]=nums[i-1]时，添加子集时只需在上一步增加的子集基础上进行添加nums[i]，而不需要对所有子集进行添加nums[i]。故在递归返回结果时，返回两个结果，一个是所有子集，还有一个是该步骤中添加的子集的集合。

3.3代码

classSolution(object):
defsubsetsWithDup(self,nums):
"""
:typenums:List[int]
:rtype:List[List[int]]
"""
nums.sort()
size=len(nums)
returnself.solve(nums,size)[0]


defsolve(self,nums,n):
ifn==0:
return[[]],[[]]
ifn==1:
return[[],[nums[n-1]]],[[nums[n-1]]]
temp=self.solve(nums[:n-1],n-1)
ans=temp[0][:]
l=len(ans)
ifnums[n-1]==nums[n-2]:
foriintemp[1]:
ans.append(i+[nums[n-1]])
else:
foriintemp[0]:
ans.append(i+[nums[n-1]])
returnans,ans[l:]

4.组合数之和(LeetCode39，40)

4.1题目

LeetCode39CombinationSum

Givenasetofcandidatenumbers(C)(withoutduplicates)andatargetnumber(T),findalluniquecombinationsinCwherethecandidatenumberssumstoT.
ThesamerepeatednumbermaybechosenfromCunlimitednumberoftimes.
Note:
Allnumbers(includingtarget)willbepositiveintegers.
Thesolutionsetmustnotcontainduplicatecombinations.
Forexample,givencandidateset[2,3,6,7]andtarget7,
Asolutionsetis:
[
[7],
[2,2,3]
]

LeetCode40CombinationSumII

Givenacollectionofcandidatenumbers(C)andatargetnumber(T),findalluniquecombinationsinCwherethecandidatenumberssumstoT.
EachnumberinCmayonlybeusedonceinthecombination.
Note:
Allnumbers(includingtarget)willbepositiveintegers.
Thesolutionsetmustnotcontainduplicatecombinations.
Forexample,givencandidateset[10,1,2,7,6,1,5]andtarget8,
Asolutionsetis:
[
[1,7],
[1,2,5],
[2,6],
[1,1,6]
]

4.2思路

LeetCode39CombinationSum

（1）对给定的数字集合进行排序

（2）target=T，从数组中找一个数n，target=T-n，如果target=0，则寻找成功添加结果，如果taget比候选数字中的最小值还小，则寻找失败，不添加

（3）注意：按从小到大的顺序进行查找，如果某数已找到，则在找下一个时，不包括该数

LeetCode40CombinationSumII

该题与上一题相比，区别在于，给定的集合列表中数字可能重复，目标集合中的数字只能使用给定集合中的数字，并且每个数字只能使用一次。注意，由于存在重复的数字，故需要保证结果中的路径集合没有重复。所以当出现candidates[i]==candidates[i-1]，跳过。

4.3代码

LeetCode39CombinationSum

classSolution(object):
defcombinationSum(self,candidates,target):
"""
:typecandidates:List[int]
:typetarget:int
:rtype:List[List[int]]
"""
candidates.sort()
self.ans=[]
self.solve(candidates,target,0,[])
returnself.ans

defsolve(self,candidates,target,start,path):
iftarget==0:
self.ans.append(path)
return
iftarget<0:
return
size=len(candidates)
foriinrange(start,size):
ifcandidates[i]>target:
return
self.solve(candidates,target-candidates[i],i,path+[candidates[i]])

LeetCode40CombinationSumII

classSolution(object):
defcombinationSum2(self,candidates,target):
"""
:typecandidates:List[int]
:typetarget:int
:rtype:List[List[int]]
"""
candidates.sort()
self.ans=[]
self.solve(candidates,target,0,[])
returnself.ans

defsolve(self,candidates,target,start,path):
iftarget==0:
self.ans.append(path)
return
iftarget<0:
return
size=len(candidates)
foriinrange(start,size):
ifi!=startandcandidates[i]==candidates[i-1]:
continue
self.solve(candidates,target-candidates[i],i+1,path+[candidates[i]])

5.生成括号(LeetCode22GenerateParentheses)

5.1题目

Givennpairsofparentheses,writeafunctiontogenerateallcombinationsofwell-formedparentheses.
Forexample,givenn=3,asolutionsetis:
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

5.2思路

在任意位置，左括号的个数要大于等于右括号的个数，如果左括号的个数有剩余，则+'(‘，递归，如果右括号有剩余，且小于左括号的的个数，则+‘）‘，最后左右括号都不剩则排列结束。

5.3代码

classSolution(object):
defgenerateParenthesis(self,n):
"""
:typen:int
:rtype:List[str]
"""
self.res=[]
self.generateParenthesisIter('',n,n)
returnself.res

defgenerateParenthesisIter(self,mstr,r,l):
ifr==0andl==0:
self.res.append(mstr)
ifl>0:
self.generateParenthesisIter(mstr+'(',r,l-1)
ifr>0andr>l:
self.generateParenthesisIter(mstr+')',r-1,l)

6.N皇后(LeetCode51，52)

6.1题目

LeetCode51N-Queens

Then-queenspuzzleistheproblemofplacingnqueensonann×nchessboardsuchthatnotwoqueensattackeachother.
Givenanintegern,returnalldistinctsolutionstothen-queenspuzzle.
Eachsolutioncontainsadistinctboardconfigurationofthen-queens'placement,where‘Q'and‘.'bothindicateaqueenandanemptyspacerespectively.
Forexample,
Thereexisttwodistinctsolutionstothe4-queenspuzzle:
[
[“.Q..”,//Solution1
“…Q”,
“Q…”,
“..Q.”],

[“..Q.”,//Solution2
“Q…”,
“…Q”,
“.Q..”]
]

LeetCode52N-QueensII

FollowupforN-Queensproblem.
Now,insteadoutputtingboardconfigurations,returnthetotalnumberofdistinctsolutions.

6.2思路

LeetCode51N-Queens

n*n的板上放置n个皇后，n个皇后不能发生攻击，即行/列/斜没有其他皇后，要求给出所有解决方案。每次在棋盘上的当前位置放置一个皇后，当不与前面行的皇后发生冲突时，则可以递归处理下面行的皇后。因为有n行n列，n个皇后，故每行可以放一个皇后，每一列也只能放置一个皇后。通过检查第k个皇后能否被放置在第j列进行判断（不与其他皇后在同行，同列，同斜行）。使用一个长度为n的列表记录第k行皇后放置的列位置。

LeetCode52N-QueensII

和上一题思路一样，返回结果的长度即可

6.3代码

LeetCode51N-Queens

classSolution(object):
defsolveNQueens(self,n):
"""
:typen:int
:rtype:List[List[str]]
"""
self.ans=[]
self.board=[-1foriinrange(n)]
self.dfs(0,[],n)
returnself.ans
defisQueen(self,krow,jcolumn):
foriinrange(krow):
ifself.board[i]==jcolumnorabs(krow-i)==abs(self.board[i]-jcolumn):
returnFalse
returnTrue

defdfs(self,krow,rowlist,n):
ifkrow==n:
self.ans.append(rowlist)
foriinrange(n):
ifself.isQueen(krow,i):
self.board[krow]=i
self.dfs(krow+1,rowlist+['.'*i+'Q'+'.'*(n-i-1)],n)

LeetCode52N-QueensII

classSolution(object):
deftotalNQueens(self,n):
"""
:typen:int
:rtype:int
"""
self.ans=[]
self.board=[-1foriinrange(n)]
self.dfs(0,[],n)
returnlen(self.ans)
defisQueen(self,krow,jcolumn):
foriinrange(krow):
ifself.board[i]==jcolumnorabs(krow-i)==abs(self.board[i]-jcolumn):
returnFalse
returnTrue

defdfs(self,krow,rowlist,n):
ifkrow==n:
self.ans.append(rowlist)
foriinrange(n):
ifself.isQueen(krow,i):
self.board[krow]=i
self.dfs(krow+1,rowlist+['.'*i+'Q'+'.'*(n-i-1)],n)

7.火柴棍摆正方形(LeetCode473MatchstickstoSquare)

7.1题目

RememberthestoryofLittleMatchGirl?Bynow,youknowexactlywhatmatchsticksthelittlematchgirlhas,pleasefindoutawayyoucanmakeonesquarebyusingupallthosematchsticks.Youshouldnotbreakanystick,butyoucanlinkthemup,andeachmatchstickmustbeusedexactlyonetime.

Yourinputwillbeseveralmatchsticksthegirlhas,representedwiththeirsticklength.Youroutputwilleitherbetrueorfalse,torepresentwhetheryoucouldmakeonesquareusingallthematchsticksthelittlematchgirlhas.

Example1:
Input:[1,1,2,2,2]
Output:true

Explanation:Youcanformasquarewithlength2,onesideofthesquarecametwostickswithlength1.
Example2:
Input:[3,3,3,3,4]
Output:false

Explanation:Youcannotfindawaytoformasquarewithallthematchsticks.

7.2思路

根据火柴棒的总长度，求正方形的变长，若变长不为整数，则直接判断为False。

先将nums按从大到小的顺序排序，used为和nums等长的列表，用于记录第i位的元素是否被用过。

使用递归判断从第i位元素起始，能否找到这样的组合满足其长度之和等于正方形的边长。

（1）若满足初始条件，则返回结果（TrueorFalse）

（2）若不满足条件，则进行递归，在剩下的元素中进行选择，看有没有满足情况的，如果没有满足情况的，used对应位置改为False，结果返回False

（3）对nums中的每个元素进行遍历，看能否满足nums中的每个火柴棒都能找到对应边的组合，其长度和等于正方形边长。

7.3代码

classSolution(object):
defmakesquare(self,nums):
"""
:typenums:List[int]
:rtype:bool
"""
total=sum(nums)
iftotal%4!=0orlen(nums)<4:returnFalse
size=total/4
nums.sort(reverse=True)
used=[False]*len(nums)
defdfs(i,expect):
ifi>=len(nums):returnexpect%size==0
ifused[i]:returndfs(i+1,expect)
used[i]=True
ifnums[i]==expect:returnTrue
ifnums[i]
以上这篇基于Python数据结构之递归与回溯搜索就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

基于Python数据结构之递归与回溯搜索

热门推荐

随机推荐