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

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

大家好 ���是寸铁

金三银四，图论基础、回溯结合bfs、dfs是必考的知识点✨

快跟着寸铁刷起来！面试顺利上岸

喜欢的小伙伴可以点点关注

详见如下专栏

寸铁的刷题笔记

17. 电话号码的字母组合

考点

dfs、回溯

代码

class Solution {    //创建一个列表,用于存储组合的结果    Listlist = new ArrayList();    public List letterCombinations(String digits) {        //如果说digits字符串为空或者长度为0        //则说明没有任何可以组合的字符,直接返回空列表即可。        if(digits == null || digits.length() == 0)return list;        //使用数组存储一个映射,也可以使用map存储        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  
77. 组合
 
考点
 
dfs、回溯
 
代码
 
class Solution {    Listresult = new ArrayList();    LinkedListpath = new LinkedList();    //可以删除最后一个元素 removeLast()    //再转为ArrayList()    public List 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             //添加元素            path.add(i);            //递归到下一层 注意: 起始数字从 i + 1开始,确保数字组合不重复。            //每次递归时，都从上一个数字的下一个数开始,这样就不会导致组合出现重复。            combineHelper(n , k , i + 1);            //向上回溯            path.removeLast();        }    }}    /*    bfs暴搜    用一个Map存储单词列表,后面用于匹配单词使用。    暴力搜索单词长度下的字母每一位的26种可能，再去与单词列表进行匹配,匹配成功则标记该单词已经走过。    同时,单词序列的长度(bfs搜索的层数)++,单词入队,用于下一轮的搜索。    最后,判断能否走到最后一个单词,也就是当搜索时匹配到最后一个单词时,搜索停止,返回走过的序列长度。    如何确保转换序列最短？    这里我们是一层层搜索,每一层优先去匹配最后单词。    如果说匹配的上,则返回序列长度。    如果说匹配不上,则把当前搜索的节点入队,用于下一层的继续搜索。    */    public int ladderLength(String beginWord, String endWord, List        //如果说开头的单词的长度与最后一个单词的长度不同,则不存在这样的转换序列。        if(beginWord.length() != endWord.length())return 0;        int n = beginWord.length();        //创建一个单词库,用于后面的单词匹配。        Set            wordsLib.add(word);        }        //如果说终点单词不在单词库中则不存在这样的转换序列。        if(!wordsLib.contains(endWord))return 0;        //宽搜        //创建标记Set记录已经走过的节点        Set            //弹出当前队列的节点进行宽搜            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  
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 
很自然的就想到了用中序遍历,再判断一下是否满足left 
进一步,我们只需要判断当前的节点是否小于之前的节点。
如果小于则不满足条件,向上返回false即可。
否则，则满足条件。
  
代码
 
class Solution {    /*    思想:根据定义,节点的左子树小于当前节点,节点的右子树大于当前节点    也就是left