回溯算法思路总结
程序员文章站
2022-05-20 22:51:39
...
注意点
- 定义清楚递归函数函数的作用,及需要的参数,参数一般有(要搜索的对象,当前访问位置index,当前已有的一个中间结果,总的结果res,访问标记变量visited)
- 递归调用函数后,记得回退,把当前值从当前结果中弹出,把参数重新置为未访问。
- 递归函数的结束条件是,当前结果的长度等于要求的长度,或当前访问位置等于遍历对象的长度(其实就是越界一位,说明遍历完成),把当前结果加入总结果列表后返回。
数字对应字母的组合
s保存从digits[0–index-1]能得到的一个字符串,即树形结构的一条路径
def find(self, index, digits, s, res):
if index == len(digits):
res.append(s)
return res
dic = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
c = digits[index]
letters = dic[c]
for i in letters: #对当前数字对应的3个字母向后递归调用
res = self.find(index+1,digits,s+i,res)
return res
排列
p中保存了一个有index个元素的排列,向这个排列的末尾加入第index+1个元素
def find(self, nums, index, p, res,used):
if index == len(nums):
res.append(p[:])
return res
for i,n in enumerate(nums): #每次都对除了取过的所有元素递归调用
if used[i] == 0:
p.append(n)
used[i] = 1
res = self.find(nums,index+1,p,res,used)
p.pop(-1)
used[i] = 0
return res
组合
递归函数的作用是求解C(n,k),当前已经找到的组合存储在c中,从start开始取新的元素。
def find(self, n, k, start, c, res):
if len(c)==k:
res.append(c[:])
return res
for i in range(start,n+1): # 对当前位之后的所有数字递归调用,避免重复
c.append(i)
res = self.find(n,k,i+1,c,res)
c.pop(-1) # 回到上一步
return res
二维数组搜索,判断是否存在指定路径
递归函数的作用从当前位置开始board[startx][starty]寻找word[index:],结束条件是index取到最后一位时,当前位置的值等于要找的字母,返回true;递归过程要先判断当前位置的值是否等于要找的index位置的值,如果是再递归调用上下左右寻找下一个元素,否则直接返回false。
def find(self, board, word, index, startx, starty, visited):
m = len(board)
n = len(board[0])
d = [[1,0],[0,1],[-1,0],[0,-1]]
if index == len(word)-1:
return board[startx][starty] == word[index]
if board[startx][starty] == word[index]:
visited[startx][starty] = 1
for i in range(4): #对上下左右递归
x = startx + d[i][0]
y = starty + d[i][1]
if self.inarea(x,y,m,n)==True and visited[x][y]==0 and self.find(board, word, index+1, x, y, visited) == True: # 边界不溢出,未访问过,下一步能找到
return True
visited[startx][starty] = 0
return False
岛判断
递归函数的作用是把和当前陆地相邻的陆地都标为false。
def dfs(self,grid,x,y,visited):
m = len(grid)
n = len(grid[0])
d = [[0,1],[1,0],[-1,0],[0,-1]]
visited[x][y] = 1
for i in range(4): #也是对上下左右递归
newx = x + d[i][0]
newy = y + d[i][1]
if self.inarea(newx,newy,m,n) and visited[newx][newy] == 0 and grid[newx][newy] == '1':
self.dfs(grid,newx,newy,visited)
return
八皇后
递归函数的作用是尝试摆放第index行的皇后的位置
def find(self,n,index,row,res,col,diag1,diag2):
if index == n:
res.append(row[:])
return res
for i in range(n): #第i列,递归每一列
if col[i] == 0 and diag1[i+index] == 0 and diag2[i-index+n-1] == 0: # 可以放,没冲突
col[i] = 1
diag1[i+index] = 1
diag2[i-index+n-1] = 1
row.append(i)
res = self.find(n,index+1,row,res,col,diag1,diag2)
row.pop(-1)
col[i] = 0
diag1[i+index] = 0
diag2[i-index+n-1] = 0
return res