欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

回溯算法思路总结

程序员文章站 2022-05-20 22:51:39
...

注意点

  1. 定义清楚递归函数函数的作用,及需要的参数,参数一般有(要搜索的对象,当前访问位置index,当前已有的一个中间结果,总的结果res,访问标记变量visited)
  2. 递归调用函数后,记得回退,把当前值从当前结果中弹出,把参数重新置为未访问。
  3. 递归函数的结束条件是,当前结果的长度等于要求的长度,或当前访问位置等于遍历对象的长度(其实就是越界一位,说明遍历完成),把当前结果加入总结果列表后返回。

数字对应字母的组合

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
相关标签: 回溯