欢迎大家加QQ群：623375442，可以方便群里面交流。以后太难的双周赛就不打了，之后有时间会补上题解。真的不想做纯数学的题目。
100561. Maximum Difference Between Adjacent Elements in a Circular Array
给你一个 循环 数组 nums ，请你找出相邻元素之间的 最大 绝对差值。
注意：一个循环数组中，第一个元素和最后一个元素是相邻的。
测试样例：
输入：nums = [1,2,4]
输出：3
解释：由于 nums 是循环的，nums[0] 和 nums[2] 是相邻的，它们之间的绝对差值是最大值 |4 - 1| = 3 。
解答：暴力运算。
class Solution {
public int maxAdjacentDistance(int[] nums) {
int res = 0;
for (int i = 0; i < nums.length; ++i) {
if (i == 0) res = Math.max(res, Math.abs(nums[0] - nums[nums.length - 1]));
else res = Math.max(res, Math.abs(nums[i] - nums[i - 1]));
}
return res;
}
}3424. Minimum Cost to Make Arrays Identical
给你两个长度都为 n 的整数数组 arr 和 brr 以及一个整数 k 。你可以对 arr 执行以下操作任意次：
- 将 arr 分割成若干个 连续的 子数组，并将这些子数组按任意顺序重新排列。这个操作的代价为 k 。
- 选择 arr 中的任意一个元素，将它增加或者减少一个正整数 x 。这个操作的代价为 x 。
请你返回将 arr 变为 brr 的 最小 总代价。
子数组 是一个数组中一段连续 非空 的元素序列。
测试样例：
输入：arr = [-7,9,5], brr = [7,-2,-5], k = 2
输出：13
解释：
- 将 arr 分割成两个连续子数组：[-7] 和 [9, 5] 然后将它们重新排列成 [9, 5, -7] ，代价为 2 。
- 将 arr[0] 减小 2 ，数组变为 [7, 5, -7] ，操作代价为 2 。
- 将 arr[1] 减小 7 ，数组变为 [7, -2, -7] ，操作代价为 7 。
- 将 arr[2] 增加 2 ，数组变为 [7, -2, -5] ，操作代价为 2 。
将两个数组变相等的总代价为 2 + 2 + 7 + 2 = 13 。
解答：有两种情况。一种是不做任何shuffle，直接计算代价。还有一种情况是，做一次shuffle，然后计算代价。第二种情况，我们可以认为两个数组都是从小到大排序，取最小的代价（这个时候，其实就是子数组长度都是1，然后任意排序）。
class Solution {
public long minCost(int[] arr, int[] brr, long k) {
long noShuffle = 0;
for (int i = 0; i < arr.length; ++i) {
noShuffle += Math.abs(arr[i] - brr[i]);
}
Integer[] sort1 = getSort(arr), sort2 = getSort(brr);
long oneShuffle = k;
boolean isShuffle = false;
for (int i = 0; i < arr.length; ++i) {
oneShuffle += Math.abs(arr[sort1[i]] - brr[sort2[i]]);
}
return Math.min(noShuffle, oneShuffle);
}
private Integer[] getSort(int[] arr) {
Integer[] res = new Integer[arr.length];
for (int i = 0; i < arr.length; ++i) {
res[i] = i;
}
Arrays.sort(res, (a, b) -> (arr[a] != arr[b] ? Integer.compare(arr[a], arr[b]) : Integer.compare(a, b)));
return res;
}
}3425. Longest Special Path
给你一棵根节点为节点 0 的无向树，树中有 n 个节点，编号为 0 到 n - 1 ，这棵树通过一个长度为 n - 1 的二维数组 edges 表示，其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和 vi 之间有一条长度为 lengthi 的边。同时给你一个整数数组 nums ，其中 nums[i] 表示节点 i 的值。
特殊路径 指的是树中一条从祖先节点 往下 到后代节点且经过节点的值 互不相同 的路径。
注意 ，一条路径可以开始和结束于同一节点。
请你返回一个长度为 2 的数组 result ，其中 result[0] 是 最长 特殊路径的 长度 ，result[1] 是所有 最长特殊路径中的 最少 节点数目。
测试样例：
输入：edges = [[0,1,2],[1,2,3],[1,3,5],[1,4,4],[2,5,6]], nums = [2,1,2,1,3,1]
输出：[6,2]
解释：最长特殊路径为 2 -> 5 和 0 -> 1 -> 4 ，两条路径的长度都为 6 。所有特殊路径里，节点数最少的路径含有 2 个节点。
解答：DFS题目，但是DFS过程中需要记录一下中间情况。
class Solution {
private class Data {
// 记录一下路径上的num和edge长度信息
int[] nums, numStack, edgeStack;
List<int[]>[] edges;
// 记录路径上重复数情况
HashMap<Integer, Stack<Integer>> map;
public Data(int[][] _edges, int[] nums) {
this.nums = nums;
edges = new List[nums.length];
for (int i = 0; i < nums.length; ++i) {
edges[i] = new ArrayList<>();
}
for (int[] e : _edges) {
edges[e[0]].add(new int[]{e[1], e[2]});
edges[e[1]].add(new int[]{e[0], e[2]});
}
numStack = new int[nums.length];
edgeStack = new int[nums.length];
map = new HashMap<>();
}
}
public int[] longestSpecialPath(int[][] _edges, int[] nums) {
Data data = new Data(_edges, nums);
int[] res = {0,1};
int[] numStack = new int[nums.length], edgeStack = new int[nums.length];
dfs(0, -1, data, res, -1, 0);
return res;
}
private void dfs(int pos, int last, Data data, int[] res, int left, int depth) {
if (data.map.containsKey(data.nums[pos]) && !data.map.get(data.nums[pos]).isEmpty()) {
left = Math.max(left, data.map.get(data.nums[pos]).peek());
} else {
data.map.put(data.nums[pos], new Stack<>());
}
if (depth >= 1) {
int curLength = data.edgeStack[depth - 1] - (left >= 0 ? data.edgeStack[left] : 0);
if (curLength > res[0]) {
res[0] = curLength;
res[1] = depth - left;
} else if (curLength == res[0]) {
res[1] = Math.min(res[1], depth - left);
}
}
data.map.get(data.nums[pos]).push(depth);
data.numStack[depth] = data.nums[pos];
for (int[] ne : data.edges[pos]) {
if (ne[0] == last) continue;
// edgeStack是对edge的前缀和
data.edgeStack[depth] = (depth == 0 ? 0 : data.edgeStack[depth - 1]) + ne[1];
dfs(ne[0], pos, data, res, left, depth + 1);
}
data.map.get(data.nums[pos]).pop();
}
}100555. Manhattan Distances of All Arrangements of Pieces
给你三个整数 m ，n 和 k 。
给你一个大小为 m x n 的矩形格子，它包含 k 个没有差别的棋子。请你返回所有放置棋子的 合法方案 中，每对棋子之间的曼哈顿距离之和。
一个 合法方案 指的是将所有 k 个棋子都放在格子中且一个格子里 至多 只有一个棋子。
由于答案可能很大， 请你将它对 10^9 + 7 取余 后返回。
两个格子 (xi, yi) 和 (xj, yj) 的曼哈顿距离定义为 |xi - xj| + |yi - yj| 。
测试样例：
输入：m = 2, n = 2, k = 2
输出：8
解释：所以所有方案的总曼哈顿距离之和为 1 + 1 + 1 + 1 + 2 + 2 = 8 。
输出为 max(4, 4, 7, 4, 2) = 7 。
解答：竞赛的时候，看了一眼不会做就溜了。纯纯数学题目。利用组合计算所有情况。
class Solution {
private static int mod = 1_000_000_007;
public int distanceSum(int m, int n, int k) {
long[] fact = new long[m * n];
fact[0] = 1;
for (int i = 1; i < m * n; i++) fact[i] = fact[i - 1] * i % mod;
long c = fact[m * n - 2] * fastMod(fact[k - 2], mod - 2, mod) % mod * fastMod(fact[m * n - k], mod - 2, mod) % mod;
long[] suma = getSum(n);
long[] sumb = getSum(m);
long res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
res += n * sumb[j] + m * suma[i];
res %= mod;
}
}
res = res * fastMod(2, mod - 2, mod) % mod;
res = res * c % mod;
return (int) res;
}
private long[] getSum(int n) {
long[] res = new long[n];
res[0] = (long) n * (n - 1) / 2;
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] - (n - i) + i;
}
return res;
}
private long fastMod(long base, long r, long mod) {
long res = 1;
long p = 1;
while (p <= r) {
if ((r & p) != 0) {
res = res * base % mod;
}
base = base * base % mod;
p = p << 1;
}
return res;
}
}