做网站大型,品牌微信网站开发,怎样设计手机网站建设,16岁0元开网店赚钱软件文章目录 129. 求根节点到叶节点数字之和题目链接标签思路代码 133. 克隆图题目链接标签思路代码 136. 只出现一次的数字题目链接标签思路代码 129. 求根节点到叶节点数字之和
题目链接
129. 求根节点到叶节点数字之和
标签
树 深度优先搜索 二叉树
思路
由于本题需要 从… 文章目录 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 为 nullreturn 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。如果已经建立过 旧节点 和 新节点 的映射则直接返回新节点。如果没有建立 旧节点 和 新节点 的映射则需要构建新节点分为以下三步 创建新节点给新节点的 val 属性赋值。保存 旧节点 和 新节点 的映射。给新节点的 neighbors 属性赋值构建新节点之间的 neighbor 关系。
注意构建新节点的第二、三步不能调换顺序。因为本节点的 neighbor 的 neighbor 是本节点这两个节点之间会 互相获取对方的新节点而 要返回本节点的新节点就需要先获取对方节点的新节点从而进入死循环。
代码
class Solution {// 给定一个旧节点返回其对应的新节点public Node cloneGraph(Node oldNode) {if (oldNode null) { // 如果 旧节点 为 nullreturn 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 关系// 按照顺序寻找 新节点 对应的 新 neighbornewNode.neighbors.add(cloneGraph(neighbor));}return newNode; // 返回新节点}// 映射 旧节点 和 新节点 的映射key 为 旧节点value 为 新节点private MapNode, 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;}
}
