欢迎大家加QQ群：623375442，可以方便群里面交流。这周终于是简单手速场了。久违得有点怀念了。
100501. Smallest Number With All Set Bits
给你一个正整数 n。
返回 大于等于 n 且二进制表示仅包含 置位 位的 最小 整数 x 。
置位 位指的是二进制表示中值为 1 的位。
测试样例：
输入：n = 5
输出：7
解释：7 的二进制表示是 "111"。
解答：按照题意，暴力计算。
class Solution {
public int smallestNumber(int n) {
int res = 0, diff = 1;
while (res < n) {
res += diff;
diff <<= 1;
}
return res;
}
}100444. Identify the Largest Outlier in an Array
给你一个整数数组 nums。该数组包含 n 个元素，其中 恰好 有 n - 2 个元素是 特殊数字 。剩下的 两个 元素中，一个是这些 特殊数字 的 和 ，另一个是 异常值 。
异常值 的定义是：既不是原始特殊数字之一，也不是表示这些数字元素和的数字。
注意，特殊数字、和 以及 异常值 的下标必须 不同 ，但可以共享 相同 的值。
返回 nums 中可能的 最大异常值。
测试样例：
输入：nums = [2,3,5,10]
输出：10
解释：特殊数字可以是 2 和 3，因此和为 5，异常值为 10。
解答：首先计算一下数组总和，并创建一个哈希字典。如果一个数字是特殊字符，那么sum - 2 n一定出现在哈希表中。注意如果sum - 2 n = n这种情况，那么当前被假定为特殊数字得出现2次。
class Solution {
public int getLargestOutlier(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
int sum = 0;
for (int n : nums) {
sum += n;
map.put(n, map.getOrDefault(n, 0) + 1);
}
int res = Integer.MIN_VALUE;
for (int n : nums) {
int remain = sum - n;
if (map.containsKey(remain - n)) {
if (remain - n != n) {
res = Math.max(remain - n, res);
} else if (map.get(remain - n) >= 2) {
res = Math.max(res, n);
}
}
}
return res;
}
}100475. Maximize the Number of Target Nodes After Connecting Trees I
有两棵 无向 树，分别有 n 和 m 个树节点。两棵树中的节点编号分别为[0, n - 1] 和 [0, m - 1] 中的整数。
给你两个二维整数 edges1 和 edges2 ，长度分别为 n - 1 和 m - 1 ，其中 edges1[i] = [ai, bi] 表示第一棵树中节点 ai 和 bi 之间有一条边，edges2[i] = [ui, vi] 表示第二棵树中节点 ui 和 vi 之间有一条边。同时给你一个整数 k 。
如果节点 u 和节点 v 之间路径的边数小于等于 k ，那么我们称节点 u 是节点 v 的 目标节点 。注意 ，一个节点一定是它自己的 目标节点 。
请你返回一个长度为 n 的整数数组 answer ，answer[i] 表示将第一棵树中的一个节点与第二棵树中的一个节点连接一条边后，第一棵树中节点 i 的 目标节点 数目的 最大值 。
注意 ，每个查询相互独立。意味着进行下一次查询之前，你需要先把刚添加的边给删掉。
测试样例：
输入：edges1 = [[0,1],[0,2],[2,3],[2,4]], edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]], k = 2
输出：[9,7,9,8,8]
解释：
- 对于 i = 0 ，连接第一棵树中的节点 0 和第二棵树中的节点 0 。
- 对于 i = 1 ，连接第一棵树中的节点 1 和第二棵树中的节点 0 。
- 对于 i = 2 ，连接第一棵树中的节点 2 和第二棵树中的节点 4 。
- 对于 i = 3 ，连接第一棵树中的节点 3 和第二棵树中的节点 4 。
- 对于 i = 4 ，连接第一棵树中的节点 4 和第二棵树中的节点 4 。
解答：这题范围太小了。n, m <= 1000。我就不用第四题的写法直接暴力了。它的逻辑其实很简单。在edges1树上的节点，找到所有当前节点符合要求的节点。同时我们在edges2树上，寻找k - 1距离下的最大节点。这样无脑链接这个点，就是最右结果。
class Solution {
public int[] maxTargetNodes(int[][] edges1, int[][] edges2, int k) {
// 寻找每棵树，距离为k / k - 1下的符合要求的节点情况。
TreeData t1 = new TreeData(edges1, k), t2 = new TreeData(edges2, k - 1);
int max = 0;
// 寻找树2的最优情况
for (int n : t2.getResult()) {
max = Math.max(max, n);
}
// 无脑链接
int[] res = new int[t1.getResult().length];
for (int i = 0; i < res.length; ++i) {
res[i] = t1.getResult()[i] + max;
}
return res;
}
}
class TreeData {
private List<Integer>[] edges;
private int[] result;
public int size, k;
public TreeData(int[][] _edges, int k) {
edges = new List[_edges.length + 1];
size = edges.length;
for (int i = 0; i < edges.length; ++i) {
edges[i] = new ArrayList<>();
}
for (int[] e : _edges) {
edges[e[0]].add(e[1]);
edges[e[1]].add(e[0]);
}
this.k = k;
result = new int[edges.length];
for (int i = 0; i < edges.length; ++i) {
dfsResult(i, -1, 0, i);
}
}
private void dfsResult(int cur, int last, int depth, int seed) {
if (depth <= k) {
result[seed] += 1;
}
if (depth < k) {
for (int n : edges[cur]) {
if (n != last) {
dfsResult(n, cur, depth + 1, seed);
}
}
}
}
public int[] getResult() {
return result;
}
}100485. Maximize the Number of Target Nodes After Connecting Trees II
有两棵 无向 树，分别有 n 和 m 个树节点。两棵树中的节点编号分别为[0, n - 1] 和 [0, m - 1] 中的整数。
给你两个二维整数 edges1 和 edges2 ，长度分别为 n - 1 和 m - 1 ，其中 edges1[i] = [ai, bi] 表示第一棵树中节点 ai 和 bi 之间有一条边，edges2[i] = [ui, vi] 表示第二棵树中节点 ui 和 vi 之间有一条边。
如果节点 u 和节点 v 之间路径的边数是偶数，那么我们称节点 u 是节点 v 的 目标节点 。注意 ，一个节点一定是它自己的 目标节点 。
请你返回一个长度为 n 的整数数组 answer ，answer[i] 表示将第一棵树中的一个节点与第二棵树中的一个节点连接一条边后，第一棵树中节点 i 的 目标节点 数目的 最大值 。
注意 ，每个查询相互独立。意味着进行下一次查询之前，你需要先把刚添加的边给删掉。
测试样例：
输入：edges1 = [[0,1],[0,2],[2,3],[2,4]], edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]], k = 2
输出：[8,7,7,8,8]
解释：
- 对于 i = 0 ，连接第一棵树中的节点 0 和第二棵树中的节点 0 。
- 对于 i = 1 ，连接第一棵树中的节点 1 和第二棵树中的节点 4 。
- 对于 i = 2 ，连接第一棵树中的节点 2 和第二棵树中的节点 7 。
- 对于 i = 3 ，连接第一棵树中的节点 3 和第二棵树中的节点 0 。
- 对于 i = 4 ，连接第一棵树中的节点 4 和第二棵树中的节点 4 。
解答：这题稍微难一点。从上一题距离为k，变成寻找奇偶性。然后因为n和m变大了很多，不能直接暴力搜索了。遍历两次树，然后寻找最优情况。
class Solution {
public int[] maxTargetNodes(int[][] edges1, int[][] edges2) {
TreeData t1 = new TreeData(edges1), t2 = new TreeData(edges2);
int max = 0;
// 寻找树2的最优情况
for (int n : t2.getResult()) {
max = Math.max(max, t2.size - n);
}
// 无脑链接
int[] res = new int[t1.getResult().length];
for (int i = 0; i < res.length; ++i) {
res[i] = t1.getResult()[i] + max;
}
return res;
}
}
class TreeData {
private List<Integer>[] edges;
private int[][] zeroPass;
private int[] result;
public int size;
public TreeData(int[][] _edges) {
edges = new List[_edges.length + 1];
size = edges.length;
for (int i = 0; i < edges.length; ++i) {
edges[i] = new ArrayList<>();
}
for (int[] e : _edges) {
edges[e[0]].add(e[1]);
edges[e[1]].add(e[0]);
}
zeroPass = new int[edges.length][2];
dfsZero(0, -1);
result = new int[edges.length];
dfsResult(0, -1, null);
}
// 第一次假设0为root，遍历结果
private void dfsZero(int cur, int last) {
zeroPass[cur][0] = 1;
for (int n : edges[cur]) {
if (n != last) {
dfsZero(n, cur);
int[] tmp = zeroPass[n];
zeroPass[cur][0] += tmp[1];
zeroPass[cur][1] += tmp[0];
}
}
}
// 第二次遍历，利用第一次的结果计算各个节点的奇偶情况。
private void dfsResult(int cur, int last, int[] mem) {
if (cur == 0) {
result[cur] = zeroPass[cur][0];
} else {
result[cur] = zeroPass[cur][0] + mem[1];
}
int zero = zeroPass[cur][0] + (mem != null ? mem[1] : 0), one = zeroPass[cur][1] + (mem != null ? mem[0] : 0);
for (int n : edges[cur]) {
if (n != last) {
dfsResult(n, cur, new int[]{zero - zeroPass[n][1], one - zeroPass[n][0]});
}
}
}
public int[] getResult() {
return result;
}
}