自学内容网 自学内容网

LeetCode 129, 133, 136


129. 求根节点到叶节点数字之和

题目链接

129. 求根节点到叶节点数字之和

标签

树 深度优先搜索 二叉树

思路

由于本题需要 从 根节点 遍历到 叶子节点(无子节点的节点叫做叶子节点),所以可以使用 深度优先搜索 的思想:每次遍历一个节点就计算 当前的路径(从根节点到当前节点)所表示的数字,然后将其传递给它的两棵子树,对 在两棵子树求得的所有路径之和 求和 并 返回。

像这样从 根节点叶子节点 遍历,如果遍历到叶子节点,则返回 从 根节点 到 此叶子节点 的路径所表示的数字。此外,可能会遇到一个当前节点为 null 的情况,此时返回 0 作为路径即可。

代码

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    // curr 是当前遍历的节点,currNum 是从根节点到 curr 的路径所表示的数字
    private int dfs(TreeNode curr, int currNum) {
        if (curr == null) { // 如果 curr 为 null
            return 0; // 则返回 0
        }
        int num = currNum * 10 + curr.val; // 计算从根节点到 curr 的路径所表示的数字
        if (curr.left == null && curr.right == null) { // 如果到叶子节点
            return num; // 则返回从根节点到这个叶子节点的路径所表示的数字
        }
        return dfs(curr.left, num) // 遍历左子树,求左子树中的所有路径之和
                + dfs(curr.right, num); // 遍历右子树,求右子树的所有路径之和
    }
}

133. 克隆图

题目链接

133. 克隆图

标签

深度优先搜索 广度优先搜索 图 哈希表

思路

本题和 LeetCode 138. 随机链表的复制 类似,使用的方法完全一样,都是 建立旧节点与新节点的映射,不过与之不同的一点是:138 题中链表的结构没有这么复杂,而本题将基础链表中的 next 指针变成了一个 neighbors 指针集合,这就意味着本题无法像 138 题一样遍历链表来为新节点的属性赋值,而需要使用别的遍历方式——深度优先搜索(本方式复用了 cloneGraph() 方法,求旧节点所对应的新节点):

  • 如果旧节点为 null,则返回 null
  • 如果已经建立过 旧节点 和 新节点 的映射,则直接返回新节点。
  • 如果没有建立 旧节点 和 新节点 的映射,则需要构建新节点,分为以下三步:
    1. 创建新节点:给新节点的 val 属性赋值。
    2. 保存 旧节点 和 新节点 的映射。
    3. 给新节点的 neighbors 属性赋值:构建新节点之间的 neighbor 关系。

注意:构建新节点的第二、三步不能调换顺序。因为本节点的 neighborneighbor 是本节点,这两个节点之间会 互相获取对方的新节点,而 要返回本节点的新节点就需要先获取对方节点的新节点,从而进入死循环。

代码

class Solution {
// 给定一个旧节点,返回其对应的新节点
    public Node cloneGraph(Node oldNode) {
        if (oldNode == null) { // 如果 旧节点 为 null
            return null; // 则返回 null
        }

        if (mapper.containsKey(oldNode)) { // 如果已经建立过 旧节点 和 新节点 的映射
            return mapper.get(oldNode); // 则直接返回 旧节点 对应的 新节点
        }

        // 构建 新节点,给新节点的 neighbors 链表初始化指定的大小,避免 后续扩容 浪费时间
        Node newNode = new Node(oldNode.val, new ArrayList<>(oldNode.neighbors.size()));
        mapper.put(oldNode, newNode); // 先保存 旧节点 和 新节点 的映射
        for (Node neighbor : oldNode.neighbors) { // 然后再构建新节点之间的 neighbor 关系
            // 按照顺序寻找 新节点 对应的 新 neighbor
            newNode.neighbors.add(cloneGraph(neighbor));
        }
        return newNode; // 返回新节点
    }
    // 映射 旧节点 和 新节点 的映射,key 为 旧节点,value 为 新节点
    private Map<Node, Node> mapper = new HashMap<>();
}

136. 只出现一次的数字

题目链接

136. 只出现一次的数字

标签

位运算 数组

思路

异或的定义是:相同为假,不同为假。例如对于两个二进制数 0101, 1001,它们异或的结果为 0101 ^ 1001 = 1100

本题考查了一个位运算的知识:对两个数使用 异或 操作得到的结果如下:

  • 如果两个数相等,则结果为 0。这是因为两个数相等代表其二进制数相等,而相同为假,所以异或的结果全是 0,从而两个相等的数的异或结果为 0
  • 如果是 0 ^ 某个数,则结果为 某个数。这种情况举个例子更好理解:例如对于 0000, 1101,它们异或的结果为 1101,恰好与这个数相等。
  • 对于其他情况,结果通常没有具体意义。

多个数进行异或操作 就是 复合了多个 两数异或 的结果,例如 0011 ^ 1100 ^ 0011 = 0 ^ 1100 = 1100

所以可以遍历数组,对所有数使用异或操作,出现两次的数都抵消成 0 了,出现一次的数最终和 0 进行异或操作,得到它本身。

代码

class Solution {
    public int singleNumber(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }
}

原文地址:https://blog.csdn.net/qq_61350148/article/details/140604559

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!