回溯算法经典面试题

这篇具有很好参考价值的文章主要介绍了回溯算法经典面试题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

回溯算法经典面试题
⭐️前言⭐️

本文汇总了常见的回溯算法题目,并将框架来进行运用,相信通过这篇文章,读者能够对回溯算法有一定了解。

🍉欢迎点赞 👍 收藏留言评论 📝私信必回哟😁

🍉博主将持续更新学习记录收获,友友们有任何问题可以在评论区留言

🍉博客中涉及源码及博主日常练习代码均已上传GitHub


回溯算法经典面试题

🍅1.回溯算法框架

解决一个回溯问题,实际上就是一个决策树的遍历过程,站在回溯树的一个节点上,你只需要考虑3个问题:
1、路径:也就是已经做出的选择。
2、选择列表:也就是你当前可以做的选择。
3、结束条件:也就是到达决策树底层,无法再做选择的条件。
接下来通过全排列N皇后的经典回溯问题来应用理解这个框架。

代码框架如下:

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

核心是for循环里面的递归,在递归调用之前「做选择」,在递归调用之后「撤销选择」。

🍅2.经典题目练习

2.1 全排列问题

https://leetcode.cn/problems/permutations/
回溯算法经典面试题
n个不重复的数,全排列共有n!个。
下图中[3]就是路径,记录你已经做过的选择;[1,2]就是「选择列表」,表示你当前可以做出的选择;「结束条件」就是遍历到树的底层叶子节点,这里也就是选择列表为空的时候。
回溯算法经典面试题
我们定义的backtrack函数就像一个指针,在这棵树上游走,同时要正确维护每个节点的属性,每当走到树的叶子节点,其路径就是一个全排列。

代码实现:

class Solution {
    List<List<Integer>> res=new LinkedList<>();
    // 主函数,输入一组不重复的数字,返回他们的全排列。
    public List<List<Integer>> permute(int[] nums) {
    	//记录路径
        LinkedList<Integer> track=new LinkedList<>();
        //路径中的元素会被标记为true,避免重复使用
        boolean[] used=new boolean[nums.length];
        backtrack(nums,track,used);
        return res;
    }
    // 路径记录在track中
    // 选择列表:nums中不存在于track的那些元素
    // 结束条件:nums中的元素全都在track中出现
    void backtrack(int[] nums,LinkedList<Integer> track,boolean[] used) {
    	//触发结束条件
        if(track.size()==nums.length) {
            res.add(new LinkedList(track));
            return;
        }
        for(int i=0;i<nums.length;i++) {
        	// 排除不合法的选择
            if(used[i]) continue;
            // 做选择
            track.add(nums[i]);
            used[i]=true;
            backtrack(nums,track,used);
            // 取消选择
            used[i]=false;
            track.removeLast();
        }
    }
}

https://leetcode.cn/problems/permutations-ii/description/
回溯算法经典面试题
注意:
该题目与上题相比,存在了重复的元素,所以在保存结果的时候,不需要保存数字结果相同的结果,那么这个时候就需要我们剪枝,比如[1,2,2 '] 路径记录下来以后,路径[1,2 ',2]就不会被记录。

如果涉及考虑重复元素,或者大小比较的情况,首先应该对列表进行排序,然后再去进一步记录结果。

那么针对重复元素造成结果相同的这部分剪枝的条件为:和前一个元素值相同(此处隐含这个元素的index>0),并且前一个元素还没有被使用过。

比如[1,2,2 '] 路径记录下来以后,路径[1,2 ‘,2]首先记录2’,在数组中的排序为1,2,2’,因为2’与数组中前一个数值相同,并且没被用过,所以该路径直接被剪枝。

即代码:

if(i>0&&nums[i-1]==nums[i]&&!used[i-1]) continue;

总代码实现:

class Solution {
    List<List<Integer>> res=new LinkedList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        LinkedList<Integer> track=new LinkedList<>();
        boolean[] used=new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums,track,used);
        return res;
    }
    void backtrack(int[] nums,LinkedList<Integer> track,boolean[] used) {
        if(track.size()==nums.length) {
            res.add(new LinkedList(track));
            return;
        }
        for(int i=0;i<nums.length;i++) {
            if(used[i]) continue;
            if(i>0&&nums[i-1]==nums[i]&&!used[i-1]) continue;
            track.add(nums[i]);
            used[i]=true;
            backtrack(nums,track,used);
            used[i]=false;
            track.removeLast();
        }
    }
}

2.2 N皇后问题

回溯算法经典面试题
题解思路:
该题其实也和上边的全排列相似,也是回溯问题,决策树的每一层表示棋盘上的每一行;每个节点可以做出的选择是,在该行的任意一列放置一个皇后。
剪枝的条件是:
判断是否符合规则,该位置的上方、左上方和右上方是否有皇后。
代码实现:

class Solution {
    List<List<String>> res = new ArrayList<>();

    /* 输入棋盘边长 n,返回所有合法的放置 */
    public List<List<String>> solveNQueens(int n) {
        // '.' 表示空,'Q' 表示皇后,初始化空棋盘
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append('.');
            }
            board.add(sb.toString());
        }
        backtrack(board, 0);
        return res;
    }

    // 路径:board 中小于 row 的那些行都已经成功放置了皇后
    // 选择列表:第 row 行的所有列都是放置皇后的选择
    // 结束条件:row 超过 board 的最后一行
    void backtrack(List<String> board, int row) {
        // 触发结束条件
        if (row == board.size()) {
            res.add(new ArrayList<>(board));
            return;
        }
        
        int n = board.get(row).length();
        for (int col = 0; col < n; col++) {
            // 排除不合法选择
            if (!isValid(board, row, col)) {
                continue;
            }
            // 做选择
            StringBuilder sb = new StringBuilder(board.get(row));
            sb.setCharAt(col, 'Q');
            board.set(row, sb.toString());

            // 进入下一行决策
            backtrack(board, row + 1);
            // 撤销选择
            sb.setCharAt(col, '.');
            board.set(row, sb.toString());
        }
    }

    /* 是否可以在 board[row][col] 放置皇后? */
    boolean isValid(List<String> board, int row, int col) {
        int n = board.size();

        /* 检查上方是否有皇后互相冲突 */
          for(int i=0;i<row;i++) {
            if(board.get(i).charAt(col)=='Q') return false;
        }

        /* 检查右上方是否有皇后互相冲突 */
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++) {
            if(board.get(i).charAt(j)=='Q') return false;
        }

        /* 检查左上方是否有皇后互相冲突 */
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--) {
            if(board.get(i).charAt(j)=='Q') return false;
        }

        return true;
    }
}


回溯算法经典面试题
该题目即在上边题目的代码上做出简单变动即可ac,就是不用在记录路径了,定义变量res记录符合规则的情况数,如果row到达底层,就让res++,最后返回res即可。

代码实现:

class Solution {
    int res=0;
    public int totalNQueens(int n) {
        List<String> board=new ArrayList<>();
        for(int i=0;i<n;i++) {
            StringBuffer sb=new StringBuffer();
            for(int j=0;j<n;j++) {
                sb.append(".");
            }
            board.add(sb.toString());
        }
        backtrack(board,0);
        return res;
    }
    void backtrack(List<String> board,int row) {
        if(row==board.size()) {
            res++;
            return;
        }
        int n=board.get(row).length();
        for(int col=0;col<n;col++) {
            if(!isValid(board,row,col)) continue;
            StringBuffer sb=new StringBuffer(board.get(row));
            sb.setCharAt(col,'Q');
            board.set(row,sb.toString());
            backtrack(board,row+1);
            sb.setCharAt(col,'.');
            board.set(row,sb.toString());
        }
    }
    boolean isValid(List<String> board,int row,int col) {
        int n=board.size();
        for(int i=0;i<row;i++) {
            if(board.get(i).charAt(col)=='Q') return false;
        }
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++) {
            if(board.get(i).charAt(j)=='Q') return false;
        }
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--) {
            if(board.get(i).charAt(j)=='Q') return false;
        }
        return true;
    }
}

代码实现2:
用一个一维数组记录皇后的状态,数组下标表示第几行,值表示第几列;通过这个一维数组记录情况可以不用恢复状态,因为在递归到不同的分支时,原来的记录可以直接被覆盖修改。

class Solution {
    public int totalNQueens(int n) {
        int[] record=new int[n];
        return process(0,record,n);
    }

    public int process(int i,int[] record,int n) {
        if(i==n) {
            return 1;
        }
        int res=0;
        for(int j=0;j<n;j++) {
            if(isValid(record,i,j)) {
                record[i]=j;
                res+=process(i+1,record,n);
            }
        }
        return res;
    }

    public boolean isValid(int[] record,int i,int j) {
        for(int k=0;k<i;k++) {
            if(record[k]==j||Math.abs(record[k]-j)==Math.abs(i-k)) {
                return false;
            }
        }
        return true;
    }
}

⭐️最后的话⭐️
总结不易,希望uu们不要吝啬你们的👍哟(^U^)ノ~YO!!如有问题,欢迎评论区批评指正😁

回溯算法经典面试题文章来源地址https://www.toymoban.com/news/detail-428843.html

到了这里,关于回溯算法经典面试题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 200个经典面试题(算法思想+数据结构)_1

    1. 爬楼梯 70. Climbing Stairs (Easy) 题目描述:有 N 阶楼梯,每次可以上一阶或者两阶,求有多少种上楼梯的方法。 定义一个数组 dp 存储上楼梯的方法数(为了方便讨论,数组下标从 1 开始),dp[i] 表示走到第 i 个楼梯的方法数目。 第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步

    2024年02月13日
    浏览(45)
  • 力扣第40题 组合总和 || c++ 回溯经典

    40. 组合总和 II 中等 相关标签 数组   回溯 给定一个候选人编号的集合  candidates  和一个目标数  target  ,找出  candidates  中所有可以使数字和为  target  的组合。 candidates  中的每个数字在每个组合中只能使用  一次  。 注意: 解集不能包含重复的组合。  示例 1: 示例

    2024年02月07日
    浏览(41)
  • 经典链表试题(一)

    📘北尘_ :个人主页 🌎个人专栏 :《Linux操作系统》《经典算法试题 》《C++》 《数据结构与算法》 ☀️走在路上,不忘来时的初心 给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。 请你将两个数

    2024年02月08日
    浏览(25)
  • c语言经典测试题2

    1.题1 我们来思考一下它的结果是什么? 我们来分析一下:\\\\是转义为字符\\\'\\\',123表示的是一个八进制,算一个字符,t算一个字符,加上\\0,应该有13个,但是strlen只计算\\0前的字符个数。所以结果应该是12.我们来看看:  2.题2 大家来思考一下结果是什么呢? 我们来分析一下

    2024年02月22日
    浏览(39)
  • C++动态规划经典试题解析之打家劫舍系列

    力扣上有几道与打家劫舍相关的题目,算是学习动态规划时常被提及的经典试题,很有代表性,常在因内大大小小的社区内看到众人对此类问题的讨论。 学习最好的方式便是归纳总结、借鉴消化,基于这个目的,本文对此类问题也做了讲解,在一些优秀思想的基础上添加了个

    2024年02月13日
    浏览(43)
  • 【算法专题】回溯算法

    什么是回溯算法? 回溯算法是⼀种经典的递归算法,通常用于解决组合问题、排列问题和搜索问题等。回溯算法的基本思想:从一个初始状态开始,按照一定的规则向前搜索,当搜索到某个状态无法前进时,回退到前一个状态,再按照其他的规则搜索。回溯算法在搜索过程中

    2024年02月03日
    浏览(47)
  • 回溯算法part06 算法

    今日任务: ● 51. N皇后 ● 37. 解数独 https://leetcode.cn/problems/n-queens/description/ https://leetcode.cn/problems/sudoku-solver/description/

    2024年01月18日
    浏览(29)
  • 初级算法-回溯算法

    主要记录算法和数据结构学习笔记,新的一年更上一层楼! 回溯算法 是递归的副产品,是一种搜索的方式。本质是穷举,可加剪枝操作 可抽象为树形结构,集合大小构成树的宽度,递归的深度,都构成树的深度 1. 组合 :N个数里面按一定规则找出k个数的集合 2. 分割 :一个

    2023年04月27日
    浏览(28)
  • 【算法】回溯算法

    本文参考《代码随想录》 原文笔记链接: https://www.programmercarl.com/ B站视频链接: https://www.bilibili.com/video/BV1cy4y167mM?spm_id_from=333.337.search-card.all.clickvd_source=c2d3149b8b6fdae1d68e10dfaabfb1de 回溯法简单来说就是按照深度优先的顺序,穷举所有可能性的算法,但是回溯算法比暴力穷举法

    2024年02月16日
    浏览(30)
  • 常见的算法技巧——回溯算法

    回溯算法(Backtracking)是一种常用的算法技巧,用于解决组合优化问题或排列问题。回溯算法通过穷举搜索的方式,尝试所有可能的解,并在搜索过程中进行剪枝,以避免无效的搜索路径。剪枝(Pruning)是一种通过提前排除不必要的分支来减少搜索空间的技巧。 确定解空间

    2024年02月13日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包