上接：【题解】—— LeetCode一周小结13
2024.4
1.故障键盘
题目链接：2810. 故障键盘
你的笔记本键盘存在故障，每当你在上面输入字符 ‘i’ 时，它会反转你所写的字符串。而输入其他字符则可以正常工作。
给你一个下标从 0 开始的字符串 s ，请你用故障键盘依次输入每个字符。
返回最终笔记本屏幕上输出的字符串。
示例 1：
输入：s = “string”
输出：“rtsng”
解释：
输入第 1 个字符后，屏幕上的文本是：“s” 。
输入第 2 个字符后，屏幕上的文本是：“st” 。
输入第 3 个字符后，屏幕上的文本是：“str” 。
因为第 4 个字符是 ‘i’ ，屏幕上的文本被反转，变成 “rts” 。
输入第 5 个字符后，屏幕上的文本是：“rtsn” 。
输入第 6 个字符后，屏幕上的文本是： “rtsng” 。
因此，返回 “rtsng” 。
示例 2：
输入：s = “poiinter”
输出：“ponter”
解释：
输入第 1 个字符后，屏幕上的文本是：“p” 。
输入第 2 个字符后，屏幕上的文本是：“po” 。
因为第 3 个字符是 ‘i’ ，屏幕上的文本被反转，变成 “op” 。
因为第 4 个字符是 ‘i’ ，屏幕上的文本被反转，变成 “po” 。
输入第 5 个字符后，屏幕上的文本是：“pon” 。
输入第 6 个字符后，屏幕上的文本是：“pont” 。
输入第 7 个字符后，屏幕上的文本是：“ponte” 。
输入第 8 个字符后，屏幕上的文本是：“ponter” 。
因此，返回 “ponter” 。
提示：
1 <= s.length <= 100
s 由小写英文字母组成
s[0] != ‘i’
题解：
方法：双端队列
把反转看成是往字符串的头部添加字符。
如果当前处于往字符串尾部添加字符的状态，那么遇到 i 后，改成往字符串头部添加字符的状态。
如果当前处于往字符串头部添加字符的状态，那么遇到 i 后，改成往字符串尾部添加字符的状态。
class Solution { public String finalString(String s) { Deque<Character> q = new ArrayDeque<>(); boolean tail = true; for (char c : s.toCharArray()) { if (c == 'i') { tail = !tail; // 修改添加方向 } else if (tail) { q.addLast(c); // 加尾部 } else { q.addFirst(c); // 加头部 } } StringBuilder ans = new StringBuilder(); for (char c : q) { ans.append(c); } if (!tail) { ans.reverse(); } return ans.toString(); } }
2.所有可能的真二叉树
题目链接：894. 所有可能的真二叉树
给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。
答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。
真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。
示例 1：
输入：n = 7
输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
示例 2：
输入：n = 3
输出：[[0,0,0]]
提示：
1 <= n <= 20
题解：
方法：动态规划
如果 n 是偶数，返回空列表。
如果 n 是奇数，返回 f[(n+1)/2]
class Solution { // 创建一个长度为11的泛型数组列表数组f，用于存储各个节点数对应的可能的满二叉树列表 private static final List<TreeNode>[] f = new ArrayList[11]; // 静态代码块用于初始化f数组 static { // 使用Arrays.setAll方法，将f数组中的每个元素初始化为一个空的ArrayList<TreeNode> Arrays.setAll(f, i -> new ArrayList<>()); // 由于只有1个节点的满二叉树只有一种情况，因此初始化f[1]为一个含有一个根节点的TreeNode列表 f[1].add(new TreeNode()); // 循环遍历计算f数组中其他元素的值 for (int i = 2; i < f.length; i++) { // 计算 f[i] // 枚举左子树的叶子节点数j，j从1遍历到i-1 for (int j = 1; j < i; j++) { // 枚举左子树叶子数 // 遍历f[j]中的每个左子树节点 for (TreeNode left : f[j]) { // 枚举左子树 // 遍历f[i-j]中的每个右子树节点 for (TreeNode right : f[i - j]) { // 枚举右子树 // 将左右子树连接到新的根节点上，构造一个新的满二叉树，并添加到f[i]中 f[i].add(new TreeNode(0, left, right)); } } } } } // 定义一个方法，根据给定的节点数n返回可能的满二叉树列表 public List<TreeNode> allPossibleFBT(int n) { // 如果n是奇数，则直接返回f[n]，因为对应的可能的满二叉树列表已经计算好了 // 如果n是偶数，则返回空列表 return f[n % 2 > 0 ? (n + 1) / 2 : 0]; } }
3.找出克隆二叉树中的相同节点
题目链接：1379. 找出克隆二叉树中的相同节点
给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标节点 target。
其中，克隆树 cloned 是原始树 original 的一个 副本 。
请找出在树 cloned 中，与 target 相同 的节点，并返回对该节点的引用（在 C/C++ 等有指针的语言中返回 节点指针，其他语言返回节点本身）。
注意：你 不能 对两棵二叉树，以及 target 节点进行更改。只能 返回对克隆树 cloned 中已有的节点的引用。
示例 1:
输入: tree = [7,4,3,null,null,6,19], target = 3
输出: 3
解释: 上图画出了树 original 和 cloned。target 节点在树 original 中，用绿色标记。答案是树 cloned
中的黄颜色的节点（其他示例类似）。
示例 2:
输入: tree = [7], target = 7
输出: 7
示例 3:
输入: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
输出: 4
提示：
树中节点的数量范围为 [1, 104] 。
同一棵树中，没有值相同的节点。
target 节点是树 original 中的一个节点，并且不会是 null 。
进阶：如果树中允许出现值相同的节点，将如何解答？
题解：
方法：深度优先搜索 递归
如果 original 是空节点，返回空。
如果 original=target（注意这里比较的是节点，不是节点值），说明我们找到了对应的节点，返回 cloned。
否则递归 original和 cloned 的左子树，如果返回值 leftRes 不为空，说明 target 在左子树中，返回 leftRes。
否则递归 original和 cloned 的右子树，由于题目保证 target一定在二叉树中，所以直接返回递归右子树的返回值。
class Solution { // 递归函数，用于在克隆树中查找与目标节点相同的节点 public TreeNode getTargetCopy(TreeNode original, TreeNode cloned, TreeNode target) { // 如果原始树为空或者当前节点为目标节点，则返回克隆树当前节点 if (original == null || original == target) { return cloned; } // 递归遍历左子树，查找目标节点 TreeNode leftRes = getTargetCopy(original.left, cloned.left, target); // 如果在左子树中找到了目标节点，则直接返回结果，无需再递归右子树 if (leftRes != null) { return leftRes; } // 否则，继续在右子树中递归查找目标节点 return getTargetCopy(original.right, cloned.right, target); } }
4.有向无环图中一个节点的所有祖先
给你一个正整数 n ，它表示一个 有向无环图 中节点的数目，节点编号为 0 到 n - 1 （包括两者）。
给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi] 表示图中一条从 fromi 到 toi 的单向边。
请你返回一个数组 answer，其中 answer[i]是第 i 个节点的所有 祖先 ，这些祖先节点 升序 排序。
如果 u 通过一系列边，能够到达 v ，那么我们称节点 u 是节点 v 的 祖先 节点。
示例 1：
输入：n = 8, edgeList =
[[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]
输出：[[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]
解释：
上图为输入所对应的图。
- 节点 0 ，1 和 2 没有任何祖先。
- 节点 3 有 2 个祖先 0 和 1 。
- 节点 4 有 2 个祖先 0 和 2 。
- 节点 5 有 3 个祖先 0 ，1 和 3 。
- 节点 6 有 5 个祖先 0 ，1 ，2 ，3 和 4 。
- 节点 7 有 4 个祖先 0 ，1 ，2 和 3 。
示例 2：
输入：n = 5, edgeList =
[[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
输出：[[],[0],[0,1],[0,1,2],[0,1,2,3]]
解释：
上图为输入所对应的图。
- 节点 0 没有任何祖先。
- 节点 1 有 1 个祖先 0 。
- 节点 2 有 2 个祖先 0 和 1 。
- 节点 3 有 3 个祖先 0 ，1 和 2 。
- 节点 4 有 4 个祖先 0 ，1 ，2 和 3 。
提示：
1 <= n <= 1000
0 <= edges.length <= min(2000, n * (n - 1) / 2)
edges[i].length == 2
0 <= fromi, toi <= n - 1
fromi != toi
图中不会有重边。
图是 有向 且 无环 的。
题解：
方法：BFS
class Solution { private int n; private List<Integer>[] g; private List<List<Integer>> ans; // 主函数，返回每个节点的祖先列表 public List<List<Integer>> getAncestors(int n, int[][] edges) { // 初始化邻接表和结果列表 g = new List[n]; this.n = n; Arrays.setAll(g, i -> new ArrayList<>()); ans = new ArrayList<>(); for (int i = 0; i < n; ++i) { ans.add(new ArrayList<>()); } // 构建有向图 for (var e : edges) { g[e[0]].add(e[1]); } // 遍历每个节点，进行广度优先搜索 for (int i = 0; i < n; ++i) { bfs(i); } return ans; } // 广度优先搜索，找到每个节点的祖先 private void bfs(int s) { Deque<Integer> q = new ArrayDeque<>(); q.offer(s); boolean[] vis = new boolean[n]; vis[s] = true; // 开始广度优先搜索 while (!q.isEmpty()) { int i = q.poll(); // 遍历节点 i 的邻居节点 for (int j : g[i]) { // 如果邻居节点未被访问过，则标记为已访问，并将其加入队列 if (!vis[j]) { vis[j] = true; q.offer(j); // 将节点 j 的祖先列表中加入节点 s ans.get(j).add(s); } } } } }
5.节点与其祖先之间的最大差值
题目链接：1026. 节点与其祖先之间的最大差值
给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。
（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
示例 1：
输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释：
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。
示例 2：
输入：root = [1,null,2,null,0,3]
输出：3
提示：
树中的节点数在 2 到 5000 之间。
0 <= Node.val <= 105
题解：
方法：dfs
深度优先搜索函数 dfs 采用递归的方式遍历二叉树的每个节点。对于每个节点，计算当前节点值与最小值、最大值的差的绝对值的最大值，并更新结果变量 ans。然后递归遍历左子树和右子树，并在递归过程中更新最小值和最大值。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans; // 主函数，返回二叉树中任意两个节点值的差的绝对值的最大值 public int maxAncestorDiff(TreeNode root) { // 初始化结果变量 ans = 0; // 深度优先搜索，记录每个节点的最大值和最小值，并更新结果变量 dfs(root, root.val, root.val); // 返回结果 return ans; } // 深度优先搜索函数，递归遍历二叉树的每个节点 private void dfs(TreeNode root, int mi, int mx) { // 如果当前节点为空，直接返回 if (root == null) { return; } // 计算当前节点值与最小值、最大值的差的绝对值的最大值 int x = Math.max(Math.abs(mi - root.val), Math.abs(mx - root.val)); // 更新结果变量 ans = Math.max(ans, x); // 更新最小值和最大值 mi = Math.min(mi, root.val); mx = Math.max(mx, root.val); // 递归遍历左子树和右子树 dfs(root.left, mi, mx); dfs(root.right, mi, mx); } }
6.树节点的第 K 个祖先
题目链接：1483. 树节点的第 K 个祖先
给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。
树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。
实现 TreeAncestor 类：
- TreeAncestor（int n， int[] parent） 对树和父数组中的节点数初始化对象。
- getKthAncestor(int node, int k) 返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 -1 。
示例 1：
输入：
[“TreeAncestor”,“getKthAncestor”,“getKthAncestor”,“getKthAncestor”]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]
输出： [null,1,0,-1]
解释：
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2,
2]);
treeAncestor.getKthAncestor(3, 1); // 返回 1 ，它是 3 的父节点
treeAncestor.getKthAncestor(5, 2); // 返回 0 ，它是 5 的祖父节点
treeAncestor.getKthAncestor(6, 3); // 返回 -1 因为不存在满足要求的祖先节点
提示：
1 <= k <= n <= 5 * 104
parent[0] == -1 表示编号为 0 的节点是根节点。
对于所有的 0 < i < n ，0 <= parent[i] < n 总成立
0 <= node < n
至多查询 5 * 104 次
题解：
方法：动态规划
class TreeAncestor { private int[][] p; // 记录每个节点的第 2^k 个祖先节点 // 构造函数，初始化每个节点的祖先数组 public TreeAncestor(int n, int[] parent) { p = new int[n][18]; // 初始化祖先数组 for (var e : p) { Arrays.fill(e, -1); // 初始值为 -1，表示没有祖先 } for (int i = 0; i < n; ++i) { p[i][0] = parent[i]; // 直接父节点是每个节点的第一个祖先节点 } // 逐层向上计算每个节点的第 2^k 个祖先节点 for (int j = 1; j < 18; ++j) { for (int i = 0; i < n; ++i) { if (p[i][j - 1] == -1) { continue; // 如果当前节点的第 2^(k-1) 个祖先节点不存在，跳过 } p[i][j] = p[p[i][j - 1]][j - 1]; // 计算当前节点的第 2^k 个祖先节点 } } } // 获取指定节点的第 k 个祖先节点 public int getKthAncestor(int node, int k) { for (int i = 17; i >= 0; --i) { // 从高位到低位遍历 k 的二进制表示 if (((k >> i) & 1) == 1) { // 如果当前位为 1 node = p[node][i]; // 获取当前节点的第 2^i 个祖先节点 if (node == -1) { break; // 如果节点不存在（已经是根节点），结束循环 } } } return node; // 返回第 k 个祖先节点的编号 } }
7.王位继承顺序
题目链接：1600. 王位继承顺序
一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点，这个家庭里有人出生也有人死亡。
这个王国有一个明确规定的王位继承顺序，第一继承人总是国王自己。我们定义递归函数 Successor(x, curOrder) ，给定一个人 x 和当前的继承顺序，该函数返回 x 的下一继承人。
Successor(x, curOrder):
如果 x 没有孩子或者所有 x 的孩子都在 curOrder 中：
如果 x 是国王，那么返回 null
否则，返回 Successor(x 的父亲, curOrder)
否则，返回 x 不在 curOrder 中最年长的孩子
比方说，假设王国由国王，他的孩子 Alice 和 Bob （Alice 比 Bob 年长）和 Alice 的孩子 Jack 组成。
一开始， curOrder 为 [“king”].
调用 Successor(king, curOrder) ，返回 Alice ，所以我们将 Alice 放入 curOrder 中，得到 [“king”, “Alice”] 。
调用 Successor(Alice, curOrder) ，返回 Jack ，所以我们将 Jack 放入 curOrder 中，得到 [“king”, “Alice”, “Jack”] 。
调用 Successor(Jack, curOrder) ，返回 Bob ，所以我们将 Bob 放入 curOrder 中，得到 [“king”, “Alice”, “Jack”, “Bob”] 。
调用 Successor(Bob, curOrder) ，返回 null 。最终得到继承顺序为 [“king”, “Alice”, “Jack”, “Bob”] 。
通过以上的函数，我们总是能得到一个唯一的继承顺序。
请你实现 ThroneInheritance 类：
ThroneInheritance(string kingName) 初始化一个 ThroneInheritance 类的对象。国王的名字作为构造函数的参数传入。
void birth(string parentName, string childName) 表示 parentName 新拥有了一个名为 childName 的孩子。
void death(string name) 表示名为 name 的人死亡。一个人的死亡不会影响 Successor 函数，也不会影响当前的继承顺序。你可以只将这个人标记为死亡状态。
string[] getInheritanceOrder() 返回 除去 死亡人员的当前继承顺序列表。
示例：
输入：
[“ThroneInheritance”, “birth”, “birth”, “birth”, “birth”, “birth”,
“birth”, “getInheritanceOrder”, “death”, “getInheritanceOrder”]
[[“king”], [“king”, “andy”], [“king”, “bob”], [“king”, “catherine”],
[“andy”, “matthew”], [“bob”, “alex”], [“bob”, “asha”], [null],
[“bob”], [null]]
输出：
[null, null, null, null, null, null, null, [“king”, “andy”, “matthew”,
“bob”, “alex”, “asha”, “catherine”], null, [“king”, “andy”, “matthew”,
“alex”, “asha”, “catherine”]]
解释：
ThroneInheritance t= new ThroneInheritance(“king”); // 继承顺序：king
t.birth(“king”, “andy”); // 继承顺序：king > andy
t.birth(“king”, “bob”); // 继承顺序：king > andy > bob
t.birth(“king”, “catherine”); // 继承顺序：king > andy > bob > catherine
t.birth(“andy”, “matthew”); // 继承顺序：king > andy > matthew > bob >
catherine
t.birth(“bob”, “alex”); // 继承顺序：king > andy > matthew > bob > alex >
catherine
t.birth(“bob”, “asha”); // 继承顺序：king > andy > matthew > bob > alex >
asha > catherine
t.getInheritanceOrder(); // 返回 [“king”, “andy”, “matthew”, “bob”,
“alex”, “asha”, “catherine”]
t.death(“bob”); // 继承顺序：king > andy > matthew > bob（已经去世）> alex > asha
catherine
t.getInheritanceOrder(); // 返回 [“king”, “andy”, “matthew”, “alex”,
“asha”, “catherine”]
提示：
1 <= kingName.length, parentName.length, childName.length, name.length
<= 15
kingName，parentName， childName 和 name 仅包含小写英文字母。
所有的参数 childName 和 kingName 互不相同。
所有 death 函数中的死亡名字 name 要么是国王，要么是已经出生了的人员名字。
每次调用 birth(parentName, childName) 时，测试用例都保证 parentName 对应的人员是活着的。
最多调用 105 次birth 和 death 。
最多调用 10 次 getInheritanceOrder 。
题解：
方法：多叉树的前序遍历
class ThroneInheritance { private String king; // 国王的姓名 private Set<String> dead = new HashSet<>(); // 记录已经去世的人的姓名 private Map<String, List<String>> g = new HashMap<>(); // 记录家族树的关系，以父节点的姓名为键，存储子节点的姓名列表 private List<String> ans = new ArrayList<>(); // 存储继承顺序的列表 // 构造函数，初始化国王姓名 public ThroneInheritance(String kingName) { king = kingName; } // 添加一个孩子节点 public void birth(String parentName, String childName) { g.computeIfAbsent(parentName, k -> new ArrayList<>()).add(childName); // 将孩子节点添加到对应父节点的子节点列表中 } // 记录一个人已经去世 public void death(String name) { dead.add(name); // 将姓名添加到去世记录中 } // 获取继承顺序列表 public List<String> getInheritanceOrder() { ans.clear(); // 清空结果列表 dfs(king); // 从国王开始进行深度优先搜索，获取继承顺序 return ans; // 返回继承顺序列表 } // 深度优先搜索函数，用于获取继承顺序 private void dfs(String x) { if (!dead.contains(x)) { // 如果当前节点没有去世，则将其姓名加入到继承顺序列表中 ans.add(x); } for (String y : g.getOrDefault(x, List.of())) { // 遍历当前节点的子节点 dfs(y); // 递归调用深度优先搜索函数 } } }
