欢迎大家加QQ群：623375442，可以方便群里面交流。上周生病了，鸽了两场。最近总算是好了，可以参加2024年最后一场比赛了.感谢手速场, 打起来很舒服。
100516. Minimum Operations to Make Columns Strictly Increasing
给你一个由 非负 整数组成的 m x n 矩阵 grid。
在一次操作中，你可以将任意元素 grid[i][j] 的值增加 1。
返回使 grid 的所有列 严格递增 所需的 最少 操作次数。
测试样例：
输入：grid = [[3,2],[1,3],[3,4],[0,1]]
输出：15
解释：
- 为了让第 0 列严格递增，可以对 grid[1][0] 执行 3 次操作，对 grid[2][0] 执行 2 次操作，对 grid[3][0] 执行 6 次操作。
- 为了让第 1 列严格递增，可以对 grid[3][1] 执行 4 次操作。
解答：按照题意，暴力计算。
class Solution {
public int minimumOperations(int[][] grid) {
int m = grid.length, n = grid[0].length;
int res = 0;
for (int i = 0; i < n; ++i) {
int last = Integer.MIN_VALUE;
for (int j = 0; j < m; ++j) {
if (grid[j][i] >= last) {
last = grid[j][i] + 1;
} else {
res += last - grid[j][i];
last += 1;
}
}
}
return res;
}
}100508. Find the Lexicographically Largest String From the Box I
给你一个字符串 word 和一个整数 numFriends。
Alice 正在为她的 numFriends 位朋友组织一个游戏。游戏分为多个回合，在每一回合中：
- word 被分割成 numFriends 个 非空 字符串，且该分割方式与之前的任意回合所采用的都 不完全相同 。
- 所有分割出的字符串都会被放入一个盒子中。
在所有回合结束后，找出盒子中 字典序最大的 字符串。
字符串 a 的字典序 小于 字符串 b 的前提是：在两个字符串上第一处不同的位置上，a 的字母在字母表中的顺序早于 b 中对应的字母。如果前 min(a.length, b.length) 个字符都相同，那么较短的字符串字典序更小。
测试样例：
输入：word = "dbca", numFriends = 2
输出："dbc"
解释：所有可能的分割方式为：
- "d" 和 "bca"。
- "db" 和 "ca"。
- "dbc" 和 "a"。
解答：这题范围太小了，可以直接暴力。WA一次，注意numFriends=1的情况。如果数据量变大，估计需要用到后缀数组。
class Solution {
public String answerString(String word, int numFriends) {
if (numFriends == 1) return word;
int[] range = null;
for (int i = 0; i < word.length(); ++i) {
numFriends = Math.max(0, numFriends - 1);
int[] curRange = {i, word.length() - numFriends};
range = compare(range, curRange, word);
}
return word.substring(range[0], range[1]);
}
private int[] compare(int[] r1, int[] r2, String word) {
if (r1 == null) return r2;
int l1 = r1[1] - r1[0], l2 = r2[1] - r2[0];
for (int i = 0; i < Math.min(l1, l2); ++i) {
if (word.charAt(r1[0] + i) != word.charAt(r2[0] + i)) {
if (word.charAt(r1[0] + i) > word.charAt(r2[0] + i)) return r1;
else return r2;
}
}
return l1 >= l2 ? r1 : r2;
}
}100522. Count Special Subsequences
给你一个只包含正整数的数组 nums 。
特殊子序列 是一个长度为 4 的子序列，用下标 (p, q, r, s) 表示，它们满足 p < q < r < s ，且这个子序列 必须 满足以下条件：
- nums[p] nums[r] == nums[q] nums[s]
- 相邻坐标之间至少间隔 一个 数字。换句话说，q - p > 1 ，r - q > 1 且 s - r > 1 。
子序列指的是从原数组中删除零个或者更多元素后，剩下元素不改变顺序组成的数字序列。
请你返回 nums 中不同 特殊子序列 的数目。
测试样例：
输入：nums = [1,2,3,4,3,6,1]
输出：1
解释：nums 中只有一个特殊子序列。
- (p, q, r, s) = (0, 2, 4, 6) ：
- 对应的元素为 (1, 3, 3, 1) 。
- nums[p] nums[r] = nums[0] nums[4] = 1 * 3 = 3
- nums[q] nums[s] = nums[2] nums[6] = 3 * 1 = 3
解答：稍微脑筋急转弯一下nums[p] nums[r] == nums[q] nums[s]可以得出nums[p] / nums[q] = nums[s] / nums[r]。这样前缀处理一下，就能快速计算结果了。
class Solution {
public long numberOfSubsequences(int[] nums) {
HashMap<Double, Integer> map = new HashMap<>();
long res = 0;
for (int i = 4; i + 2 < nums.length; ++i) {
double n1 = nums[i - 2], cur = nums[i];
for (int j = 0; j + 1 < i - 2; ++j) {
double div = nums[j] / n1;
map.put(div, map.getOrDefault(div, 0) + 1);
}
// 保证nums[p] / nums[q] = nums[s] / nums[r]
for (int j = i + 2; j < nums.length; ++j) {
res += map.getOrDefault(nums[j] / cur, 0);
}
}
return res;
}
}100507. Count the Number of Arrays with K Matching Adjacent Elements
给你三个整数 n ，m ，k 。长度为 n 的 好数组 arr 定义如下：
- arr 中每个元素都在 闭 区间 [1, m] 中。
- 恰好 有 k 个下标 i （其中 1 <= i < n）满足 arr[i - 1] == arr[i] 。
请你返回可以构造出的 好数组 数目。
由于答案可能会很大，请你将它对 10^9 + 7 取余 后返回。
测试样例：
输入：n = 3, m = 2, k = 1
输出：4
解释：总共有 4 个好数组，分别是 [1, 1, 2] ，[1, 2, 2] ，[2, 1, 1] 和 [2, 2, 1] 。所以答案为 4 。
解答：这题着实难度不大。一共n个位置。不算上第一个位置，那么我们从n - 1个位置中选出k个位置，这k个位置的数字与之前相同。那么剩下的数字中，随机分布（但是要确保它和之前的数不同）
class Solution {
private static final int mod = 1_000_000_007;
private static final long[] reverse = new long[100000];
static {
reverse[0] = 1;
for (int i = 1; i < 100000; ++i) {
reverse[i] = reverse[i - 1] * getInv(i) % mod;
}
}
public int countGoodArrays(int n, int m, int k) {
// 计算剩下的数字可能性，且它与前一个数不同
long n1 = mul(m - 1, n - 1 - k) * m % mod;
long n2 = 1;
for (int i = 1; i <= n - 1; ++i) {
n2 = n2 * i % mod;
}
// 利用组合公式，计算C(n - 1, k)
return (int) mul(n1, mul(n2, mul(reverse[k], reverse[n - k - 1])));
}
private static long getInv(int x) {
return mul(x, mod - 2);
}
private static long mul(int x, int remain) {
if (remain == 0) {
return 1;
} else {
long tmp = mul(x, remain / 2);
long res = tmp * tmp % mod;
if (remain % 2 == 1) {
res = res * x % mod;
}
return res;
}
}
private long mul(long x, long y) {
return x * y % mod;
}
}