一、3423. 循环数组中相邻元素的最大差值
题目链接
暴力枚举相邻的两个元素，代码如下：
class Solution {
public int maxAdjacentDistance(int[] nums) {
int ans = 0;
int n = nums.length;
for(int i=0; i<n; i++){
ans = Math.max(ans, Math.abs(nums[i]-nums[(i+1)%n]));
}
return ans;
}
}
二、3424. 将数组变相同的最小代价
题目链接
本题有两种情况：
- 不使用操作一，直接计算，答案为 s u m ( a b s ( a [ i ] − b [ i ] ) ) sum(abs(a[i] - b[i])) sum(abs(a[i]−b[i]))
- 使用操作一，将数组 a a a 其变为最佳的顺序，然后计算，答案为 s u m ( a b s ( a [ i ] − b [ i ] ) ) + k sum(abs(a[i]-b[i]))+k sum(abs(a[i]−b[i]))+k
- 取两者的较大值
这里的最佳顺序是， 最大的 a [ i ] − > 最大的 b [ i ] ，次大的 a [ i ] − > 次大的 b [ i ] 最大的a[i]->最大的b[i]，次大的a[i]->次大的b[i] 最大的a[i]−>最大的b[i]，次大的a[i]−>次大的b[i]，以此类推，证明如下：
代码如下：
class Solution {
public long minCost(int[] arr, int[] brr, long k) {
long ans = count(arr, brr);
Arrays.sort(brr);
Arrays.sort(arr);
return Math.min(ans, count(arr, brr)+k);
}
long count(int[] a, int[] b){
long res = 0;
int n = a.length;
for(int i=0; i<n; i++){
res += (long)Math.abs(a[i]-b[i]);
}
return res;
}
}
三、3425. 最长特殊路径
题目链接
本题求从祖先节点到后代节点，且节点值互不相同的最长路径（路径相同时，求经过节点最少的数量），可以得到以下信息：
- 求的是一个路径，就不可能是一颗树，可以使用前缀和的思想来求一个区间的和（即路径长度），在树的概念里，可以使用树的高度 d e p t h depth depth（深度）来代替区间 [ l , r ] [l,r] [l,r]
- 题目还要求一个路径中不能出现节点值相同的节点，所以还需要用一个哈希表 m a p map map 来记录从根节点到叶子节点的每个路径中，距离当前节点最近的所有节点值所在的深度。
- 此时就可以边遍历边计算，得到以当前节点为终点的路径的最大值及其经过的节点个数，同时不断的更新答案。
代码如下：
class Solution {
public int[] longestSpecialPath(int[][] edges, int[] nums) {
int n = nums.length;
List<int[]>[] g = new ArrayList[n];
Arrays.setAll(g, e->new ArrayList<>());
for(int[] e : edges){
int v = e[0], w = e[1], wt = e[2];
g[v].add(new int[]{w, wt});
g[w].add(new int[]{v, wt});
}
st.add(0);
dfs(0, -1, 0, g, nums);
return new int[]{len, cnt};
}
int len = 0;
int cnt = 1;
List<Integer> st = new ArrayList<>();//前缀和
Map<Integer, Integer> map = new HashMap<>();//统计<nums[i], depth>
//dfs(x:当前节点，fa:父节点，last:距离当前节点最近的不满足条件的节点深度)
void dfs(int x, int fa, int last, List<int[]>[] g, int[] nums){
int pre = map.getOrDefault(nums[x], 0);//上一次nums[x]出现的位置
last = Math.max(pre, last);//不满足要求的最大深度
int depth = st.size();//当前深度
int sum = st.get(depth-1);
int newLen = sum - st.get(last);
//更新答案
if(len < newLen || len == newLen && cnt > depth-last){
len = newLen;
cnt = depth-last;
}
map.put(nums[x], depth);//更新nums[x]所在的最近位置
for(int[] t : g[x]){
int y = t[0], wt = t[1];
if(y == fa) continue;
st.add(sum + wt);//更新前缀和
dfs(y, x, last, g, nums);
st.remove(depth);//回溯
}
map.put(nums[x], pre);//回溯
}
}
四、3426. 所有安放棋子方案的曼哈顿距离
题目链接
对于本题来说，我们无法枚举每一种合法方案，计算两两棋子之间的曼哈顿距离之和，所以需要反过来想，我们是否可以计算出每一个曼哈顿距离有多少种合法方案，也就是所谓的贡献法。这里我们需要把 ∣ x i − x j ∣ | x_i-x_j| ∣xi−xj∣ 和 ∣ y i − y j ∣ |y_i-y_j| ∣yi−yj∣ 分开计算。
- 先计算在一个 1 × n 1\times n 1×n 的矩阵中 ，如果当前有且只有 2 2 2 个棋子，此时的曼哈顿距离怎么算？
- 由于只有一行所以此时的曼哈顿距离只需要计算 ∣ x i − x j ∣ |x_i-x_j| ∣xi−xj∣ 一个维度
- 根据上述枚举 ∣ x i − x j ∣ |x_i-x_j| ∣xi−xj∣ 大小，求合法方案数的做法：
- 对于大小为 1 1 1 的合法方案有 n − 1 n-1 n−1
- 对于大小为 2 2 2 的合法方案有 n − 2 n-2 n−2
- 对于大小为 3 3 3 的合法方案有 n − 3 n-3 n−3
- …
- 可以发现，实际上就是计算 ∑ i = 1 n − 1 i ∗ ( n − i ) = n ∗ ∑ i = 1 n − 1 i + ∑ i = 1 n − 1 i 2 \sum_{i=1}^{n-1}i*(n-i) =n * \sum_{i=1}^{n-1}i +\sum_{i=1}^{n-1}i^2 ∑i=1n−1i∗(n−i)=n∗∑i=1n−1i+∑i=1n−1i2
- 注： ∑ i = 1 n i = n ( n + 1 ) 2 \sum_{i=1}^{n}i = \frac{n(n + 1)}{2} ∑i=1ni=2n(n+1)， ∑ i = 1 n i 2 = n ( n + 1 ) ( 2 n + 1 ) 6 \sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6} ∑i=1ni2=6n(n+1)(2n+1)
- 如果在一个 m × n m\times n m×n 的矩阵中：
- m = 1 m=1 m=1，有且只有 k ⩾ 2 k\geqslant 2 k⩾2 个棋子，此时的合法方案数还需要处理剩余 k − 2 k-2 k−2 个棋子的位置，即 ( m n − 2 k − 2 ) \binom{mn-2}{k-2} (k−2mn−2)，此时答案变成 ( m n − 2 k − 2 ) ∗ ∑ i = 1 n − 1 i ∗ ( n − i ) \binom{mn-2}{k-2}*\sum_{i=1}^{n-1}i*(n-i) (k−2mn−2)∗∑i=1n−1i∗(n−i)
- m ⩾ 1 m\geqslant1 m⩾1，有且只有 k ⩾ 2 k\geqslant 2 k⩾2 个棋子，此时的合法方案数还需要处理已经选择好的 2 2 2 个棋子在哪一行，即 m 2 m^2 m2，此时 s u m ( ∣ x i − x j ∣ ) = ( m n − 2 k − 2 ) ∗ m 2 ∗ ∑ i = 1 n − 1 i ∗ ( n − i ) sum(|x_i-x_j|)=\binom{mn-2}{k-2}*m^2*\sum_{i=1}^{n-1}i*(n-i) sum(∣xi−xj∣)=(k−2mn−2)∗m2∗∑i=1n−1i∗(n−i)，同理 s u m ( ∣ y i − y j ∣ ) = ( m n − 2 k − 2 ) ∗ n 2 ∗ ∑ i = 1 m − 1 i ∗ ( m − i ) sum(|y_i-y_j|)=\binom{mn-2}{k-2}*n^2*\sum_{i=1}^{m-1}i*(m-i) sum(∣yi−yj∣)=(k−2mn−2)∗n2∗∑i=1m−1i∗(m−i)
- 最终化简后就变成了 ( m n − 2 k − 2 ) ( m 2 n ( n 2 − 1 ) + n 2 m ( m 2 − 1 ) 6 ) \binom{mn-2}{k-2}(\frac{m^2n(n^2-1) + n^2m(m^2-1)}{6}) (k−2mn−2)(6m2n(n2−1)+n2m(m2−1))
代码如下：
class Solution {
private static final int MOD = 1_000_000_007;
private static final int MX = 100_000;
private static final long[] f = new long[MX];//i!
private static final long[] inv_f = new long[MX];//1/(i!)
static{
f[0] = 1;
for(int i=1; i<MX; i++){
f[i] = f[i-1] * i % MOD;
}
// 费马小定理！
// 1 / b % MOD = b ^ (MOD-2) % MOD 注：MOD必须为质数才成立
// 1 / (a*b*c) % p = pow(a*b*c, p - 2) % p
// 1 / (a*b) % p = pow(a*b, p-2) % p
// 1 / (a*b) % p = 1 / (a*b*c) * c % p
// 得到：inv_f[i-1] = inv_f[i] * i % p
inv_f[MX-1] = pow(f[MX-1], MOD-2);
for(int i=MX-1; i>0; i--){
inv_f[i-1] = inv_f[i] * i % MOD;
}
}
//x^y
static long pow(long x, long y){
long res = 1;
while(y > 0){
if(y%2 > 0)
res = res * x % MOD;
x = x * x % MOD;
y /= 2;
}
return res;
}
public int distanceSum(int m, int n, int k) {
return (int)(m * n * (m * ((long)n * n - 1) + n * ((long)m * m - 1)) / 6 % MOD * comb(m*n-2, k-2) % MOD);
}
//n!/(n-m)!m!
public long comb(int n, int m){
return f[n] * inv_f[m] % MOD * inv_f[n-m] % MOD;
}
}