面试150题-回溯

📕文章题目选自LeetCode面试150题-回溯
😊该文章内容基于作者本人思考总结，如有错误欢迎指正
🏠题单地址：https://leetcode.cn/studyplan/top-interview-150/

回溯

LeetCode150-电话号码的字母组合-LC17

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/9 16:08
 * @Email: lihh53453@hundsun.com
 * @Description: 电话号码的字母组合
 * 1.回溯 确定dfs停止位置
 * 2.遍历要形成组合的集合
 * 3.每次递归index都会改变 当index为digits的长度时单词构建完毕将其添加到结果列表中
 */
public class LC17 {
    private Map<Character,String> map;
    public List<String> letterCombinations(String digits) {
        map = new HashMap<>();
        if(digits.isEmpty()) return new ArrayList<>();
        List<String> list = new ArrayList<>();
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        dfs(list,digits,map,0,new StringBuffer());
        return list;
    }

    private void dfs(List<String> res, String digits, Map<Character, String> map, int index, StringBuffer stringBuffer) {
        if(index == digits.length()){
            res.add(stringBuffer.toString());
        }else{
            String s = map.get(digits.charAt(index));
            for (int i = 0; i < s.length(); i++) {
                stringBuffer.append(s.charAt(i));
                dfs(res, digits, map, index+1, stringBuffer);
                stringBuffer.deleteCharAt(index);
            }
        }
    }

}

LeetCode150-组合-LC77

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/9 16:51
 * @Email: lihh53453@hundsun.com
 * @Description: 组合
 * 剪枝 假如 n = 4  k = 15  temp.size() == 1 此时已经有了一个数 再选n - temp.size()个数
 * 搜索起点的上界 + 接下来要选择的元素个数 - 1 = n  ->  13 + 3 - 1 = 15
 * 最小上界为 13 -> 13 14 15
 * 最小上界为 k - n - (k - path.size()) + 1
 *
 */
public class LC77 {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> temp = new LinkedList<>();
        dfs(temp,res,1,n,k);
        return res;
    }

    private void dfs(Deque<Integer> temp, List<List<Integer>> res, int begin, int n, int k) {
        if(temp.size() == k){
            res.add(new ArrayList<>(temp));
        }else{
            //优化剪枝
            //for(int i = begin;i <= n;i++){
            for(int i = begin;i <= k - n - (k - temp.size()) + 1;i++){
                temp.addLast(i);
                dfs(temp, res, i + 1, n, k);
                temp.removeLast();
            }
        }
    }

}

LeetCode150-全排列-LC46

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/11 14:32
 * @Email: lihh53453@hundsun.com
 * @Description: 全排列
 * 考虑 res添加时要创建新副本
 * 组合的逻辑：交换+回溯
 * 交换的起点为index 选中之后将不在选中
 */
public class LC46 {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        for(int num : nums){
            temp.add(num);
        }
        int n = nums.length;
        dfs(res,temp,0,n);
        return res;
    }

    private void dfs(List<List<Integer>> res, List<Integer> temp, int index, int n) {
        if(index == n){
//            res.add(temp);
            //要拷贝一个新的副本 否则会直接引用原来的list集合
            res.add(new ArrayList<>(temp));
        }else{
//            for (int i = 0; i < n; i++) {
            // 如果i从0开始 dfs启动永远都只会是0坐标开始
            for (int i = index; i < n; i++) {
                Collections.swap(temp,index,i);
                dfs(res,temp,index+1,n);
                Collections.swap(temp,index,i);
            }
        }
    }

    public static void main(String[] args) {
        int[] a = new int[]{1,2,3};
        LC46 lc46 = new LC46();
        lc46.permute(a);
    }
}

组合排列回溯算法总结

相同点
1.两个有需要使用结果list集合和暂存集合保存顺序结果
2.使用dfs+回溯算法
3.res添加结果时要添加新副本 res.add(new ArrayList<>(temp));
4.递归起点相同 都为[index,n)
不同点
1.组合使用queue添加数字，可以考虑剪枝,区间替换为[index,k - n - (k - temp.size())+1]
2.排列使用交换，可以使用Collections.swap()方法

LeetCode150-组合总和-LC39

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/11 15:08
 * @Email: lihh53453@hundsun.com
 * @Description: 组合总和
 * 思路：回溯+target-目标值+跳过节点
 */
public class LC39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        dfs(candidates,target,0,res,temp);
        return res;
    }

    private void dfs(int[] candidates, int target, int index, List<List<Integer>> res, List<Integer> temp) {
        if(target == 0){
            res.add(new ArrayList<>(temp));
            return;
        }
        if(index == candidates.length){
            return;
        }
        dfs(candidates,target,index+1,res,temp);
        if(target - candidates[index] >= 0){
            temp.add(candidates[index]);
            dfs(candidates,target - candidates[index],index,res,temp);
            temp.remove(temp.size() - 1);
        }
    }
}

LeetCode150-N皇后II-LC52

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/11 15:37
 * @Email: lihh53453@hundsun.com
 * @Description: N皇后II 求符合N皇后的个数问题
 * 1.使用三个Set集合判断是否存在 如果存在则该节点的要求
 * 2.三个集合的规则 row+col为右上到左下的斜线  row-col为左上到右下的斜线  row为斜线
 * 3.col从0开始 row使用回溯 同时也从0开始
 * 4.二进制优化 目前没看懂
 */
public class LC52 {
    public int totalNQueens(int n) {
        Set<Integer> row_set = new HashSet<>();
        Set<Integer> dig_set_y = new HashSet<>();
        Set<Integer> dig_set_n = new HashSet<>();
        return dfs(n,0,row_set,dig_set_y,dig_set_n);
    }

    private int dfs(int n, int row, Set<Integer> rowSet, Set<Integer> digSetY, Set<Integer> digSetN) {
        if(row == n){
            return 1;
        }else{
            int count = 0;
//            for (int i = row; i < n; i++) {
            //这不是求组合问题 每次dfs都需要从0坐标位置开始
            for (int col = 0; col < n; col++) {
                if(rowSet.contains(col)) continue;
                if(digSetY.contains(row - col)) continue;
                if(digSetN.contains(row + col)) continue;
                rowSet.add(col);
                digSetY.add(row - col);
                digSetN.add(row + col);
                count +=dfs(n,row + 1,rowSet,digSetY,digSetN);
                rowSet.remove(col);
                digSetY.remove(row - col);
                digSetN.remove(row + col);
            }
            return count;
        }
    }
}

LeetCode150-括号生成-LC22

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/11 16:06
 * @Email: lihh53453@hundsun.com
 * @Description: 括号生成
 * 思路：dfs条件 左括号数量 < n(最大括号数) 可以不断添加
 *             右括号数量 < 左括号数 可以不断添加
 * 更新括号数量
 * dfs结束条件:StringBuilder的长度为n*2
 */
public class LC22 {
    public List<String> generateParenthesis(int n) {
        List<String> res= new ArrayList<>();
        StringBuilder stringBuilder = new StringBuilder();
        dfs(stringBuilder,res,0,0,n);
        return res;
    }

    private void dfs(StringBuilder stringBuilder, List<String> res, int left, int right, int n) {
        if(stringBuilder.length() == n * 2){
            res.add(stringBuilder.toString());
        }else{
            if(left < n){
                stringBuilder.append("(");
                dfs(stringBuilder,res,left+1,right,n);
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            }
            if(left > right){
                stringBuilder.append(")");
                dfs(stringBuilder,res,left,right + 1,n);
                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            }
        }
    }
}

LeetCode150-单词搜索-LC79

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/11 16:27
 * @Email: lihh53453@hundsun.com
 * @Description: 单词搜索
 * 思路：
 * dfs逻辑：1.最后一个字母与单词word最后一个字母相同并且长度与word长度相同
 *         2.匹配index++位置的单词
 * 回溯逻辑：visit[i][j] = true -> false; 匹配完该节点重新将该节点状态返回
 */
public class LC79 {
    private boolean flag = false;
    private boolean[][] visit;
    private final int[][] dict = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    public boolean exist(char[][] board, String word) {
        visit = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j <board[0].length; j++) {
                if(board[i][j] != word.charAt(0)) continue; //剪枝
                dfs(i, j, word, 0, board);
                if(flag) return true;
            }
        }
        return false;
    }

    private void dfs(int i, int j, String word, int index, char[][] board) {
        if(flag) return;//剪枝
        if(board[i][j] != word.charAt(index)){
            return;
        }
        if(index == word.length() - 1){
            flag = true;
        }
        visit[i][j] = true;
        for(int[] arr:dict){
            int new_i = arr[0] + i;
            int new_j = arr[1] + j;
            if(new_i >=0 && new_j >=0 && new_i < board.length && new_j < board[0].length){
                if(!visit[new_i][new_j]){
                    dfs(new_i,new_j,word,index+1,board);
                }
            }
        }
        visit[i][j] = false;
    }
}

回溯总结

1. 电话号码的数组组合：map集合，遍历数字位置map获取单词，index标志结束位
2. 组合：起点index为1,选取数的范围n,终点长度为k,index == k标志结束,副本更新
3. 排列：起点index为0,交换,index == target结束，副本更新
4. 组合总和：起点index为0，for循环从0开始 因为可以无限选，无限选要保证跳过的逻辑，target-当前值
5. N皇后：三条斜线Set集合保存当前节点row-col,row,row+rol,回溯节点状态
6. 括号生成：结束位置为n*2，记录括号左右数量，数量增加逻辑(left<n,right<left)->dfs
7. 单词搜索：小岛数量(回溯版)，回溯visit节点状态，减枝

面试150题-树+图论

📕文章题目选自LeetCode面试150题-树、图论部分
😊该文章内容基于作者本人思考总结，如有错误欢迎指正
🏠题单地址：https://leetcode.cn/studyplan/top-interview-150/

树

LeetCode150-二叉树的最大深度-LC104

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/5 10:16
 * @Email: lihh53453@hundsun.com
 * @Description: 二叉树的最大深度
 * 递归
 */
public class LC104 {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right) + 1;
    }
}

LeetCode150-相同的树-LC104

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/5 10:21
 * @Email: lihh53453@hundsun.com
 * @Description: 相同的树
 * 递归
 */
public class LC100 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }else if(p == null || q == null){
            return false;
        } else if (p.val != q.val) {
            return false;
        }else{
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }
    }
}

LeetCode150-反转二叉树-LC226

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/5 10:38
 * @Email: lihh53453@hundsun.com
 * @Description: 反转二叉树
 */
public class LC226 {
    public TreeNode invertTree_dfs(TreeNode root) {
        if(root == null) return null;
        TreeNode left = invertTree_dfs(root.left);
        TreeNode right = invertTree_dfs(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

LeetCode150-对称二叉树-LC101

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/5 10:59
 * @Email: lihh53453@hundsun.com
 * @Description:
 */
public class LC101 {
    public boolean isSymmetric(TreeNode root) {
        return check(root.left,root.right);
    }
    private boolean check(TreeNode left,TreeNode right){
        if(left == null && right == null){
            return true;
        }else if(left == null || right == null){
            return false;
        }else{
            return left.val == right.val && check(left.right,right.left) && check(right.right,left.left);
        }
    }
}

LeetCode150-从前序与中序遍历序列构造二叉树-LC105

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/5 16:45
 * @Email: lihh53453@hundsun.com
 * @Description:
 */
public class LC105 {
    private Map<Integer,Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        int length = inorder.length;
        for(int i = 0; i < inorder.length;i++){
            map.put(inorder[i],i);
        }
        return setTree(preorder,inorder,0,length - 1,0, length - 1);
    }

    private TreeNode setTree(int[] preorder, int[] inorder, int pre_start, int pre_end, int ino_start, int ino_end) {
        if(pre_start > pre_end) return null; //坐标相遇即停止
        int root_value = preorder[pre_start];
        int root_index_in_inorder = map.get(root_value);
        int size_left_subtree = root_index_in_inorder - ino_start;
        TreeNode root = new TreeNode(root_value);
        // 递归构建左子树 形成对应关系
        // 左子树在前序遍历中的边界是：从pre_start + 1（根节点已使用）到pre_start + size_left_subtree
        // 左子树在中序遍历中的边界是：从ino_start到ino_end - 1（排除根节点）
        root.left = setTree(preorder, inorder, pre_start + 1, pre_start + size_left_subtree, ino_start, root_index_in_inorder - 1);
        // 递归构建右子树
        // 右子树在前序遍历中的边界是：从pre_start + size_left_subtree + 1到pre_end
        // 右子树在中序遍历中的边界是：从root_index_in_inorder + 1到ino_end
        root.right = setTree(preorder, inorder, pre_start + size_left_subtree + 1, pre_end, root_index_in_inorder + 1, ino_end);
        return root;
    }
}

LeetCode150-从中序与后序遍历序列构造二叉树-LC106

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/5 17:18
 * @Email: lihh53453@hundsun.com
 * @Description:
 */
public class LC106 {
    private Map<Integer,Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        int n = inorder.length;
        for(int i = 0; i < inorder.length;i++){
            map.put(inorder[i],i);
        }
        return setTree(inorder,postorder,0,n - 1,0,n - 1);
    }

    private TreeNode setTree(int[] inorder, int[] postorder, int ino_start, int ino_end, int post_start, int post_end) {
        if(ino_start > ino_end) return null;
        int root_index = map.get(postorder[post_end]);
        int left_tree_len = root_index - ino_start;
        TreeNode root = new TreeNode(postorder[post_end]);
        // 递归构建左子树。
        // 左子树在中序遍历中的边界是从ino_start到ino_start + left_tree_len - 1。
        // 左子树在后序遍历中的边界是从post_start到post_start + left_tree_len - 1。
        root.left = setTree(inorder, postorder, ino_start, root_index - 1, post_start, post_start + left_tree_len - 1);

        // 递归构建右子树。
        // 右子树在中序遍历中的边界是从root_index + 1到ino_end。
        // 右子树在后序遍历中的边界是从post_start + left_tree_len到post_end - 1。
        root.right = setTree(inorder, postorder, root_index + 1, ino_end, post_start + left_tree_len, post_end - 1);
        return root;
    }
}

两个数组实现中序遍历 先序遍历 后序便利的转换总结

先序遍历

// 递归构建左子树
root.left = setTree(preorder, inorder, 
                    pre_start + 1, // 左子树前序遍历起始索引
                    pre_start + size_left_subtree, // 左子树前序遍历结束索引
                    ino_start, // 左子树中序遍历起始索引
                    root_index_in_inorder - 1); // 左子树中序遍历结束索引（排除根节点）

// 递归构建右子树
root.right = setTree(preorder, 
                     inorder, 
                     pre_start + size_left_subtree + 1, // 右子树前序遍历起始索引
                     pre_end, // 右子树前序遍历结束索引
                     root_index_in_inorder + 1, // 右子树中序遍历起始索引
                     ino_end); // 右子树中序遍历结束索引

中序遍历

// 递归构建左子树
root.left = setTree(inorder, 
                    ino_start, // 左子树中序遍历起始索引
                    root_index_in_inorder - 1, // 左子树中序遍历结束索引（排除根节点）
                    ...); // 省略其他参数

// 递归构建右子树
root.right = setTree(inorder, 
                     root_index_in_inorder + 1, // 右子树中序遍历起始索引
                     ino_end, // 右子树中序遍历结束索引
                     ...); // 省略其他参数

后序遍历

// 递归构建左子树
root.left = setTree(postorder, 
                    inorder, 
                    post_start, // 左子树后序遍历起始索引
                    post_start + left_tree_len - 1, // 左子树后序遍历结束索引
                    ino_start, // 左子树中序遍历起始索引
                    root_index_in_inorder - 1); // 左子树中序遍历结束索引

// 递归构建右子树
root.right = setTree(postorder, 
                     inorder, 
                     post_start + left_tree_len, // 右子树后序遍历起始索引
                     post_end - 1, // 右子树后序遍历结束索引
                     root_index_in_inorder + 1, // 右子树中序遍历起始索引
                     ino_end); // 右子树中序遍历结束索引

LeetCode150-填充每个节点的下一个右侧节点指针 II-LC117

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/5 19:02
 * @Email: lihh53453@hundsun.com
 * @Description:
 * 使用dfs递归的方式处理 
 * 1.在遍历的过程中 左节点的个数与层数都相同
 * 2.当不同时则是需要被连接的节点
 * 3.更新每一层的最新的位置节点位置
 * 4.递归处理
 * 5.递归结束 当节点为空时不处理 直接return
 */
public class LC117 {
    private final List<TreeNodePoint> list = new ArrayList<>();
    public TreeNodePoint connect(TreeNodePoint root) {
        dfs(root,0);
        return root;
    }
    public void dfs(TreeNodePoint root,int depth){
        if(root == null) return;
        if(depth == list.size()){
            list.add(root);
        }else{
            list.get(depth).next = root;
            list.set(depth,root);
        }
        dfs(root.left,depth + 1);
        dfs(root.right,depth + 1);
    }
}

LeetCode150-二叉树展开为链表-LC114

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/6 9:08
 * @Email: lihh53453@hundsun.com
 * @Description: 二叉树展开为链表
 * 逻辑：找到左子树的最右节点 将右子树的头节点衔接到左子树的最右节点
 * cur 当前节点root
 * next root的左子树头节点
 * pre 从左子树头节点开始依次遍历到左子树的最右节点
 * pre.right = cur.right; 连接操作
 * cur进入链表 进入下一节点 cur = cur.right
 */
public class LC114 {
    public void flatten(TreeNode root) {
        TreeNode cur = root;
        while(cur != null){
            if(cur.left != null){
                TreeNode next = cur.left;
                TreeNode pre = next;
                while(pre.right != null){
                    pre = pre.right;
                }
                pre.right = cur.right;
                cur.left = null;
                cur.right = next;
            }
            cur = cur.right;
        }
    }
}

LeetCode150-路径总和-LC112

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/6 9:22
 * @Email: lihh53453@hundsun.com
 * @Description: 路径总和
 */
public class LC112 {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) return false;
        //if(root.val == targetSum) return true;
        //这里需要一个条件判断
        if(root.left == null && root.right == null){
            return targetSum == root.val;
        }
        return hasPathSum(root.left,targetSum - root.val) || hasPathSum(root.right,targetSum - root.val);
    }
}

LeetCode150-求根节点到叶节点数字之和-LC129

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/6 9:32
 * @Email: lihh53453@hundsun.com
 * @Description: 求根节点到叶节点的数字之和
 * 向下传递路径和 4 7 5 6 向7 传递47 但是返回475 + 476
 */
public class LC129 {
    public int sumNumbers(TreeNode root) {
        return dfs(root,0);
    }
    private int dfs(TreeNode root,int sum){
        if(root == null) return 0;
        sum = sum * 10 + root.val;
        if(root.left == null && root.right == null){
            return sum;
        }else {
            return dfs(root.left,sum) + dfs(root.right,sum);
        }
    }
}

LeetCode150-二叉树中的最大路径和-LC124

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/6 9:58
 * @Email: lihh53453@hundsun.com
 * @Description: 二叉树中的最大路径和 
 * 解析如图
 */
public class LC124 {
    int max_value = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxSum(root);
        return max_value;
    }
    public int maxSum(TreeNode root){
        if(root == null) return 0;

        int left = Math.max(maxSum(root.left),0);
        int right = Math.max(maxSum(root.right),0);
        int nowVal = left + right + root.val;
        max_value = Math.max(max_value,nowVal);
        return root.val + Math.max(left,right);
    }
}

LeetCode150-二叉树中的最大路径和-LC124

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/6 10:46
 * @Email: lihh53453@hundsun.com
 * @Description: 使用中序遍历构建二叉搜索树
 */
public class LC173 {
    private List<Integer> list;
    private int index;
    public LC173(TreeNode root) {
        index = 0;
        list = new ArrayList<>();
        init_tree(root,list);
    }

    public int next() {
        return list.get(index++);
    }

    public boolean hasNext() {
        return index < list.size();
    }
    public void init_tree(TreeNode root,List<Integer> arr){
        if(root == null){
            return;
        }
        init_tree(root.left,arr);
        arr.add(root.val);
        init_tree(root.right,arr);
    }
}

LeetCode150-完全二叉树的节点个数-LC222

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/6 16:25
 * @Email: lihh53453@hundsun.com
 * @Description: 完全二叉树的节点个数
 * 递归计算即可
 */
public class LC222 {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        int left = countNodes(root.left);
        int right = countNodes(root.right);
        return left + right + 1;
    }
}

LeetCode150-二叉树的最近公共祖先-LC236

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/6 16:38
 * @Email: lihh53453@hundsun.com
 * @Description: 二叉树的最近公共祖先
 */
public class LC236 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        /*
          返回条件：1.当前节点为空
                  2.找到了p节点
                  3.找到了q节点
         */
        if(root == null || p == root || q == root) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if(left == null) return right; //如果左子树为空 那么两个节点都在右子树
        if(right == null) return left; //如果右子树为空 那么两个节点都在左子树
        return root; //如果左子树和右子树都拿到值了 那么此时这个节点就是要找的节点
    }
}

递归树总结：

• 对于树的题一般采用dfs算法
• 递归时确定递归的截至位置 例如if(root == null) return 0;
• 与计算相关时 截止位置的返回值一般为return 0
• 找到递归的逻辑

LeetCode150-二叉树的右视图-LC199

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/6 17:33
 * @Email: lihh53453@hundsun.com
 * @Description: 二叉树的右视图
 */
public class LC199 {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int count = queue.size();
            for (int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                //                queue.offer(root.left);
                //                queue.offer(root.right);
                //这里要注意判断是否非空
                if(node!=null){
                    if(node.left != null) queue.offer(node.left);
                    if(node.right != null) queue.offer(node.right);
                    if(i == count - 1) res.add(node.val); //唯一的操作就是在bfs的过程中将最后的节点加入list
                }
            }
        }
        return res;
    }
}

LeetCode150-二叉树的层平均值-LC637

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/7 9:04
 * @Email: lihh53453@hundsun.com
 * @Description: 二叉树的层平均值
 */
public class LC637 {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        int size;
        queue.offer(root);
        while(!queue.isEmpty()){
            size = queue.size();
            double levelSum = 0.0;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if(node != null){
                    levelSum += node.val;
                    if(node.left != null) queue.offer(node.left);
                    if(node.right != null) queue.offer(node.right);
                }
            }
            res.add((levelSum / size));
        }
        return res;
    }
}

LeetCode150-二叉树的层序遍历-LC102

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/7 9:20
 * @Email: lihh53453@hundsun.com
 * @Description: 二叉树的层序遍历
 */
public class LC102 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        int size;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            size = queue.size();
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if(node!=null){
                    temp.add(node.val);
                    if(node.left != null) queue.offer(node.left);
                    if(node.right != null) queue.offer(node.right);
                }
            }
            res.add(temp);
        }
        return res;
    }
}

层次树总结

/**
 * 层次遍历模板代码
 */
public List<List<Integer>> static bfs(TreeNode root){
    List<List<Integer>> res = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    List<Integer> list = new ArrayList<>();
    queue.offer(root);
    int size;
    ... 添加逻辑代码
    while(!queue.isEmpty()){
        size = queue.size();
        for(int i = 0;i < size;i++){
            TreeNode node = queue.poll();
            list.add(node.val);
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
            ... 添加逻辑代码
        }
        res.add(list);
    }
    return res;
}

LeetCode150-二叉搜索树的最小绝对差-LC530

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/7 14:18
 * @Email: lihh53453@hundsun.com
 * @Description: 二叉搜索树的最小绝对差
 */
public class LC530 {
    int pre;
    int res;
    public int getMinimumDifference(TreeNode root) {
        res = Integer.MAX_VALUE;
        pre = -1;
        dfs(root);
        return res;
    }
    private void dfs(TreeNode root){
        if(root == null) return;
        dfs(root.left);
        if (pre != -1) {
            res = Math.min(res, root.val - pre);
        }
        pre = root.val; //保存上一节点值
        dfs(root.right);
    }
}

LeetCode150-二叉搜索树中第K小的元素-LC230

LeetCode150-验证二叉搜索树-LC98

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/7 15:34
 * @Email: lihh53453@hundsun.com
 * @Description: 验证二叉搜索树
 */
public class LC98 {
    long pre = Long.MIN_VALUE; //Integer.MIN_VALUE 和例子冲突 0x8000000000000000L为最小值
    boolean res;
    public boolean isValidBST(TreeNode root) {
        res = true;
        dfs(root);
        return res;
    }
    public void dfs(TreeNode root){
        if(root == null) return;
        if(!res) return; //检查res是否已经更新为false;
        dfs(root.left);
        if(root.val > pre){
            pre = root.val; //更新pre值
        }else{
            res = false;
        }
        dfs(root.right);
    }
}

二叉搜索树总结

1.二叉搜索树的逻辑就是中序遍历

public void dfs(TreeNode root){
    if(root == null) return;
        ... 可以在这里限制执行结束的操作 如2所述
    dfs(root.left);
    ... 中序遍历要执行的操作 例如 list.add(root.val);
    dfs(root.right);
}

2.可以设置一个全局变量作为结束当前遍历的标志
例如因为找到了第K小的元素 此时–k == 0
此时更新值 并且直接返回return即可 后面的操作直接忽略

图

LeetCode150-岛屿数量-LC200

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/7 16:17
 * @Email: lihh53453@hundsun.com
 * @Description: 被围绕的区域
 */
public class LC200 {
    int row;
    int col;
    public int numIslands(char[][] grid) {
        if(grid == null ||  grid.length == 0 || grid[0].length == 0) return 0;
        row = grid.length;
        col = grid[0].length;
        int res = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(grid[i][j] == '1'){
                    res++;
                    dfs(grid,i,j);
                }
            }
        }
        return res;
    }
    public void dfs(char[][] grid,int i,int j){
        if(i < 0 || j < 0 || i >= row || j >= col || grid[i][j] == '0'){
            return;
        }
        grid[i][j] = '0';
        dfs(grid,i + 1,j);
        dfs(grid,i - 1,j);
        dfs(grid,i,j + 1);
        dfs(grid,i,j - 1);
    }
}

LeetCode150-被环绕的区域-LC130

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/7 17:03
 * @Email: lihh53453@hundsun.com
 * @Description: 被环绕的区域
 */
public class LC130 {
    int row;
    int col;
    public void solve(char[][] board) {
        if(board == null || board[0].length == 0) return;
        row = board.length;
        col = board[0].length;
        for (int i = 0; i < col; i++) {
            dfs(board,0,i);
            dfs(board,row - 1,i);
        }
        for (int i = 0; i < row; i++) {
            dfs(board,i,0);
            dfs(board,i,col - 1);
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(board[i][j] == 'A'){
                    board[i][j] = 'O';
                }else if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }

    }
    public void dfs(char[][] board,int i,int j){
//        if(i < 0|| j < 0 || i >= row || j >= col || board[i][j] == 'X'){
//            return;
//        }
        //board[i][j] == 'X' 这里没有对'A'进行排除 否则就会报错 死循环
        // 死循环 -> [['O','O'],['O','O']]
        if(i < 0|| j < 0 || i >= row || j >= col || board[i][j] != 'O'){
            return;
        }
        board[i][j] = 'A';
        dfs(board,i+1,j);
        dfs(board,i-1,j);
        dfs(board,i,j+1);
        dfs(board,i,j-1);

    }
}

LeetCode150-克隆图-LC130

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/8 10:34
 * @Email: lihh53453@hundsun.com
 * @Description: 克隆图
 * 保证图不会死循环的满足条件
 * 1.map存储已经访问的节点 在访问之前进行判断
 * 2.在递归之前就要将克隆节点保存到map中防止重复访问
 */
public class LC133 {
    private final Map<MapNode,MapNode> map = new HashMap<>();
    public MapNode cloneGraph(MapNode node) {
        if(node == null) return null;
        if(map.containsKey(node)) return map.get(node);
        MapNode cacheNode = new MapNode(node.val,new ArrayList<>());
        map.put(node,cacheNode);
        for(MapNode mapNode:node.neighbors){
            cacheNode.neighbors.add(cloneGraph(mapNode));
        }
        return cacheNode;
    }
}

（待解决）LeetCode150-除法求值-LC399

LeetCode150-课程表-LC207

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/8 14:18
 * @Email: lihh53453@hundsun.com
 * @Description: 课程表
 * 这一题就是判断有没有环 如果在dfs的过程中走到了自己 说明不满足拓扑排序
 * 构造拓扑排序 每一个节点对应一个状态 0未开始 1真在找节点 2节点访问完毕
 * 停止条件即judge为false时 全部return
 */
public class LC207 {
    List<List<Integer>> keys;
    int[] visit;
    boolean judge = true;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        keys = new ArrayList<>();
        visit = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            keys.add(new ArrayList<>());
        }
        for (int[] arr:prerequisites){
            keys.get(arr[1]).add(arr[0]);
        }
        for (int i = 0; i < numCourses && judge; i++) {
            if(visit[i] == 0){
                dfs(i);
            }
        }
        return judge;
    }

    public void dfs(int num){
        visit[num] = 1;
        for (int v:keys.get(num)){
            if(visit[v] == 0){
                dfs(v);
                if(!judge){
                    return;
                }
            }else if(visit[v] == 1){
                judge = false;
                return;
            }
        }
        visit[num] = 2;
    }
}

LeetCode150-课程表II-LC210

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/8 14:44
 * @Email: lihh53453@hundsun.com
 * @Description: 课程表II
 */
public class LC210 {
    List<List<Integer>> keys; //每一个课程对应一个链表
    boolean flag = true; // 是否满足有向无环图
    int[] result; //模拟栈
    int[] visited; //当前坐标位置访问标记
    int index; //栈的位置坐标
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        keys = new ArrayList<>();
        result = new int[numCourses];
        visited = new int[numCourses];
        index = numCourses - 1;
        for (int i = 0; i < numCourses; i++) {
            keys.add(new ArrayList<>());
        }
        for(int[] arr:prerequisites){
            keys.get(arr[0]).add(arr[1]); //注意这里的先后顺序 [0,1] 先走arr[0] 才能走arr[1];
        }
        for (int i = 0; i < numCourses && flag; i++) {
            if(visited[i] == 0){
                dfs(i);
            }
        }
        if (!flag) {
            return new int[0];
        }
        return result;
    }
    public void dfs(int num){
        visited[num] = 1;
        for(int val:keys.get(num)){
            if(visited[val] == 0){
                dfs(val);
                if(!flag) return;
            }else if(visited[val] == 1){
                flag = false;
                return;
            }
        }
        visited[num] = 2;
        result[index--] = num;
    }
}

拓扑排序总结

模板代码

public class Sort {
    List<List<Integer>> keys; //每一个坐标都有一个可以走到的点，用一个链表维护
    int[] visit; //当前坐标位置访问状态 0未开始 1进行中 2结束
    boolean judge = true; //是否满足有向无环图
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        keys = new ArrayList<>();
        visit = new int[numCourses];//初始化
        for (int i = 0; i < numCourses; i++) {
            keys.add(new ArrayList<>());//numCourses个坐标对应numCourses个链表
        }
        for (int[] arr:prerequisites){
            keys.get(arr[1]).add(arr[0]);//将当前点位可以到达的坐标添加到链表
        }
        for (int i = 0; i < numCourses && judge; i++) {
            if(visit[i] == 0){//当前坐标未开始 从当前节点进入
                dfs(i);
            }
        }
        return judge;//返回是否满足拓扑排序
    }

    public void dfs(int num){
        visit[num] = 1;//将状态修改为进行中
        for (int v:keys.get(num)){
            if(visit[v] == 0){
                dfs(v);
                if(!judge){
                    return;//如果此时已经不满足拓扑排序规则直接return
                }
            }else if(visit[v] == 1){//拓扑排序走到了自己 说明形成了环不满足规则将标志位改为false
                judge = false;
                return;
            }
        }
        visit[num] = 2;
    }
}

LeetCode150-蛇梯棋-LC909

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/8 16:29
 * @Email: lihh53453@hundsun.com
 * @Description: 蛇梯棋
 */
public class LC909 {
    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        boolean[] vis = new boolean[n*n + 1];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{1,0});
        while(!queue.isEmpty()){
            int[] node = queue.poll();
            for(int i = 1;i <= 6;++i){
                int nxt = node[0] + i;
                if(nxt > n * n){
                    break;
                }
                int[] rc = change(nxt,n);
                if(board[rc[0]][rc[1]] > 0){
                    nxt = board[rc[0]][rc[1]];
                }
                if(nxt == n * n){
                    //return rc[1]+1; 这里不是坐标位置加1 而是节点位置+1
                    return node[1] + 1;
                }
                if(!vis[nxt]){
                    vis[nxt] = true;
                    queue.offer(new int[]{nxt,node[1]+1});//同上
                }
            }
        }
        return -1;
    }

    public int[] change(int next,int n) {
        int row = (next - 1) / n;
        int col = (next - 1) % n;
        if(row % 2 == 1){
            col = n - 1 - col;
        }
        return new int[]{n - 1 - row,col};
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {-1, -1, -1, -1, -1, -1},
                {-1, -1, -1, -1, -1, -1},
                {-1, -1, -1, -1, -1, -1},
                {-1, 35, -1, -1, 13, -1},
                {-1, -1, -1, -1, -1, -1},
                {-1, 15, -1, -1, -1, -1}
        };
        LC909 lc909 = new LC909();
        lc909.snakesAndLadders(matrix);
    }
}

LeetCode150-最小基因变化-LC433

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/9 9:03
 * @Email: lihh53453@hundsun.com
 * @Description: 最小基因变化
 * 思路：
 * 1.将单词中每一个字符替换成dict的单词 添加到队列中
 * 2.存储在队列中时进行判断 visit是否遍历过 set集合是否包含目标数组
 * 3.满足以上条件step++
 * 4.当找到end单词时返回step 否则返回-1
 * 5.bfs条件：队列 弹出 队列长度遍历 
 */
public class LC433 {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Queue<String> queue = new ArrayDeque<>();
        Set<String> set = new HashSet<>(Arrays.asList(bank));
        Set<String> visited = new HashSet<>();
        Character[] dict = {'A','C','G','T'};
        if(startGene.equals(endGene)) return 0;
        if(!set.contains(endGene)) return -1;
        queue.add(startGene);
        visited.add(startGene);
        int step = 1;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                for (int j = 0; i < word.length(); i++) {
                    for (int k = 0; j < 4; j++) {
                        if(dict[k] != word.charAt(j)){
                            StringBuilder sb = new StringBuilder(word);
                            sb.setCharAt(j,dict[k]);
                            String v_string = sb.toString();
                            if(!visited.contains(v_string) && set.contains(v_string)){
                                if(v_string.equals(endGene)){
                                    return step;
                                }
                                queue.offer(v_string);
                                visited.add(v_string);
                            }
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }
}

LeetCode150-单词接龙-LC127

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/9 9:44
 * @Email: lihh53453@hundsun.com
 * @Description: 单词接龙
 * 单词接龙 参数 start开始单词 end结束单词 限定符合的单词集合keys
 * 1.遍历单词集合set防止重复遍历
 * 2.queue队列保存下一遍历单词 创建队列 初始化队列 弹出节点 确定每一次队列的长度循环遍历
 * 3.确定判断条件
 *   3.1 不在keys中直接进入下一次循环
 *   3.2 visit已经访问的直接进入下一次循环
 */
public class LC127 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> visit = new HashSet<>();
        Queue<String> queue = new ArrayDeque<>();
        Set<String> key = new HashSet<>(wordList);
        int step = 1;
        if(beginWord.equals(endWord) || !key.contains(endWord)) return 0;
        queue.offer(beginWord);
        visit.add(beginWord);
        while(!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                assert word != null;
                if(word.equals(endWord)) return step;
                for (int j = 0; j < endWord.length(); j++) {
                    char[] charArray = word.toCharArray();
                    char temp = charArray[j];
                    for (char k = 'a'; k <= 'z'; k++) {
                        if(k == word.charAt(j)){
                            continue;
                        }
                        charArray[j] = k;
                        String v_string = new String(charArray);
                        if(!visit.contains(v_string) && key.contains(v_string)){
                            visit.add(v_string);
                            queue.offer(v_string);
                        }
                    }
                    charArray[j] = temp;
                }
            }
            step++;
        }
        return 0;
    }
}

LeetCode150-实现前缀树-LC208

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/9 10:40
 * @Email: lihh53453@hundsun.com
 * @Description:
 */
public class LC208 {
    private LC208[] children;
    private boolean isEnd;
    public LC208() {
        boolean isEnd = false;
        children = new LC208[26];
    }

    public void insert(String word) {
        LC208 trie = this;
        char[] charArray = word.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            char c = charArray[i];
            int index = c - 'a';
            if(trie.children[index] == null){
                trie.children[index] = new LC208();
            }
            trie = trie.children[index];
        }
        trie.isEnd = true;
    }

    public boolean search(String word) {
        LC208 trie = searchPrefix(word);
        return null != trie && trie.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }
    private LC208 searchPrefix(String prefix) {
        LC208 trie = this;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            int index = c - 'a';
            if(trie.children[index] == null){
                return null;
            }
            trie = trie.children[index];
        }
        return trie;
    }
}

LeetCode150-单词拼写-LC221

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/9 11:13
 * @Email: lihh53453@hundsun.com
 * @Description: 单词拼写
 * 1.每一个节点维护一个节点数组和结束标志isEnd
 * 2.使用start坐标标志位 当与长度相同时 结束判断isEnd是否为true
 */
public class LC221 {
}
class WordDictionary {
    private WordDictionary[] children;
    private boolean isEnd;

    public WordDictionary() {
        children = new WordDictionary[26];
    }

    public void addWord(String word) {
        WordDictionary node = this;
        char[] charArray = word.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            int index = charArray[i] - 'a';
            if (node.children[index] == null) {
                node.children[index] = new WordDictionary();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        return search(this, word, 0);
    }

    private boolean search(WordDictionary node, String word, int start) {
        if (start == word.length()) {
            return node.isEnd;
        }
        char c = word.charAt(start);
        if (c != '.') {
            WordDictionary child = node.children[c - 'a'];
            return child != null && search(child, word, start + 1);
        } else {
            for (int j = 0; j < 26; j++) {
                if (node.children[j] != null && search(node.children[j], word, start + 1)) {
                    return true;
                }
            }
            return false;
        }
    }
}

LeetCode150-单词拼写II-LC212

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/9 14:35
 * @Email: lihh53453@hundsun.com
 * @Description: 字典树 + 回溯 + 递归dfs
 * 1.构建字典树 将每一个单词添加到字典树中
 * 2.遍历每一个棋子 遍历完棋子都需要回溯
 * 3.dfs的过程中会访问当前字典树上是否已经构建了单词 满足isEnd时就将其添加到结果集合中
 */
public class LC212 {
    // 存储结果集
    private final Set<String> res = new HashSet<>();
    // 四个方向的移动：右，左，下，上
    private final int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    // 接收一个字符矩阵和单词数组，返回矩阵中能拼出的单词列表
    public List<String> findWords(char[][] board, String[] words) {
        Trie trie = new Trie();
        // 将所有单词插入字典树
        for (String word : words) {
            trie.insert(word);
        }

        // 遍历棋盘的每个格子，从每个格子开始深度优先搜索
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, trie.root, i, j, new StringBuilder());
            }
        }

        // 将结果集转换为列表并返回
        return new ArrayList<>(res);
    }

    // 深度优先搜索函数
    private void dfs(char[][] board, TrieNode node, int i, int j, StringBuilder word) {
        // 检查当前位置是否越界或已经被访问过
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || node == null || board[i][j] == '*') {
            return;
        }

        // 当前字符
        char c = board[i][j];
        // 计算字符在字典树中的索引
        int index = c - 'a';
        // 获取字典树中对应的节点
        TrieNode nextNode = node.children[index];
        // 如果没有对应的节点，说明当前路径不包含任何单词
        if (nextNode == null) {
            return;
        }

        // 将当前字符添加到路径中
        word.append(c);
        // 如果当前节点是单词的结尾，将路径添加到结果集中
        if (nextNode.isEnd) {
            res.add(word.toString());
        }

        // 标记当前位置为已访问
        board[i][j] = '*';
        // 遍历四个方向
        for (int[] dir : directions) {
            int newI = i + dir[0];
            int newJ = j + dir[1];
            // 递归搜索下一个位置
            dfs(board, nextNode, newI, newJ, word);
        }
        // 恢复当前位置的字符
        board[i][j] = c;
        // 回溯，移除路径中的最后一个字符
        word.setLength(word.length() - 1);
    }
}

// 定义字典树节点
class TrieNode {
    // 存储子节点的数组，长度为26，对应26个英文字母
    TrieNode[] children = new TrieNode[26];
    // 标记该节点是否是单词的结尾
    boolean isEnd;

    public TrieNode() {}
}

// 定义字典树
class Trie {
    // 字典树的根节点
    public TrieNode root = new TrieNode();

    // 向字典树中插入单词
    public void insert(String word) {
        TrieNode node = root;
        // 遍历单词中的每个字符
        for (char c : word.toCharArray()) {
            // 计算字符在字典树中的索引
            int index = c - 'a';
            // 如果当前节点没有子节点，创建新的子节点
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            // 移动到子节点
            node = node.children[index];
        }
        // 设置当前节点为单词的结尾
        node.isEnd = true;
    }
}

图论总结

1.岛屿问题
定义遍历时的出发点 有时时从四周 有时遍历每一个点
维护一个visit数组将访问过的节点标记防止重复遍历死循环
2.拓扑排序(有向无环图)

public class Sort {
    List<List<Integer>> keys; //每一个坐标都有一个可以走到的点，用一个链表维护
    int[] visit; //当前坐标位置访问状态 0未开始 1进行中 2结束
    boolean judge = true; //是否满足有向无环图
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        keys = new ArrayList<>();
        visit = new int[numCourses];//初始化
        for (int i = 0; i < numCourses; i++) {
            keys.add(new ArrayList<>());//numCourses个坐标对应numCourses个链表
        }
        for (int[] arr:prerequisites){
            keys.get(arr[1]).add(arr[0]);//将当前点位可以到达的坐标添加到链表
        }
        for (int i = 0; i < numCourses && judge; i++) {
            if(visit[i] == 0){//当前坐标未开始 从当前节点进入
                dfs(i);
            }
        }
        return judge;//返回是否满足拓扑排序
    }

    public void dfs(int num){
        visit[num] = 1;//将状态修改为进行中
        for (int v:keys.get(num)){
            if(visit[v] == 0){
                dfs(v);
                if(!judge){
                    return;//如果此时已经不满足拓扑排序规则直接return
                }
            }else if(visit[v] == 1){//拓扑排序走到了自己 说明形成了环不满足规则将标志位改为false
                judge = false;
                return;
            }
        }
        visit[num] = 2;
    }
}

3.前缀树

定义前缀树

class Trie{
    public Trie[] children;
    public boolean isEnd;
    public Trie(){
        children = new Trie[n] //n为需要的长度
        isEnd = false;
    }
    // 向字典树中插入单词
    public void insert(String word) {
        TrieNode node = this;
        // 遍历单词中的每个字符
        for (char c : word.toCharArray()) {
            // 计算字符在字典树中的索引
            int index = c - 'a';
            // 如果当前节点没有子节点，创建新的子节点
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            // 移动到子节点
            node = node.children[index];
        }
        // 设置当前节点为单词的结尾
        node.isEnd = true;
    }
}

面试150题-链表

📕文章题目选自LeetCode面试150题-链表
😊该文章内容基于作者本人思考总结，如有错误欢迎指正
🏠题单地址：https://leetcode.cn/studyplan/top-interview-150/

链表

LeetCode150-环形链表-LC141

/**
 * @ProjectName: Mounts
 * @Description: 环形链表
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/4 12:47
 * @Email: lihh53453@hundsun.com
 * 处理环形问题只需要考虑使用快慢指针 当相遇的时候一定有环
 * 但一定要注意循环的结束位置
 */
public class LC141 {
    public boolean hasCycle(Node head) {
        if (head == null || head.next == null) {
            return false;
        }
        Node fast = head.next;
        Node slow = head;
        while(fast != slow){
            if(fast == null || fast.next == null){
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }
}

LeetCode150-合并两个有序链表-LC21

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/4 13:32
 * @Email: lihh53453@hundsun.com
 * @Description: 合并两个有序链表
 * list1 = list1.next; 保证节点能在l1上继续走
 * list2 = list2.next; 保证节点能在l2上继续走
 * 将两个值进行比较 决定下一个扩展的节点是哪一个
 * 最后必定有一个值剩余 将节点指向最后一个有值的节点即可
 */
public class LC21 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode temp = new ListNode();
        ListNode cur = temp;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if(list1 == null){
            cur.next = list2;
        }else {
            cur.next = list1;
        }
        return temp.next;
    }
}

LeetCode150-两数相加-LC2

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/4 13:32
 * @Email: lihh53453@hundsun.com
 * @Description: 合并两个有序链表
 * list1 = list1.next; 保证节点能在l1上继续走
 * list2 = list2.next; 保证节点能在l2上继续走
 * 将两个值进行比较 决定下一个扩展的节点是哪一个
 * 最后必定有一个值剩余 将节点指向最后一个有值的节点即可
 */
public class LC21 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode temp = new ListNode();
        ListNode cur = temp;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if(list1 == null){
            cur.next = list2;
        }else {
            cur.next = list1;
        }
        return temp.next;
    }
}

LeetCode150-随机链表的复制-LC138

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/4 14:04
 * @Email: lihh53453@hundsun.com
 * @Description: 随机链表的复制
 * 用一个map来保存当前节点和传入节点的关系 将其关联上
 * 如果map存在这个节点直接将其返回即可
 * 如果不存在则选择创建一个新的节点 并且向下拓展
 */
public class LC138 {
    Map<Node,Node> cache = new HashMap<>();
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        if(!cache.containsKey(head)){
            Node new_node = new Node(head.val);
            cache.put(head,new_node);
            new_node.next = copyRandomList(head.next);
            new_node.random = copyRandomList(head.random);
        }
        return cache.get(head);
    }
}

LeetCode150-反转链表II-LC92

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/4 14:59
 * @Email: lihh53453@hundsun.com
 * @Description:
 * 1 2 3 4 5
 * 2->4
 */
public class LC92 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1,head);
        ListNode start = dummy;
        for(int i = 0;i<left - 1;i++){
            start = start.next;
        }
        ListNode pre = null;
        ListNode cur = start.next;
        for(int i = 0;i < right - left;i++){// 2-4  -> 0-2 -> 2 循环两次
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        start.next.next = cur;
        start.next = pre;
        return dummy.next;
    }
}

LeetCode150-K 个一组翻转链表-LC25

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/4 15:25
 * @Email: lihh53453@hundsun.com
 * @Description: K 个一组翻转链表
 */
public class LC25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode temp = dummy;
        int n = 0;
        while(temp.next != null){
            temp = temp.next;
            n++;
        }
        ListNode p = dummy;
        ListNode pre = null;
        ListNode cur = dummy.next;
        for(;n>=k;n-=k){
            for(int i = 0;i < k ;i++){
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            ListNode new_start = p.next;
            p.next.next = cur;
            p.next = pre;
            p = new_start;
        }
        return dummy.next;
    }
}

反转链表总结

确定反转的四个变量

• 反转链表节点 cur

• 反转链表节点cur的前一个节点 pre 初始为null

• 反转链表前一个节点 p 初始为cur->pre

• 反转链表后的链表的下一个无关节点p.next

  反转逻辑

• 暂存cur.next节点为nxt

• 将当前节点cur指向pre

• 更新pre为cur

• 更新cur为next

  反转范围

  因为头节点也可能被操作 所以需要创造有个虚拟的头节点**dummy**

反转链表I

直接反转整个列表 循环条件为while(dummy.next != null)

反转链表II

1. 由于制定了范围 首先要确定起始位置 for(int i = 0;i < left - 1; i++) 这个循环一共会走left-1步
2. 此时节点p位置确定 cur位置初始化为p.next, pre初始化为null
3. 执行反转逻辑
4. 连接链表
   • 将p.next(反转后的尾节点).next指向cur(此时cur位于反转链表后的链表的下一个无关节点)
   • 将p.next指向反转后的链表的头节点 -> p.next = pre(pre此时位于反转后的新头节点)

K 个一组翻转链表

1. 首先确定节点个数 从节点个数中以k个节点为单位 依次循环链表 for(;n>=k;n-=k)

2. 在k个范围内初始化 以下三个值

   ListNode p = dummy;
   ListNode pre = null;
   ListNode cur = dummy.next;

3. 此时节点p位置确定 cur位置初始化为p.next, pre初始化为null

4. 执行反转逻辑

5. 连接链表

   • 将p.next进行保存 因为在下一轮中p需要更新为新的起始位置 ListNode new_start = p.next
   • 将p.next(反转后的尾节点).next指向cur(此时cur位于反转链表后的链表的下一个无关节点)
   • 将p.next指向反转后的链表的头节点 -> p.next = pre(pre此时位于反转后的新头节点)
   • 更新p p.next = new_start

LeetCode150-删除链表的倒数第 N 个结点-LC19

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/4 16:01
 * @Email: lihh53453@hundsun.com
 * @Description:
 * 使用快慢指针 先让快指针走n步
 * 然后两个节点同时出发
 * 当快指针走到最后一步的时候 此时两个节点只相隔n
 */
public class LC19 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        while(n-->0){
            fast = fast.next;
        }
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

LeetCode150-删除排序链表中的重复元素II-LC82

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/4 16:09
 * @Email: lihh53453@hundsun.com
 * @Description:
 */
public class LC82 {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p = dummy;
        while(p.next != null && p.next.next != null){
            if(p.next.val == p.next.next.val){
                int val = p.next.val;
                while(p.next != null && p.next.val == val){//循环覆盖操作
                    p.next = p.next.next;//覆盖操作
                }
            }else{
                p = p.next;//跳过 不采取行动
            }
        }
        return dummy.next;
    }
}

LeetCode150-旋转链表-LC61

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/4 16:21
 * @Email: lihh53453@hundsun.com
 * @Description: 旋转链表
 * 解题思路： 首先确定链表长度 
 *          拼接链表为环状
 *          平移头节点位置
 *          返回新头节点
 */
public class LC61 {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || k == 0 || head.next == null) return head;
        ListNode temp = head;
        int index = 1;
        while(temp.next != null){
            temp = temp.next;
            index++;
        }
        int add = index - k % index;//计算出需要平移多少位置
        if(index == add){
            return head;
        }
        temp.next = head;
        while(add-->0){
            temp = temp.next;
        }
        ListNode new_head = temp.next;
        temp.next = null;
        return new_head;
    }
}

LeetCode150-分隔链表-LC86

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/4 16:34
 * @Email: lihh53453@hundsun.com
 * @Description: 分隔链表
 * 将小于和大于该节点的节点保存在链表中 再将两个链表相连即可
 */
public class LC86 {
    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0);
        ListNode small_head = small;
        ListNode biger = new ListNode(0);
        ListNode biger_head = biger;
        while(head != null){
            if(head.val < x){
                small_head.next = head;
                small_head = small_head.next;
            }else{
                biger_head.next = head;
                biger_head = biger_head.next;
            }
            head = head.next;
        }
        biger_head.next = null;
        small_head.next = biger.next;
        return small.next;
    }
}

LeetCode150-LRU缓存-LC146

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/4 16:55
 * @Email: lihh53453@hundsun.com
 * @Description: LRU 缓存
 */
public class LC146 {
    private Map<Integer, LinkedNode> cache = new HashMap<Integer, LinkedNode>();
    private int size;
    private int capacity;
    private LinkedNode head, tail;

    public LC146(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部节点
        head = new LinkedNode();
        tail = new LinkedNode();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        LinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        LinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            LinkedNode newNode = new LinkedNode(key, value);
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                LinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(LinkedNode node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    private void removeNode(LinkedNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void moveToHead(LinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private LinkedNode removeTail() {
        LinkedNode res = tail.pre;
        removeNode(res);
        return res;
    }
}

class LinkedNode{
    public int key;
    public int value;
    public LinkedNode pre;
    public LinkedNode next;
    public LinkedNode(LinkedNode pre,LinkedNode next){
        this.pre = pre;
        this.next = next;
    }
    public LinkedNode(){}
    public LinkedNode(int _key, int _value) {key = _key; value = _value;}
}

总结

1. 要注意链表的创建 指针指向和定义
2. 成环时考虑拆解 快慢指针可以确定节点位置
3. 反转链表的四个变量

面试150题-栈

📕文章题目选自LeetCode面试150题-栈
😊该文章内容基于作者本人思考总结，如有错误欢迎指正
🏠题单地址：https://leetcode.cn/studyplan/top-interview-150/

栈

LeetCode150-有效的括号-LC20

/**
 * @ProjectName: Mounts
 * @Description: LeetCode150-有效的括号-LC20
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/3 16:01
 * @Email: lihh53453@hundsun.com
 */
public class LC20 {
    public boolean isValid(String s) {
        Map<Character,Character> map = new HashMap<Character,Character>(){{
            put(']','[');
            put('}','{');
            put(')','(');
        }};
        Deque<Character> queue = new LinkedList<>();
        for(char c:s.toCharArray()){
            if(map.containsKey(c)){
                if (queue.isEmpty() || queue.peek() != map.get(c)){
                    return false;
                }
                queue.pop();
            }else{
                /*
                [(]1722672830113
                [[, (]1722672830113
                 */
                queue.push(c); //添加到顶部
                //queue.add(c); 添加到末尾
                /*
                [(]1722672780704
                [(, []1722672780705
                [[]1722672780705
                []1722672780705
                 */
            }
            System.out.println(queue + String.valueOf(System.currentTimeMillis()));
        }
        return queue.isEmpty();
    }

    public static void main(String[] args) {
        LC20 lc20 = new LC20();
        lc20.isValid("([)]");
    }
}

LeetCode150-简化路径-LC71

/**
 * @ProjectName: Mounts
 * @Description: LeetCode150-简化路径-LC71
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/3 16:41
 * @Email: lihh53453@hundsun.com
 */
public class LC71 {
    public String simplifyPath(String path) {
        String[] split = path.split("/");
        Deque<String> queue = new LinkedList<>();
        for(String str:split){
            if("..".equals(str)){
                if(!queue.isEmpty()){
                    queue.pollLast();
                }
            }else if(!str.isEmpty() && !".".equals(str)){
                queue.addLast(str);
            }
            /*
            这样的写法会导"/.."的情况 不满足条件"..".equals(str) && !queue.isEmpty() 而走到!str.isEmpty() && !".".equals(str)
            此时满足条件 那么queue就会添加".."
             */
//            if("..".equals(str) && !queue.isEmpty()){
//                queue.pollLast();
//            }else if(!str.isEmpty() && !".".equals(str)){
//                queue.addLast(str);
//            }

        }
        StringBuilder stringBuilder = new StringBuilder();
        if (queue.isEmpty()) {
            stringBuilder.append('/');
        } else {
            while (!queue.isEmpty()) {
                stringBuilder.append('/');
                stringBuilder.append(queue.pollFirst());
            }
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        LC71 lc71 = new LC71();
        lc71.simplifyPath("/..");
    }
}

LeetCode150-最小栈-LC155

/**
 * @ProjectName: Mounts
 * @Description: LeetCode150-最小栈-LC155
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/3 17:07
 * @Email: lihh53453@hundsun.com
 * 有关栈的简单实现
 */
public class LC155 {
    Node root;
    public LC155() {
        this.root = new Node();
    }

    public void push(int val) {
        //当前节点保存root之前的状态 例如next和min 相当于备份
        //先备份node 在更新root
        Node node = new Node(val,root.next);
        node.min = root.min;
        root.min = Math.min(root.min,val);
        root.next = node;
    }

    public void pop() {
        Node cur = root.next;
        if (cur.val == root.min) {
            root.min = cur.min;
            //cur节点保证进来之前root的min值
        }
        root.next = cur.next;
        cur.next = null;

    }

    public int top() {
        return root.next.val;
    }

    public int getMin() {
        return root.min;
    }

    public static void main(String[] args) {
        LC155 minStack = new LC155();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        minStack.getMin();   //--> 返回 -3.
        minStack.pop();
        minStack.top();      //--> 返回 0.
        minStack.getMin();   //--> 返回 -2.
    }
}

class Node{
    Node next;
    int min;
    int val;
    public Node(Node next){
        this.next = next;
    }
    public Node(int val,Node next){
        this.val = val;
        this.next = next;
    }
    public Node(){
        this.min = Integer.MAX_VALUE;
    }
}

LeetCode150-逆波兰表达式求值-LC150

/**
 * @ProjectName: Mounts
 * @Description: LC150-逆波兰表达式求值LC150
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/3 17:38
 * @Email: lihh53453@hundsun.com
 */
public class LC150 {

    public int evalRPN(String[] tokens) {
        Set<String> set = new HashSet<>();
        set.add("*");
        set.add("-");
        set.add("+");
        set.add("/");
        Deque<Integer> queue = new LinkedList<>();
        for(String str:tokens){
            if(set.contains(str)){
                int num2 = queue.pop();
                int num1 = queue.pop();
                switch (str){
                    case "+":
                        queue.push(num1 + num2);
                        break;
                    case "-":
                        queue.push(num1 - num2);
                        break;
                    case "*":
                        queue.push(num1 * num2);
                        break;
                    case "/":
                        queue.push(num1 / num2);
                        break;
                }
            }else{
                queue.push(Integer.parseInt(str));
            }
        }
        return queue.pop();
    }
}

LeetCode150-基本计算器-LC224

/**
 * @ProjectName: Mounts
 * @Author: DSXRIIIII
 * @CreateDate: 2024/8/3 19:17
 * @Email: lihh53453@hundsun.com
 * @Description:
 * 定义一个栈用来记录当前括号内的数字是否要变成负数
 * 例如-(1 + 2 + 3) --> -1 - 2 - 3
 * sign 的作用即是 保持同一个括号内的数字 去掉括号后的数字要转换
 * 并且该题目也有多位数相加 所以还要添加一个循环
 * (1 + 2 - (1 + 2))
 * 分析：
 *     1.遇到（括号 将当前sign值添加到队列
 *     2.遇到 数字1 res+=sign*1 此时sign为1
 *     3.遇到 + 保持最新的sign peek操作不会将值弹出只做检查
 *     4.遇到 数字2 res+=sign*2 此时sign为1
 *     5.遇到 - 反转此时的sign值 -ops.peek() 将此时的sign值反转
 *     6.遇到（括号 将当前sign值添加到队列 此时sign值为-1 意味着括号内的所有加减号都要反转
 *     7.遇到 数字1 res+=sign*1 此时sign为-1 所以是减操作
 *     8.遇到 数字2 res+=sign*1 此时sign为-1 所以是减操作
 *     9.遇到）括号 将当前sign值移除队列 最新的sign值不会对产生数字影响
 *     10.遇到）括号 将当前sign值移除队列 最新的sign值不会对产生数字影响
 */    
public class LC224 {
    public int calculate(String s) {
        Deque<Integer> ops = new LinkedList<>();
        int sign = 1;
        ops.push(1);
        int index = 0;
        int res = 0;
        while(index < s.length()){
            if(s.charAt(index) == ' '){
                index++;
            }else if(s.charAt(index) == '('){
                ops.push(sign);
                index++;
            }else if(s.charAt(index) == ')'){
                ops.pop();
                index++;
            }else if(s.charAt(index) == '+'){
                sign = ops.peek();
                index++;
            }else if(s.charAt(index) == '-'){
                sign = -ops.peek();
                index++;
            }else{
                int num = 0;
                while(index < s.length() && Character.isDigit(s.charAt(index))){
                    num = num * 10 + s.charAt(index) - '0';
                    index++;
                }
                res += sign * num;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String s = " 2-1 + 2 ";
        LC224 lc224 = new LC224();
        lc224.calculate(s);
    }
}

总结

栈(JAVA)一律采用双端队列Deque
实现：Deque