【图解算法数据结构】搜索与回溯算法篇 + Java代码实现

简介: 【图解算法数据结构】搜索与回溯算法篇 + Java代码实现

@[toc]


一、矩阵中的路径

在这里插入图片描述

public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, words, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) {
            return false;
        }
        if (k == word.length - 1) {
            return true;
        }
        board[i][j] = '\0';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
                dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }
AI 代码解读

二、机器人的运动范围

在这里插入图片描述

    int m, n, k;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        this.m = m; this.n = n; this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }
    public int dfs(int i, int j, int si, int sj) {
        if(i >= m || j >= n || k < si + sj || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
    }
AI 代码解读

三、树的子结构

在这里插入图片描述

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    boolean recur(TreeNode A, TreeNode B) {
        if(B == null) {
            return true;
        }
        if(A == null || A.val != B.val) {
            return false;
        }
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
AI 代码解读

四、二叉树的镜像

在这里插入图片描述

    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        TreeNode tmp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(tmp);
        return root;
    }
AI 代码解读

五、对称的二叉树

在这里插入图片描述

    public boolean isSymmetric(TreeNode root) {
        return root == null || recur(root.left, root.right);
    }
    boolean recur(TreeNode L, TreeNode R) {
        if(L == null && R == null) {
            return true;
        }
        if(L == null || R == null || L.val != R.val) {
            return false;
        }
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
AI 代码解读

六、从上到下打印二叉树 I

在这里插入图片描述

    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        List<TreeNode> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        int[] arr = new int[list.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i).val;
        }
        return arr;
    }
AI 代码解读

七、从上到下打印二叉树 II

在这里插入图片描述

    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) {
            queue.add(root);
        }
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(tmp);
        }
        return res;
    }
AI 代码解读

八、从上到下打印二叉树 III

在这里插入图片描述

    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) {
            queue.add(root);
        }
        while(!queue.isEmpty()) {
            LinkedList<Integer> tmp = new LinkedList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if(res.size() % 2 == 0) {
                    tmp.addLast(node.val);
                } else {
                    tmp.addFirst(node.val);
                }
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(tmp);
        }
        return res;
    }
AI 代码解读

九、二叉树中和为某一值的路径

在这里插入图片描述
在这里插入图片描述

    List<List<Integer>> res;

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) {
            return new ArrayList<>();
        }
        res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        list.add(root.val);
        dfs(root, list, root.val, target);
        return res;
    }

    public void dfs(TreeNode node, List<Integer> list, int sum, int target) {
        if (sum == target && node.left == null && node.right == null) {
            res.add(new ArrayList<>(list));
        }
        if (node.left != null) {
            list.add(node.left.val);
            dfs(node.left, list, sum + node.left.val, target);
            list.remove(list.size() - 1);
        }
        if (node.right != null) {
            list.add(node.right.val);
            dfs(node.right, list, sum + node.right.val, target);
            list.remove(list.size() - 1);
        }
    }
AI 代码解读

十、二叉搜索树与双向链表

在这里插入图片描述
在这里插入图片描述

    Node pre, head;
    public Node treeToDoublyList(Node root) {
        if(root == null) {
            return null;
        }
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    void dfs(Node cur) {
        if(cur == null) {
            return;
        }
        dfs(cur.left);
        if(pre != null) {
            pre.right = cur;
        } else {
            head = cur;
        }
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
AI 代码解读

十一、序列化二叉树

在这里插入图片描述

    public String serialize(TreeNode root) {
        if (root == null) {
            return "[]";
        }
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            } else {
                res.append("null,");
            }
        }
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

    public TreeNode deserialize(String data) {
        if (data.equals("[]")) {
            return null;
        }
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (!vals[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.left);
            }
            i++;
            if (!vals[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
AI 代码解读

十二、字符串的排列

在这里插入图片描述

    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    void dfs(int x) {
        if(x == c.length - 1) {
            res.add(String.valueOf(c));      // 添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++) {
            if(set.contains(c[i])) {
                continue; // 重复,因此剪枝
            }
            set.add(c[i]);
            swap(i, x);                      // 交换,将 c[i] 固定在第 x 位
            dfs(x + 1);                      // 开启固定第 x + 1 位字符
            swap(i, x);                      // 恢复交换
        }
    }
    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
AI 代码解读

十三、二叉搜索树的第 k 大节点

在这里插入图片描述

    int res, k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs(root.right);
        if(k == 0) {
            return;
        }
        if(--k == 0) {
            res = root.val;
        }
        dfs(root.left);
    }
AI 代码解读

十四、二叉树的深度

在这里插入图片描述

    public int maxDepth(TreeNode root) {
        return maxDepth(root, 1);
    }

    public int maxDepth(TreeNode node, int curHeight) {
        if (node == null) {
            return curHeight - 1;
        }
        return Math.max(maxDepth(node.left, curHeight + 1), maxDepth(node.right, curHeight + 1));
    }
AI 代码解读

--

十五、平衡二叉树

在这里插入图片描述

    boolean isBalanced = true;

    public boolean isBalanced(TreeNode root) {
        maxDepth(root);
        return isBalanced;
    }

    public int maxDepth(TreeNode root) {
        return maxDepth(root, 1);
    }

    public int maxDepth(TreeNode node, int curHeight) {
        if (node == null || !isBalanced) {
            return curHeight - 1;
        }
        int lh = maxDepth(node.left, curHeight + 1);
        int rh = maxDepth(node.right, curHeight + 1);
        if (Math.abs(lh - rh) > 1) {
            isBalanced = false;
        }
        return Math.max(lh, rh);
    }
AI 代码解读

十六、求 1 + 2 + … + n

在这里插入图片描述

    public int sumNums(int n) {
        return dfs(n, 0);
    }

    public int dfs(int n, int res) {
        if (n > 0) {
            return dfs(n - 1, res + n);
        }
        return res;
    }
AI 代码解读

十七、二叉搜索树的最近公共祖先

在这里插入图片描述

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val > q.val) { // 保证 p.val < q.val
            TreeNode tmp = p;
            p = q;
            q = tmp;
        }
        while(root != null) {
            if(root.val < p.val) // p,q 都在 root 的右子树中
            {
                root = root.right; // 遍历至右子节点
            } else if(root.val > q.val) // p,q 都在 root 的左子树中
            {
                root = root.left; // 遍历至左子节点
            } else {
                break;
            }
        }
        return root;
    }
AI 代码解读

十八、二叉树的最近公共祖先

在这里插入图片描述

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null && right == null) {
            return null; // 1.
        }
        if(left == null) {
            return right; // 3.
        }
        if(right == null) {
            return left; // 4.
        }
        return root; // 2. if(left != null and right != null)
    }
AI 代码解读
目录
打赏
0
0
0
0
116
分享
相关文章
接替此文【下篇-服务端+后台管理】优雅草蜻蜓z系统JAVA版暗影版为例-【蜻蜓z系列通用】-2025年全新项目整合搭建方式-这是独立吃透代码以后首次改变-独立PC版本vue版搭建教程-优雅草卓伊凡
接替此文【下篇-服务端+后台管理】优雅草蜻蜓z系统JAVA版暗影版为例-【蜻蜓z系列通用】-2025年全新项目整合搭建方式-这是独立吃透代码以后首次改变-独立PC版本vue版搭建教程-优雅草卓伊凡
160 96
接替此文【下篇-服务端+后台管理】优雅草蜻蜓z系统JAVA版暗影版为例-【蜻蜓z系列通用】-2025年全新项目整合搭建方式-这是独立吃透代码以后首次改变-独立PC版本vue版搭建教程-优雅草卓伊凡
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
近端策略优化(PPO)是深度强化学习中高效的策略优化方法,广泛应用于大语言模型的RLHF训练。PPO通过引入策略更新约束机制,平衡了更新幅度,提升了训练稳定性。其核心思想是在优势演员-评论家方法的基础上,采用裁剪和非裁剪项组成的替代目标函数,限制策略比率在[1-ϵ, 1+ϵ]区间内,防止过大的策略更新。本文详细探讨了PPO的基本原理、损失函数设计及PyTorch实现流程,提供了完整的代码示例。
133 10
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
如何在 Java 代码中使用 JSqlParser 解析复杂的 SQL 语句?
大家好,我是 V 哥。JSqlParser 是一个用于解析 SQL 语句的 Java 库,可将 SQL 解析为 Java 对象树,支持多种 SQL 类型(如 `SELECT`、`INSERT` 等)。它适用于 SQL 分析、修改、生成和验证等场景。通过 Maven 或 Gradle 安装后,可以方便地在 Java 代码中使用。
306 11
利用 Java 代码获取淘宝关键字 API 接口
在数字化商业时代,精准把握市场动态与消费者需求是企业成功的关键。淘宝作为中国最大的电商平台之一,其海量数据中蕴含丰富的商业洞察。本文介绍如何通过Java代码高效、合规地获取淘宝关键字API接口数据,帮助商家优化产品布局、制定营销策略。主要内容包括: 1. **淘宝关键字API的价值**:洞察用户需求、优化产品标题与详情、制定营销策略。 2. **获取API接口的步骤**:注册账号、申请权限、搭建Java开发环境、编写调用代码、解析响应数据。 3. **注意事项**:遵守法律法规与平台规则,处理API调用限制。 通过这些步骤,商家可以在激烈的市场竞争中脱颖而出。
深入理解Java中synchronized三种使用方式:助您写出线程安全的代码
`synchronized` 是 Java 中的关键字,用于实现线程同步,确保多个线程互斥访问共享资源。它通过内置的监视器锁机制,防止多个线程同时执行被 `synchronized` 修饰的方法或代码块。`synchronized` 可以修饰非静态方法、静态方法和代码块,分别锁定实例对象、类对象或指定的对象。其底层原理基于 JVM 的指令和对象的监视器,JDK 1.6 后引入了偏向锁、轻量级锁等优化措施,提高了性能。
79 3
java日常开发中如何写出优雅的好维护的代码
代码可读性太差,实际是给团队后续开发中埋坑,优化在平时,没有那个团队会说我专门给你一个月来优化之前的代码,所以在日常开发中就要多注意可读性问题,不要写出几天之后自己都看不懂的代码。
79 2
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
Java 中的注解(Annotations):代码中的 “元数据” 魔法
Java注解是代码中的“元数据”标签,不直接参与业务逻辑,但在编译或运行时提供重要信息。本文介绍了注解的基础语法、内置注解的应用场景,以及如何自定义注解和结合AOP技术实现方法执行日志记录,展示了注解在提升代码质量、简化开发流程和增强程序功能方面的强大作用。
151 5
Java 内存管理与优化:掌控堆与栈,雕琢高效代码
Java内存管理与优化是提升程序性能的关键。掌握堆与栈的运作机制,学习如何有效管理内存资源,雕琢出更加高效的代码,是每个Java开发者必备的技能。
98 5
Java中的Lambda表达式:简化代码的现代魔法
在Java 8的发布中,Lambda表达式的引入无疑是一场编程范式的革命。它不仅让代码变得更加简洁,还使得函数式编程在Java中成为可能。本文将深入探讨Lambda表达式如何改变我们编写和维护Java代码的方式,以及它是如何提升我们编码效率的。

热门文章

最新文章