当前位置: 首页 > article >正文

LeetCodeHot100_0x07

LeetCodeHot100_0x07

49. 二叉树的最近公共祖先(不会)

求解思路: 这题不看答案真想不明白,官解的思路还是太巧妙了。具体的先认识一下如何判断某个节点是p、q祖先,需要任意满足以下两种情况之一:

  • p、q分居两边,那么必定存在一个节点,它的左子树中存在p/q ,右子树中存在q/p
  • p、q同侧,那么必然是p是q的祖先或 q是p的祖先,也就是说根节点是p / q,且子树中存在 p / q即可。

那么如何设计搜索逻辑呢?从根节点出发,首先是判断当前根节点具不具备成为祖宗的潜力:也就是符合上述两种情况:所以我们可以定义一个Boolean类型的DFS方法,分别递归它的左子树和右子树判断是否存在p / q。

通过以上,祖先是找到了,但是如何确保是最近祖先呢?这就归功于递归的回溯特性了。回溯确保能从最底层逐级往上判断,那么最近祖先肯定先被扫描记录到,以确保找到的祖先就是最近祖先。

class Solution {
    public TreeNode res;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 思路描述:
        // 求p q 的最近公共祖先分解:存在最小一棵树使得:
        //1. 左子树中存在p/q  右子树存在 q/p
        //2. p/q 全在一边,那么p / q 其中之一是树根节点

        // 进行dfs深搜判断(题目确保q/p不同)
        // 搜左子树判断是否存在 p/q,定义为 lson
        // 搜右子树判断是否存在 p/q,定义为 rson

        // 如果lson && rson符合 证明符合第一种情况,这个树根节点可能是解
        // 如果树根节点等于 p/q 且lson / rson 存在真,证明符合第二种情况,这个树根可能是解

        // 那要如何确保最近呢?—— 根节点必然是祖先,但是不是最近的
        // dfs的回溯特性,确保了我们是从最底层开始向上推导的,也就是说,一定能确保最近的祖先会先被res记录到
        dfs(root,p,q);
        return res;
    }

    public boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return false;
        boolean lson = dfs(root.left,p,q);  // 判断左子树中是否存在p/q
        boolean rson = dfs(root.right,p,q); // 判断右子树中是否存在p/q

        // 判断是否符合情况1 或 情况2
        if(lson && rson || (root.val == p.val || root.val == q.val) && (lson || rson)) res = root;

        // 如果子树存在lson / rson 或 根节点是 p/q 这三种情况之一,都证明了root下符合要求
        return lson || rson || (root.val == p.val || root.val == q.val);
    }
}


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

求解思路: 求最大路径和 与 求最大长度有什么区别么?其实没有,这题我们一样可以参照树的直径思路,遍历每一个节点,以该节点为树根,求出左子树最大和 与 右子树最大和 + 当前树根值。

当然注意一点,如果左子树最大和小于0,那就没必要左子树了(树根+右子树),因为这是个累赘,不可能是最优解。右子树同理。

class Solution {
    private int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        // 和二叉树直径思路应该类似?遍历每一个节点,然后把左右最大路径相加,再更新最大值
        solve(root);
        return res;
    }

    public int solve(TreeNode root) {
        if(root == null) return 0;
        int LMax = solve(root.left);
        int RMax = solve(root.right);
        res = Math.max(res,LMax + RMax + root.val);
        int ans = Math.max(LMax,RMax) + root.val;
        return ans > 0 ? ans : 0; // 小于零的必然不可能成为最优
    }
}


51. 岛屿数量

求解思路: 这题实质上就是让你判断图中有几块陆地,几个连通块。所以我们可以遍历图,当发现一块陆地时,我们上下左右不断扩张,将周围都是陆地的位置全部利用标记数组标记起来。简化一下我们不用另开标记数组,直接改地图:当遍历到陆地,拿水把它覆盖了,也是一种标记方式。

class Solution {
    public int numIslands(char[][] grid) {
        // 求连通块数量
        int m = grid.length;
        int n = grid[0].length;
        int isLandCount = 0;
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(grid[i][j] == '1') { // 发现一篇陆地,放水去淹
                    infect(grid,i,j);
                    isLandCount ++;
                }
            }
        }
        return isLandCount;
    }

    // 淹水函数
    public void infect(char[][] grid,int x,int y) {
        // 越界不淹,有水不淹
        if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == '0') 
            return ; 

        grid[x][y] = '0';   // 淹水
        
        infect(grid,x+1,y); // 向右淹
        infect(grid,x,y+1); // 向下淹
        infect(grid,x-1,y); // 向左淹
        infect(grid,x,y-1); // 向上淹
    } 
}


52. 腐烂的橘子

求解思路: 这题和上一题类似,都是有一个感染过程。然而这题要求给出最小感染时间,翻译翻译就是最小路径。对于图论中的最小路径问题,基本上要请出我们的BFS算法了。这题一样。我们完全可以定义一个队列存储腐烂橘子,然后进行感染。在感染更新图时,第一层被感染的橘子标记为3,第二层感染的橘子标记为4。即在发起感染的橘子的值基础上加1。最后答案就再遍历一遍,如果还存在新鲜橘子说明无法完全感染,否则在被感染橘子中找到值最大的,再减去2就是答案。

class Solution {
    public int orangesRotting(int[][] grid) {
        // 利用数组本身标记扩散时间,利用队列进行层次感染
        Queue<int[]> queue = new LinkedList<>();
        int m = grid.length;
        int n = grid[0].length;
        int[] dx = {0,1,0,-1};
        int[] dy = {1,0,-1,0};

        //第一遍遍历:将烂橘子加入队列
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(grid[i][j] == 2) {
                    queue.offer(new int[]{i,j});
                }
            }
        }

        // 开始感染橘子
        while(!queue.isEmpty()) {
            // 取出烂橘子
            int[] point = queue.poll();
            int x = point[0], y = point[1];

            // 四个方向进行感染
            for(int i=0;i<4;i++) {
                int u = x + dx[i];
                int v = y + dy[i];
                if(u >= 0 && u < m && v >= 0 && v < n && grid[u][v] == 1) {
                    grid[u][v] = grid[x][y] + 1;    // 感染
                    queue.offer(new int[]{u,v});    // 入队
                }
            }
        }

        // 第二遍遍历,判断答案
        int maxTime = 0;
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(grid[i][j] == 1) return -1;  // 还有新鲜橘子(那你不寄了么)
                if(grid[i][j] >= 2) {
                    maxTime = Math.max(maxTime,grid[i][j] - 2); // 更新最大时间(3表示第一层感染的,减去基准2)
                }
            }
        }
        return maxTime;
    }
}


53. 课程表

求解思路: 首先清楚什么是拓扑,按照拓扑排序的思路,每一次将指向自己次数为0的课程取出来【这些课程就是达到选修条件的】,然后将与这些课程相关的课程的指向次数-1【因为已经修了】。然后如果发现出现了指向为0的课程,就可以继续重复上述操作。

根据描述,可以感觉到这题跟层序遍历思路类似,都需要借助队列将每一层指向为0的元素存储,然后弹出。

这题的关键在于如何用良好的结构将课程间的关系存储起来,然后用队列去处理。
在这里插入图片描述

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 只要课程被指向一次就+1
        List<List<Integer>> edges = new ArrayList<>();
        int[] coursesCnt = new int[numCourses];

        //1. 先把拓扑结构创建好
        for(int i=0;i<numCourses;i++) { 
            edges.add(new ArrayList<Integer>());
        }

        //2. 将拓扑数据存入,指向边次数存入
        for(int[] courses : prerequisites) {
            // 按要求将没门课程的先序课程存入,并记录指向的次数
            edges.get(courses[1]).add(courses[0]);
            ++coursesCnt[courses[0]];
        }

        //3. 创建队列
        Queue<Integer> queue = new LinkedList<>();
        for(int i=0;i<numCourses;i++) {
            // 指向为0的课程可以达修的要求了
            if(coursesCnt[i] == 0) queue.offer(i);
        }

        //4. 操作队列
        int isVisited = 0;  // 已经修完的课程
        while(!queue.isEmpty()) {
            isVisited ++;
            int u = queue.poll();   // 取出指向为0的课程,将它直接关联的课程的指向都-1
            for(int v : edges.get(u)) {
                --coursesCnt[v];
                if(coursesCnt[v] == 0) {
                    queue.offer(v); // 把指向为0的课程又加入到队列中 
                }
            }
        }
        
        //5. 判断是否所有的课程都修完了
        if(isVisited == numCourses) return true;
        return false;
    }
}


54. 实现Tire前缀树(模板)

求解思路: 定义一个数组存放孩子单词节点,并声明一个布尔变量isEnd用来标记结尾。只有标记了结尾的单词才是真正存进Tire的单词,其他路径上的单词只是前缀。

  • 插入时逐个遍历单词,将字母插入到节点该插入的位置,并更新节点位置,然后字母插入完成后将对应节点的isEnd标记为true
  • 查找时也是逐个遍历单词,然后依次判断该字母是否存在于Tire中,最后遍历完后,还需要判断一下末尾字母有没有isEnd = true。
  • 查找前缀和查找思路一致,只是少了个isEnd判断
class Trie {
    // 定义属性
    private Trie[] children;
    private boolean isEnd;

    // 初始化方法
    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
    
    // 插入
    public void insert(String word) {
        // this指向当前实例对象
        Trie node = this;
        for(int i=0; i<word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if(node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];   // 指向下一个节点
        }
        node.isEnd = true;
    }
    
    // 查找
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    // 判断前缀
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    // 查找前缀
    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for(int i=0;i<prefix.length();i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if(node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}


55. 全排列

求解思路: 递归解法

  • 递归终止条件:长度达到数组大小,证明所有元素都参与了排列,计入答案中
  • 递归思路:遍历数组,判断当前位置是否使用,没有就尝试使用,并进入下一层递归,最后回溯删除。
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    boolean[] visited;

    public List<List<Integer>> permute(int[] nums) {
        // 标记数组初始化
        visited = new boolean[nums.length]; 
        // dfs回溯
        dfs(nums, new ArrayList<>());   
        return res;
    }

    private void dfs(int[] nums, List<Integer> path) {
        // 如果将所有元素都选择了,可以作为一个答案
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path)); 
            return;
        }
        // 遍历寻找没有被使用的元素
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                // 将元素加入列表,并标记
                visited[i] = true;
                path.add(nums[i]);

                // 进入下一层调用
                dfs(nums, path);    

                // 递归
                path.remove(path.size() - 1); 
                visited[i] = false;
            }
        }
    }
}


56. 子集

求解思路: 每种元素只有两种选择,只要遍历一遍,让每个元素做出自己的选择,就是其中一个子集。用递归把所有结果记录下来。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> arr = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
    // 每种元素只有两种选择:加入或者不加入
    // 每轮只需要遍历一遍,让每个元素都做出自己的选择就可以了
    // 一共需要做出n^2种选择,用递归再合适不可了。
        // 进行dfs
        dfs(nums,0);
        return res;
    }

    public void dfs(int[] nums, int setup) {
        if(setup == nums.length) {
            res.add(new ArrayList<Integer>(arr));
            return;
        }

        arr.add(nums[setup]); // 加
        dfs(nums,setup + 1);
        arr.remove(arr.size()-1); // 不加
        dfs(nums,setup + 1);
    }
}


57. 电话号码的字母组合

求解思路: 求所有组合。可以这么考虑,例如234,2有三种选择、3有三种选择、4有三种选择。那么我们可以首先遍历digits,遍历到2、3、4.然后对于每一个,我们实现存好对应的映射字母表,再遍历字母表。从字母表种选择其中一个字母作为一种组合。每个元素也是只有选和不选两种选择。

class Solution {

    // 存储哈希
    char[][] s = new char[][] {
        {'a','b','c'},    // 2
        {'d','e','f'},    // 3
        {'g','h','i'},    // 4
        {'j','k','l'},    // 5
        {'m','n','o'},    // 6
        {'p','q','r','s'},// 7 
        {'t','u','v'},    // 8
        {'w','x','y','z'} // 9
    };
    // 存储答案
    List<String> res = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0) return res;    // 非空判断
        dfs(digits,0,new StringBuilder());      // 递归回溯:目标字符串,枚举到的位数,中间字符串
        return res;
    }

    public void dfs(String digits, int setup, StringBuilder sb) {
        if(sb.length() == digits.length()) { // 枚举到了最后一个完,那么一个答案就出来了
            res.add(sb.toString());
            return;
        }
        
        for(char ch : s[digits.charAt(setup)-'2']) {    // 找到当前位置的数值对应映射的哈希字母表
            sb.append(ch);                              // 加入
            dfs(digits,setup+1,sb);                     // 进入下一层 
            sb.deleteCharAt(sb.length() - 1);           // 回溯
        }
    }
}


58. 组合总和

求解思路: 首先进行排序,方便后续剪枝。思路是这样的:允许重复使用元素,也就是说下一层dfs可以从当前元素开始(这个很重要

所以我们在设计DFS时,一样从第一个元素开始尝试,只要当前target小于目标值,就可以尝试将当前元素加入,然后递归下一层时同样从这个元素开始继续进行尝试。当然也要有回溯删除元素。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates,target,0,new ArrayList<Integer>());
        return res;
    }

    public void dfs(int[] candidates,int target,int start, ArrayList<Integer> ans) {
        if(target == 0) {
            res.add(new ArrayList<>(ans));
            return;
        }
        for(int i=start;i<candidates.length;i++) {
            if(target < candidates[i]) break; // 剪枝,后面不合适了
            ans.add(candidates[i]);           // 尝试加入
            dfs(candidates,target-candidates[i],i,ans); // 加入后递归到下一层需要从i继续开始尝试
            ans.remove(ans.size() - 1);       // 回溯
        }
    }
}

59. 括号生成

求解思路:

  • 思路:记录左括号和右括号的使用数量
  • 递归出口条件:左括号和右括号数量为n
  • 递归方案:无脑添加左括号,无脑补充右括号,不行就回溯
class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        // 给定一个n,让你生成含n对且有效的括号数量??????
        // 看到题目我直接一整个放弃摆烂了好吧!

        // 诶,好像又有点思路了!
        // 诶诶诶好像过了
        // 666 甜菜出院
        // 思路: 
            // 1.记录当前用了多少个左括号和右括号
            // 2.如果左括号和右括号都用了N个,就可以存入一种方案
            // 3.无脑添加左括号
            // 4.无脑匹配右括号
            // 5. 回溯回溯回溯!!!
        dfs(0,0,n, new StringBuilder());
        return res;
    }

    public void dfs(int l,int r,int n,StringBuilder str) {
        if(l==n && r==n) {
            res.add(str.toString());
            return;
        }
        if(l < n) {
            dfs(l + 1,r,n,str.append('('));
            str.deleteCharAt(str.length() - 1); // 回溯
        }
        if(r < l) {
            dfs(l, r+1,n,str.append(')'));
            str.deleteCharAt(str.length() - 1); // 回溯
        }
    }
}

60. 总结

LeetCodeHot100_0x07主要是关于搜索和递归的题目,前后也是跨了好多天才做完,这次纯粹是懒大王了。回顾一下每一题的思路吧:

  1. 二叉树的最近公共祖先 经典面试递归
    • 明确公共祖先主要满足两种情况:
      • 当前节点的左右子树分别存在 p / q
      • 当前节点就是p / q,且左子树或右子树中存在另一个
    • 递归终止条件:为空
    • 明确递归思路
      • 定义布尔类型的DFS,用于判断当前节点左子树和右子树分别满不满足存在p/q
      • 定义左子树 lson,右子树rlon,那么翻译符合的两种条件有:
      • lson == true && rson == true ||
      • (root.val == p || root.val == q) && (lson == true || rson == true) )

  1. 二叉树的最大路径和 递归贪心
    • 这题本质上和二叉树的最大直径思路是一样的,只是把左右子树最大深度变形成最大路径和
    • 所以我们参考二叉树直径的思路:
      • (1)遍历每一个节点
      • (2)计算左子树最大和、计算右子树最大和 递归计算
      • (3)判断左、右子树最大和是否大于0 ,小于0的没有加入到答案的机会 贪心思维
    • 递归函数的设计:
      • 递归终止条件:为空返回0
      • 递归返回值: 返回 (左子树最大节点 与 右子树最大节点的较大值 + 当前节点值 )再与0比较,返回较大值
      • 递归思路:递归左子树计算Lmax,递归右子树计算Rmax,作为返回值的计算条件

  1. 岛屿数量 搜索模板DFS
    • 这题算是图论里面最基础的一个模型了。为了判断有几块岛屿,我们可以采取以下策略:
      • (1)遍历图,找到一块陆地
      • (2)以这块陆地出发,上下左右去尽可能把相连的陆地全部找到
      • (3)将这些陆地标记为已使用,表明这一堆陆地等效为一整块陆地

  1. 腐烂橘子 图论搜索BFS队列
    • 这题是图论的另一类模板题,强调广度搜索,具体解题策略如下:
      • (1)第一遍 遍历图,找到所有在0时刻腐烂的橘子,将它们的坐标加入队列结构中
      • (2)第二遍 遍历队列,获取到x时刻的烂橘子,然后立马对上下左右进行扩展一层的搜索
      • (3)如果发现新鲜橘子,将它变成腐烂橘子,并标记腐烂时刻为x+1,最后将它加入腐烂橘子队列
      • (4)循环上述步骤,直到所有腐烂橘子全部出队为止
      • (5)第三遍 遍历图,判断图中还存不存在新鲜橘子,如果还有,说明它可以避免感染。

  1. 课程表 拓扑序列队列
    • 这题要你判断能否将所有课程修完,并且在修课前,要将所有的先修课程完成。这个实际上是考察拓扑序列的问题,所以我们的解题策略描述如下:
      • (1)构建入度,将课程的入度情况存储起来
      • (2)定义队列,将初始构建入度为0的课程加入到队列中
      • (3)遍历队列,逐个取出课程,将所有依附于它的课程入度-1,记录已完成课程数量+1
      • (4)判断入队,如果存在新的入度为0的课程,可以将它继续加入到队列
      • (5)结果判断, 如果已完成课程数量小于课程数组长度,说明修不完。

  1. 实现Tire前缀树 模板前缀树数据结构
    • 这题就是实现前缀树的系列方法,定义好Tire的数据结构:children + isEnd
      • 实现添加:遍历 + 结尾标记true
      • 实现前缀判断:遍历判断children有没有
      • 实现单词判断: 遍历前缀判断 + 结尾标记是否为true

  1. 全排列 dfs
    • 这题递归的经典例题,全排列的思路比较简单,简称试错原理:
      • (1)遍历数组,判断当前元素是否使用过?
      • (2)没使用过,尝试加入ans中,并跳入下一层递归
      • (3)回溯处理,将当前元素从ans中删除

  1. 子集 dfs
    • 这题也是经典例题了,和上题稍微不同的是这题的每一个元素都有两种选择:即选或不选
      • (1)遍历数组,选择当前元素,加入ans,进入下一层递归
      • (2)删除元素,表示不选择当前元素,进入下一层递归

  1. 电话号码的组合 哈希递归
    • 这题在递归思想的基础上多了一步数据映射处理的步骤。先将电话号码与26个字母连城哈希映射。接着进行DFS,DFS思路如下:
      • (1)遍历字符串,获取每一位数值
      • (2)根据数值,找到与之映射的字母表
      • (3)接着就是类似全排列的思路,尝试加入,递归下一层,回溯

  1. 组合总和 sortdfs
    • 这题指出元素可以重复使用,要求写出所有组合之和符合目标值的方案,既然可以重复使用,那就要避免不要形成无限递归,具体策略如下:
      • (1)将原数组进行排序,便于后续进行递归终止判断
      • (2)遍历数组,从默认start = 0位置开始
      • (3)判断终止,判断当前剩下的大小与当前元素大小比较,如果任然小于当前元素,那么后面的也一定不符合了,可以直接终止。
      • (4)如果可以继续,那尝试将该元素加入,并将start更新成当前元素位置,以进入下一层递归
      • (5)如果不合适,回溯

  1. 括号生成 贪心dfs
    • 这题看到题目差点放弃,感觉很抽象,但实际想想,其实遵循两个原则就秒了:
      • (1)无脑放左括号,直到数量到达n
      • (2)无脑补右括号,直到数量等于左括号数量
    • 你就写吧,这两个无脑条件直接秒杀

http://www.kler.cn/a/588327.html

相关文章:

  • [蓝桥杯 2023 省 A] 买瓜 --暴力DFS+剪枝优化
  • 深入分析 Shell 中 IFS、数组赋值与输出行为
  • 相对论-空间和时间(1)
  • ngx_event_conf_t
  • 淘宝API vs 爬虫:合规获取实时商品数据的成本与效率对比
  • [论文阅读]Demystifying Prompts in Language Models via Perplexity Estimation
  • 前端性能优化指标及优化方案
  • Leetcode-1278.Palindrome Partitioning IV [C++][Java]
  • 重返OI:1999
  • 计算机网络:IP数据分片与偏移试题
  • 【网络安全 | 漏洞挖掘】价值14981$的Google点击劫持漏洞
  • 【Agent】OpenManus-Agent-实现具体的智能体
  • c#:使用串口通讯实现数据的发送和接收
  • [WEB开发] Web基础
  • 由一个话题进入DFMEA(设计失效模式及影响分析)
  • 关于新奇的css
  • 强化学习 - PPO控制无人机
  • 第5章 构造、析构、拷贝语义学2: 继承情况下的对象构造
  • ETIMEDOUT 网络超时问题
  • Webpack总结