本文主要是介绍[Leetcode] 每日两题 51 100 -day99 重温回溯算法(2)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

重温回溯算法（2）

续 [Leetcode] 每日两题 46 112 -day98重温回溯算法（1）

回溯算法的思路就是把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。本质上还是暴力枚举。使用的思想和DFS类似。

详细描述 ：

回溯法按深度优先策略搜索问题的解空间树。

首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。

如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。

回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类：1. 使用约束函数，剪去不满足约束条件的路径；2.使用限界函数，剪去不能得到最优解的路径。

51. N 皇后

对于棋盘格 的排列问题，可以先转化为1-n 做排列，就相当于 从第一行开始，选第几个位置放置象棋，这样排列完成就发现行与列已经完全区别开。这个时候只需要在进行排列的过程中加入斜线判断，也就是在新放置的这一行对之前所有已经放置的刚进行是否在一条斜线上的判断。

最后转换为答案的输出格式。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:

        res =[]
        def dfs(lis):
            if len(lis) ==n:
                res.append(lis)
                return
            for i in range(n):
                tmp = lis.copy()
                if i not in tmp:
                    flag = 1
                    for j in range(len(tmp)):
                        if abs(len(tmp)-j) == abs(i -tmp[j]) :   # 判断是否在一条斜线上
                            flag = 0
                            break
                    if flag:
                        tmp.append(i)
                        dfs(tmp)
        
        dfs([])
        ret =[]
        for one in res:  
            ret.append( ["."*i + "Q" + "."*(n-i-1) for i in one])
      
        return ret 

100. 相同的树

使用回溯思想来做这个题就显得十分简单了，

对于两个需要判断的树，判断完当前节点相等之后还需要判断其左右子树， 可以发现又变成了分别判断两个子树是否相等，使用递归。

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:

        if not p and not q:
            return True
        if p and q:
            if p.val == q.val:
                l = self.isSameTree(p.left,q.left)
                r = self.isSameTree(p.right,q.right)
                return l and r
        
        return False

这篇关于[Leetcode] 每日两题 51 100 -day99 重温回溯算法(2)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！