【寸铁的刷题笔记】树、回溯、图论、bfs、dfs(四)

这篇具有很好参考价值的文章主要介绍了【寸铁的刷题笔记】树、回溯、图论、bfs、dfs(四)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【寸铁的刷题笔记】树、回溯、图论、bfs、dfs(四)

大家好 我是寸铁👊
金三银四图论基础回溯结合bfsdfs是必考的知识点✨
快跟着寸铁刷起来!面试顺利上岸👋
喜欢的小伙伴可以点点关注 💝


🌞详见如下专栏🌞

🍀🍀🍀寸铁的刷题笔记🍀🍀🍀


17. 电话号码的字母组合

考点

dfs、回溯


代码

class Solution {
    //创建一个列表,用于存储组合的结果
    List<String>list = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        //如果说digits字符串为空或者长度为0
        //则说明没有任何可以组合的字符,直接返回空列表即可。
        if(digits == null || digits.length() == 0)return list;
        //使用数组存储一个映射,也可以使用map<Integer , String>存储
        String[]numString = {
            " ",//下标为0
            " ",//下标为1
            "abc",//2
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
        };
        //递归
        //传入参数: 数字字符串,numString映射数组,当前搜索的层数
        backTracing(digits , numString , 0);
        //返回最后的列表
        return list;
    }
    //用stringbuilder进行拼接
    StringBuilder temp = new StringBuilder();
    public void backTracing(String digits , String[] numString , int num){
        //如果说最后的层数等于数字的长度
        //则说明已经搜索完了,入队即可。
        if(num == digits.length()){
            list.add(temp.toString());
            return;
        }
        //获取数字所对应的映射字符串
        String str = numString[digits.charAt(num) - '0'];
        //进行dfs暴搜
        //枚举第一个数字
        for(int i = 0; i < str.length(); i++){
            //添加到temp中
            temp.append(str.charAt(i));
            //继续向下一层递归
            backTracing(digits , numString , num + 1);
            //恢复现场,向上回溯
            temp.deleteCharAt(temp.length() - 1);//向上回溯
        }
    }
}

77. 组合

考点

dfs、回溯


代码

class Solution {
    List<List<Integer>>result = new ArrayList<>();
    LinkedList<Integer>path = new LinkedList<>();
    //可以删除最后一个元素 removeLast()
    //再转为ArrayList<>()
    public List<List<Integer>> combine(int n, int k) {
        combineHelper(n , k ,1);//确定入参 n表示数字1 - n  k 表示组合的大小
        return result;//返回最终的结果
    }
    public void combineHelper(int n , int k , int startIndex){
        if(path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex; i <= n; i++){
            //添加元素
            path.add(i);
            //递归到下一层 注意: 起始数字从 i + 1开始,确保数字组合不重复。
            //每次递归时,都从上一个数字的下一个数开始,这样就不会导致组合出现重复。
            combineHelper(n , k , i + 1);
            //向上回溯
            path.removeLast();
        }
    }
}

127. 单词接龙

考点

bfs、宽度搜索、哈希表


思路

先用一个Map存储单词列表,后面用于匹配单词使用。
暴力搜索单词长度下的字母每一位的26种可能,再去与单词列表进行匹配,匹配成功则标记该单词已经走过
同时,单词序列的长度(bfs搜索的层数)++,
如何确保转换序列最短?
这里我们是一层层搜索,每一层优先去匹配最后的单词
匹配的上,谁所在的那一层就是最短的序列长度
如果说匹配的上,则直接返回序列长度
如果说匹配不上,则把当前搜索到的节点入队,用于下一层的继续搜索。


代码

class Solution {
    /*
    bfs暴搜
    用一个Map存储单词列表,后面用于匹配单词使用。
    暴力搜索单词长度下的字母每一位的26种可能,再去与单词列表进行匹配,匹配成功则标记该单词已经走过。
    同时,单词序列的长度(bfs搜索的层数)++,单词入队,用于下一轮的搜索。
    最后,判断能否走到最后一个单词,也就是当搜索时匹配到最后一个单词时,搜索停止,返回走过的序列长度。
    如何确保转换序列最短?
    这里我们是一层层搜索,每一层优先去匹配最后单词。
    如果说匹配的上,则返回序列长度。
    如果说匹配不上,则把当前搜索的节点入队,用于下一层的继续搜索。
    */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //如果说开头的单词的长度与最后一个单词的长度不同,则不存在这样的转换序列。
        if(beginWord.length() != endWord.length())return 0;
        int n = beginWord.length();
        //创建一个单词库,用于后面的单词匹配。
        Set<String>wordsLib = new HashSet<>();
        for(String word : wordList){
            wordsLib.add(word);
        }
        //如果说终点单词不在单词库中则不存在这样的转换序列。
        if(!wordsLib.contains(endWord))return 0;

        //宽搜
        //创建标记Set记录已经走过的节点
        Set<String>visited = new HashSet<>();
        visited.add(beginWord);//标记起点节点已经被搜索过
        //维护一个队列,用于宽搜。
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(beginWord , 1)); 
        while(!queue.isEmpty()){
            //弹出当前队列的节点进行宽搜
            Node cur = queue.poll();
            String curWord = cur.word;//记录弹出节点的单词
            int cnt = cur.cnt; //记录弹出节点的单词长度
            //每次弹出一个单词,序列的长度就++
            //因为要往下一层搜索,是一层层搜索,如果最后找到,则返回找到的序列长度即可
            //找不到则返回0 
            cnt++; //bfs搜索的层数(序列长度)加1
            System.out.println(curWord);
            System.out.println(cnt);//a --> c
             //暴力搜索
             //注意:这个搜索的话,是一层层搜。
             //每次搜索时,会优先考虑是否与最后一个单词匹配,确保序列长度是最短的。
             //如果匹配上,则直接返回序列长度即可,此时的序列长度为最短
             //如果没有匹配,则先把这一层搜索到的节点入队,用于下一层搜索。
            for(int i = 0 ; i < n; i++){
                for(int j = 0; j < 26; j++){
                    StringBuilder nextWordBuilder = new StringBuilder(curWord);
                    nextWordBuilder.setCharAt(i , (char)('a' + j));
                    String nextWord = nextWordBuilder.toString();
                    //如果说该节点没被遍历过并且单词库中有该节点
                    if(!visited.contains(nextWord) && wordsLib.contains(nextWord)){
                        if(nextWord.equals(endWord))return cnt;//如果说暴搜的单词等于最后一个单词则返回序列的长度
                        System.out.println(nextWord);
                        visited.add(nextWord);//标记该节点已经被遍历过
                        queue.offer(new Node(nextWord , cnt));//把该节点入队
                        
                    }
                 
                }
            }
        }
        return 0;//找不到转换序列 则返回0
    }
}
//节点类
class Node{
    String word;//单词
    int cnt;//序列长度
    public Node(String word , int cnt){
        this.word = word;
        this.cnt = cnt;
    }
}

124. 二叉树中的最大路径和

考点

dfs、递归

思路

要求:返回其最大路径和
做法:路径和:枚举每个点作为起点,加上左右子树的值,取最大值即可。
先递归处理根节点的左右分支,向下走到底,把叶子节点的最大路径和取一个最大值。
回溯:向上回溯时,会计算上层根节点的路径和,继续取一个最大值。
返回:由于每个节点只能选一条路走,最大路径和下应该选择左右分支的最大值分支

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        //递归函数入口
        maxGain(root);
        //返回最大路径和
        return maxSum;
    }
    //题意分析:
    /*
    要求:返回其最大路径和
    做法:路径和:枚举每个点作为起点,加上左右子树的值,取最大值即可。
    先递归处理根节点的左右分支,向下走到底,把叶子节点的最大路径和取一个最大值。
    回溯:向上回溯时,会计算上层根节点的路径和,继续取一个最大值。
    返回:由于每个节点只能选一条路走,最大路径和下应该选择左右分支的最大值分支
    */
    public int maxGain(TreeNode node){
        if(node == null){
            return 0;
        }
        //向左递归,计算左子树的叶子节点的最大路径和
        //如果小于0 则不选该分支 因为选了后路径和反而更小
        int leftGain = Math.max(maxGain(node.left) , 0);
        //向右递归,计算右子树的叶子节点的最大路径和
       //如果小于0 则不选该分支 因为选了后路径和反而更小
        int rightGain = Math.max(maxGain(node.right) , 0);
        //计算
        //回溯时,会依次把上层非叶子节点做为根节点,计算其路径和
        int priceNewPath = node.val + leftGain + rightGain;
        //把每次计算的结果取一个max
        maxSum = Math.max(maxSum , priceNewPath);
        //返回一条较大路径 给上层节点继续计算路径和
        return node.val + Math.max(leftGain , rightGain);
    }
}

98. 验证二叉搜索树

考点

DFS、双指针、回溯
530. 二叉搜索树的最小绝对差的处理逻辑类似

思路

思想:根据定义,节点的左子树小于当前节点,节点的右子树大于当前节点
也就是left < middle < right
很自然的就想到了用中序遍历,再判断一下是否满足left < middle < right即可
进一步,我们只需要判断当前的节点是否小于之前的节点。
如果小于则不满足条件,向上返回false即可。
否则,则满足条件。


代码

class Solution {
    /*
    思想:根据定义,节点的左子树小于当前节点,节点的右子树大于当前节点
    也就是left < middle < right
    很自然的就想到了用中序遍历,再判断一下是否满足left < middle < right即可
    进一步,我们只需要判断当前的节点是否小于之前的节点。
    如果小于则不满足条件,向上返回false即可。
    否则,则满足条件。
    */
    TreeNode pre; //存储上一个节点
    public boolean isValidBST(TreeNode root) {
            //如果节点为空则直接返回true
            if(root == null)return true;

            //左 创建一个变量记录左子树递归的结果
            boolean left = isValidBST(root.left);
            if(!left){
                return false;
            }
            //中 处理条件的逻辑 判断当前节点是否 <= 上一个节点
            if(pre != null && root.val <= pre.val){
                return false;
            }
            //一开始为空,记录上一个节点。
            pre = root;
             //右 创建一个变量记录右子树递归的结果
            boolean right = isValidBST(root.right);
            //向上返回右子树递归的结果 right
             // if(!right){
       		 //     return false;
        		// }
        //与下等效,考虑到方法的返回语句,如下编译通过。
            return right;
    }
}

往期好文💕

保姆级教程

【保姆级教程】Windows11下go-zero的etcd安装与初步使用

【保姆级教程】Windows11安装go-zero代码生成工具goctl、protoc、go-zero

【Go-Zero】手把手带你在goland中创建api文件并设置高亮


报错解决

【Go-Zero】Error: user.api 27:9 syntax error: expected ‘:‘ | ‘IDENT‘ | ‘INT‘, got ‘(‘ 报错解决方案及api路由注意事项

【Go-Zero】Error: only one service expected goctl一键转换生成rpc服务错误解决方案

【Go-Zero】【error】 failed to initialize database, got error Error 1045 (28000):报错解决方案

【Go-Zero】Error 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using password: YES)报错解决方案

【Go-Zero】type mismatch for field “Auth.AccessSecret“, expect “string“, actual “number“报错解决方案

【Go-Zero】Error: user.api 30:2 syntax error: expected ‘)‘ | ‘KEY‘, got ‘IDENT‘报错解决方案

【Go-Zero】Windows启动rpc服务报错panic:context deadline exceeded解决方案


Go面试向

【Go面试向】defer与time.sleep初探

【Go面试向】defer与return的执行顺序初探

【Go面试向】Go程序的执行顺序

【Go面试向】rune和byte类型的认识与使用

【Go面试向】实现map稳定的有序遍历的方式文章来源地址https://www.toymoban.com/news/detail-838595.html

到了这里,关于【寸铁的刷题笔记】树、回溯、图论、bfs、dfs(四)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • U4_1:图论之DFS/BFS/TS/Scc

    由点(vertices)和边(edges)组成 G = ( V , E ) G=(V,E) G = ( V , E ) , ∣ V ∣ = n |V|=n ∣ V ∣ = n , ∣ E ∣ = m |E|=m ∣ E ∣ = m (这里默认有向图,无向图用 G G G = = = { V V V , E E E }表示 顶点的度是关联在其上的边的数量。满足 ∑ d e g r e e ( v ) = 2 ∣ E ∣ sum degree(v)=2|E| ∑ d e g ree ( v ) = 2∣

    2024年02月05日
    浏览(38)
  • 【算法基础:搜索与图论】3.2 树与图的dfs和bfs

    要学会建树、建图的通用方法。 dfs 和 bfs 的代码框架。 https://www.acwing.com/problem/content/848/ 在 dfs 的过程中,统计各个节点作为断点时的连通块最大值。 https://www.acwing.com/problem/content/849/ 看到最短距离就可以想到使用宽搜。 注意! :题目中说明了 a 和 b 表示存在一条从 a 走到

    2024年02月16日
    浏览(39)
  • 过去一周的刷题笔记

    1.左移()一位相当于乘2,右移()一位相当于除2(不完全等同), 2.格林编码 /*当 n == 1 ,返回 [0,1] . 当 n == 2 ,返回 [0,1,3,2] . 当 n == 3 ,返回 [0,1,3,2,6,7,5,4] . 当 n == …… ,返回 [0,1,3,2,6,7,5,4,……] . 可见当 n == k,就是在 n == k - 1 的情况下增加了一些数字。并且根据题意知道,

    2024年02月02日
    浏览(40)
  • 【算法导论】图论(图的基本概念,图上的深度优先搜索(DFS),广度优先搜索(BFS),最小生成树(MST)及Prim,Kruskal算法)

    图(Graph)是一种包含节点与节点的边的集合,记作G=(V,E),V是节点的集合,E是边的集合。 有向图 一个有向图G=(V,E),E中每个元素是V上的一个二值关系:一条从a出发的连向b的边e可以记作一个 有序 对e = (a,b) 。 无向图 一个无向图G=(V,E),E的每个元素e可以表示V上的一个 无序 对,记

    2024年02月03日
    浏览(52)
  • 图论做题笔记:bfs

    题目: 基因序列可以表示为一条由 8 个字符组成的字符串,其中每个字符都是  \\\'A\\\' 、 \\\'C\\\' 、 \\\'G\\\'  和  \\\'T\\\'  之一。 假设我们需要调查从基因序列  start  变为  end  所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。 例如, \\\"AACCGGTT\\\" -- \\\"AACCGGTA

    2024年04月09日
    浏览(42)
  • 算法基础学习笔记——⑩DFS与BFS\树与图

    ✨博主:命运之光 ✨专栏:算法基础学习 目录 DFS与BFS树与图 ✨DFS ✨BFS 🍓宽搜流程图如下: 🍓宽搜流程: 🍓广搜模板 ✨树与图 🍓树是特殊的图(连通无环的图) 🍓树与图的存储: 🍓用宽搜框架来搜索图: 前言: 算法学习笔记记录日常分享,需要的看哈O(∩_∩)O,

    2024年02月09日
    浏览(35)
  • 推荐一个免费的刷题网站

    在学习编程的过程中,刷题是非常重要的一部分。而随着互联网的发展,许多刷题网站应运而生。今天,我想向大家推荐一个免费的刷题网站:LeetCode。 LeetCode是一个致力于帮助程序员提升技能的在线学习平台。它提供了超过2000道算法题和面试题,覆盖了许多编程语言和难度

    2024年02月03日
    浏览(55)
  • 菜鸟的刷题之路之二叉树

    💕“成功不是终点,失败不是终结,勇气才是启程的第一步。”💕 🐼作者:不能再留遗憾了🐼 🎆专栏:菜鸟的刷题之路🎆 🚗本文章主要内容:将有序数组转换为二叉搜索树、二叉搜索树中第K小的元素和叶子相似的树的详细题解🚗 将有序数组转换为二叉搜索树(难度:

    2024年02月07日
    浏览(36)
  • 刷题笔记25——图论课程表

    为了最终理解你所不理解的,你必须经历一条愚昧无知的道路。为了占有你从未占有的东西,你必须经历被剥夺的道路。为了达到你现在所不在的名位,你必须经历那条你不在其中的道路。——艾略特 非常奇妙,我最初的错误是如下,在找到目标节点后直接加入到res中,但是

    2024年02月07日
    浏览(39)
  • 刷题笔记26——图论二分图判定

    世界上的事情,最忌讳的就是个十全十美,你看那天上的月亮,一旦圆满了,马上就要亏厌;树上的果子,一旦熟透了,马上就要坠落。凡事总要稍留欠缺,才能持恒。 ——莫言 visited数组是在如果有环的情况下,防止在图中一直绕圈设置的,类似于剪枝操作,走过了就没必要再走一遍

    2024年02月07日
    浏览(40)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包