欢迎大家加QQ群：623375442，可以方便群里面交流。这周题目着实很难。第三题7分，coding难度挺大。第四题8分，需要一些套路。
100432. Maximum Possible Number by Binary Concatenation
给你一个长度为 3 的整数数组 nums。
现以某种顺序 连接 数组 nums 中所有元素的 二进制表示 ，请你返回可以由这种方法形成的 最大 数值。
注意 任何数字的二进制表示 不含 前导零。
测试样例：
输入：nums = [1,2,3]
输出：30
解释：按照顺序 [3, 1, 2] 连接数字的二进制表示，得到结果 "11110"，这是 30 的二进制表示。
解答：这题利用一些字符串拼接的排序。长度很短，直接暴力。
class Solution {
public int maxGoodNumber(int[] nums) {
Integer[] sort = new Integer[nums.length];
for (int i = 0; i < sort.length; ++i) {
sort[i] = i;
}
Arrays.sort(sort, (a, b) -> ((Integer.toBinaryString(nums[b]) + Integer.toBinaryString(nums[a])).compareTo(Integer.toBinaryString(nums[a]) + Integer.toBinaryString(nums[b]))));
String binary = "";
for (int n : sort) {
binary += Integer.toBinaryString(nums[n]);
}
return Integer.parseInt(binary, 2);
}
}
100417. Remove Methods From Project
你正在维护一个项目，该项目有 n 个方法，编号从 0 到 n - 1。
给你两个整数 n 和 k，以及一个二维整数数组 invocations，其中 invocations[i] = [ai, bi] 表示方法 ai 调用了方法 bi。
已知如果方法 k 存在一个已知的 bug。那么方法 k 以及它直接或间接调用的任何方法都被视为 可疑方法 ，我们需要从项目中移除这些方法。
只有当一组方法没有被这组之外的任何方法调用时，这组方法才能被移除。
返回一个数组，包含移除所有 可疑方法 后剩下的所有方法。你可以以任意顺序返回答案。如果无法移除 所有 可疑方法，则 不 移除任何方法。
测试样例：
输入： n = 4, k = 1, invocations = [[1,2],[0,1],[3,2]]
输出：[0,1,2,3]
解释：方法 2 和方法 1 是可疑方法，但它们分别直接被方法 3 和方法 0 调用。由于方法 3 和方法 0 不是可疑方法，我们无法移除任何方法，故返回所有方法。
解答：这题其实就挺恶心的，题目描述很绕。题目其实不难，利用DFS寻找所有可疑方案。然后利用并查集寻找所有不可以方法的方法组。保留方法组。
class Solution {
class DSU{
int[] parent;
public DSU(int N) {
parent = new int[N];
for (int i = 0; i < N; ++i) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
parent[find(x)] = find(y);
}
}
public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
List<Integer>[] edges = new List[n];
DSU uf = new DSU(n);
for (int i = 0; i < n; ++i) {
edges[i] = new ArrayList<>();
}
for (int[] in : invocations) {
edges[in[0]].add(in[1]);
uf.union(in[0], in[1]);
}
boolean[] suspicious = new boolean[n];
dfs1(k, edges, suspicious);
boolean[] isVisit = new boolean[n];
List<Integer> res = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if (!suspicious[i]) {
isVisit[uf.find(i)] = true;
}
}
for (int i = 0; i < n; ++i) {
if (isVisit[uf.find(i)]) {
res.add(i);
}
}
return res;
}
private void dfs1(int k, List<Integer>[] edges, boolean[] suspicious) {
if (!suspicious[k]) {
suspicious[k] = true;
for (int n : edges[k]) {
dfs1(n, edges, suspicious);
}
}
}
}100431. Construct 2D Grid Matching Graph Layout
给你一个二维整数数组 edges ，它表示一棵 n 个节点的 无向 图，其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 之间有一条边。
请你构造一个二维矩阵，满足以下条件：
- 矩阵中每个格子 一一对应 图中 0 到 n - 1 的所有节点。
- 矩阵中两个格子相邻（横 的或者 竖 的）当且仅当 它们对应的节点在 edges 中有边连接。
题目保证 edges 可以构造一个满足上述条件的二维矩阵。
请你返回一个符合上述要求的二维整数数组，如果存在多种答案，返回任意一个。
测试样例：
输入：n = 4, edges = [[0,1],[0,2],[1,3],[2,3]]
输出：[3,1],[2,0]]
解答：题目保证 edges 可以构造一个满足上述条件的二维矩阵。这题就变得简单很多。首先我们统计一下每个点的度。如果整个结果最小度是1，那么最大度一定是2，此时是一字长蛇阵。否则最小度一定是2（四个对角线上）。我们随机选择一个对角线，然后按照edges的情况填充。
class Solution {
public int[][] constructGridLayout(int n, int[][] _edges) {
List<Integer>[] edges = new List[n];
for (int i = 0; i < n; ++i) {
edges[i] = new ArrayList<>();
}
for (int[] e : _edges) {
edges[e[0]].add(e[1]);
edges[e[1]].add(e[0]);
}
int min = findMinConnection(edges);
boolean[] isUsed = new boolean[n];
if (edges[min].size() == 1) {
// 一字长蛇阵，按顺序一个个排列
int[][] res = new int[1][n];
res[0][0] = min;
isUsed[min] = true;
for (int i = 1; i < n; ++i) {
int other = findRemain(edges[res[0][i - 1]], isUsed);
isUsed[other] = true;
res[0][i] = other;
}
return res;
} else {
// 首先我们初始化前两列。
List<List<Integer>> matrix = initialTwoRow(min, edges, isUsed);
while (findRemain(edges[matrix.get(matrix.size() - 1).get(0)], isUsed) != -1) {
// 上一排已经排完，那么每一排都能根据上一排情况计算
// 每一排第一个数的度一定是3
buildOneRow(matrix, edges, isUsed);
}
return turnMatrix(matrix);
}
}
private int findMinConnection(List<Integer>[] edges) {
int res = 0;
for (int i = 1; i < edges.length; ++i) {
if (edges[i].size() < edges[res].size()) {
res = i;
}
}
return res;
}
private int findShared(List<Integer> e1, List<Integer> e2, boolean[] isUsed) {
for (int n1 : e1) {
for (int n2 : e2) {
if (n1 == n2 && !isUsed[n1]) {
return n1;
}
}
}
return -1;
}
private int findRemain(List<Integer> e1, boolean[] isUsed) {
for (int n : e1) {
if (!isUsed[n]) {
return n;
}
}
return -1;
}
private int[][] turnMatrix(List<List<Integer>> lists) {
int[][] res = new int[lists.size()][lists.get(0).size()];
for (int i = 0; i < res.length; ++i) {
for (int j = 0; j < res[i].length; ++j) {
res[i][j] = lists.get(i).get(j);
}
}
return res;
}
private List<List<Integer>> initialTwoRow(int min, List<Integer>[] edges, boolean[] isUsed) {
List<List<Integer>> matrix = new ArrayList<>();
matrix.add(new ArrayList<>());
isUsed[min] = true;
matrix.get(0).add(min);
// 随机选择一个数，且这个数字和对角线选中数相连。
matrix.add(new ArrayList<>());
int down = findRemain(edges[min], isUsed);
isUsed[down] = true;
matrix.get(1).add(down);
int last = min;
do {
// 因为题目保证了有解答。所以当前第一排最后一个数一定只剩下一个可选结果
last = findRemain(edges[last], isUsed);
isUsed[last] = true;
matrix.get(0).add(last);
int share = findShared(edges[last], edges[matrix.get(1).get(getSize(matrix, 1))], isUsed);
isUsed[share] = true;
matrix.get(1).add(share);
} while (findRemain(edges[last], isUsed) != -1);
return matrix;
}
private void buildOneRow(List<List<Integer>> matrix, List<Integer>[] edges, boolean[] isUsed) {
List<Integer> lastRow = matrix.get(matrix.size() - 1);
List<Integer> nextRow = new ArrayList<>();
for (int n : lastRow) {
int tmp = findRemain(edges[n], isUsed);
isUsed[tmp] = true;
nextRow.add(tmp);
}
matrix.add(nextRow);
}
private int getSize(List<List<Integer>> matrix, int row) {
return matrix.get(row).size() - 1;
}
}100436. Sorted GCD Pair Queries
给你一个长度为 n 的整数数组 nums 和一个整数数组 queries 。
gcdPairs 表示数组 nums 中所有满足 0 <= i < j < n 的数对 (nums[i], nums[j]) 的 最大公约数 升序 排列构成的数组。
对于每个查询 queries[i] ，你需要找到 gcdPairs 中下标为 queries[i] 的元素。
请你返回一个整数数组 answer ，其中 answer[i] 是 gcdPairs[queries[i]] 的值。
gcd(a, b) 表示 a 和 b 的 最大公约数 。
测试样例：
输入：nums = [2,3,4], queries = [0,2,2]
输出：[1,2,2]
解释：gcdPairs = [gcd(nums[0], nums[1]), gcd(nums[0], nums[2]), gcd(nums[1], nums[2])] = [1, 2, 1].升序排序后得到 gcdPairs = [1, 1, 2] 。所以答案为 [gcdPairs[queries[0]], gcdPairs[queries[1]], gcdPairs[queries[2]]] = [1, 2, 2] 。
解答：这题需要知道一个套路。因为n很大，所以我们暴力枚举肯定是不行的。那么我们就反向思维一下，我们枚举一下能够让某一个数整除的所有数。然后利用这个信息，计算GCD的分布情况。最后利用前缀和，二分查找结果。
class Solution {
// 一个特殊类，输入一个数字n，输出所有n能够整除的整数。
private class PossibleSplit {
private static HashMap<Integer, List<Integer>> split = new HashMap<>();
public List<Integer> getSplit(int num) {
if (!split.containsKey(num)) {
Map<Integer, Integer> prime = new HashMap<>();
int tmp = num;
for (int i = 2; i * i <= num; ++i) {
int c = 0;
while (tmp % i == 0) {
++c;
tmp /= i;
}
if (c > 0) {
prime.put(i, c);
}
}
if (tmp != 1) {
prime.put(tmp, 1);
}
List<Map.Entry<Integer, Integer>> list = new ArrayList<>(prime.entrySet());
List<Integer> result = new ArrayList<>();
dfs(list, result, 0, 1);
// 这里注意，结果从大到小排序
// 小数可能会被大数重复计算
Collections.sort(result, (a, b) -> (b.compareTo(a)));
split.put(num, result);
}
return split.get(num);
}
private void dfs(List<Map.Entry<Integer, Integer>> list, List<Integer> result, int offset, int mul) {
if (offset == list.size()) {
result.add(mul);
} else {
dfs(list, result, offset + 1, mul);
int tmp = mul;
for (int i = 1; i <= list.get(offset).getValue(); ++i) {
tmp *= list.get(offset).getKey();
dfs(list, result, offset + 1, tmp);
}
}
}
}
public int[] gcdValues(int[] nums, long[] queries) {
int max = Arrays.stream(nums).max().getAsInt();
PossibleSplit split = new PossibleSplit();
long[] mem = new long[max + 1];
// 统计一下每个数整除情况
int[] count = new int[max + 1];
for (int n : nums) {
List<int[]> success = new ArrayList<>();
for (int t : split.getSplit(n)) {
// 如果之前有数字也能被t整除
if (count[t] > 0) {
int diff = count[t];
// 刷新一下结果，然后去掉重复情况
for (int[] s : success) {
if (s[0] % t == 0) {
diff -= s[1];
}
}
if (diff > 0) {
success.add(new int[]{t, diff});
}
mem[t] += diff;
}
count[t] += 1;
}
}
// 前缀和
for (int i = 1; i < mem.length; ++i) {
mem[i] += mem[i - 1];
}
int[] res = new int[queries.length];
// 二分寻找结果
for (int i = 0; i < queries.length; ++i) {
int st = 0, ed = mem.length;
while (st < ed) {
int mid = (st + ed) / 2;
if (mem[mid] <= queries[i]) {
st = mid + 1;
} else {
ed = mid;
}
}
res[i] = st;
}
return res;
}
}