欢迎大家加QQ群：623375442，可以方便群里面交流。第二题是第四题的一种特殊情况。我就单独放第四题题解了。
100443. Find the Maximum Factor Score of Array
给你一个整数数组 nums。
因子得分 定义为数组所有元素的最小公倍数（LCM）与最大公约数（GCD）的 乘积。
在 最多 移除一个元素的情况下，返回 nums 的 最大因子得分。
注意，单个数字的 LCM 和 GCD 都是其本身，而 空数组 的因子得分为 0。
lcm(a, b) 表示 a 和 b 的 最小公倍数。
gcd(a, b) 表示 a 和 b 的 最大公约数。
测试样例：
输入： nums = [2,4,8,16]
输出： 64
解释：移除数字 2 后，剩余元素的 GCD 为 4，LCM 为 16，因此最大因子得分为 4 * 16 = 64。
解答：这题暴力枚举lcm和gcd。
class Solution {
public long maxScore(int[] nums) {
long res = removeOneElement(nums, -1);
for (int i = 0; i < nums.length; ++i) {
res = Math.max(res, removeOneElement(nums, i));
}
return res;
}
private long removeOneElement(int[] nums, int t) {
long gcd = -1, lcm = -1;
for (int i = 0; i < nums.length; ++i) {
if (i != t) {
if (gcd == -1) {
gcd = nums[i];
lcm = nums[i];
} else {
gcd = gcd(gcd, nums[i]);
lcm = lcm * nums[i] / gcd(lcm, nums[i]);
}
}
}
return gcd * lcm;
}
private long gcd(long x, long y) {
while (y != 0) {
long tmp = x % y;
x = y;
y = tmp;
}
return x;
}
}100454. Find the Number of Subsequences With Equal GCD
给你一个整数数组 nums。
请你统计所有满足一下条件的 非空 子序列对 (seq1, seq2) 的数量：
- 子序列 seq1 和 seq2 不相交，意味着 nums 中 不存在 同时出现在两个序列中的下标。
- seq1 元素的 GCD 等于 seq2 元素的 GCD。
返回满足条件的子序列对的总数。
由于答案可能非常大，请返回其对 10^9 + 7 取余 的结果。
gcd(a, b) 表示 a 和 b 的 最大公约数。
子序列 是指可以从另一个数组中删除某些或不删除元素得到的数组，并且删除操作不改变其余元素的顺序。
测试样例：
输入：nums = [1,2,3,4]
输出：10
解答：这题有点脑经急转弯。注意提示的范围1 <= nums.length <= 200，1 <= nums[i] <= 200。这样猜测一下，我们设定dp的内容是第i个位置，且到达它之前左右两个子序列的gcd值。这样复杂度应该可控。
class Solution {
private static final int mod = 1_000_000_007;
public int subsequencePairCount(int[] nums) {
// dp为达到第i个位置，两个子序列的当前GCD值
Integer[][][] dp = new Integer[201][201][nums.length];
// 第一个和第二个0代表子序列中一个数字都没有
return helper(0, 0, 0, nums, dp);
}
private int helper(int l, int r, int pos, int[] nums, Integer[][][] dp) {
if (pos == nums.length) {
if (l != 0 && r != 0 && l == r) {
return 1;
} else {
return 0;
}
} else if (dp[l][r][pos] == null) {
int res = 0;
// 当前数字不加入子序列
res = (res + helper(l, r, pos + 1, nums, dp)) % mod;
// 当前数字加入左子序列
if (l == 0) {
res = (res + helper(nums[pos], r, pos + 1, nums, dp)) % mod;
} else {
res = (res + helper(gcd(l, nums[pos]), r, pos + 1, nums, dp)) % mod;
}
// 当前数字加入右子序列
if (r == 0) {
res = (res + helper(l, nums[pos], pos + 1, nums, dp)) % mod;
} else {
res = (res + helper(l, gcd(nums[pos], r), pos + 1, nums, dp)) % mod;
}
dp[l][r][pos] = res;
}
return dp[l][r][pos];
}
private int gcd(int x, int y) {
while (y != 0) {
int tmp = x % y;
x = y;
y = tmp;
}
return x;
}
}100472. Total Characters in String After Transformations II
给你一个由小写英文字母组成的字符串 s，一个整数 t 表示要执行的 转换 次数，以及一个长度为 26 的数组 nums。每次 转换 需要根据以下规则替换字符串 s 中的每个字符：
- 将 s[i] 替换为字母表中后续的 nums[s[i] - 'a'] 个连续字符。例如，如果 s[i] = 'a' 且 nums[0] = 3，则字符 'a' 转换为它后面的 3 个连续字符，结果为 "bcd"。
- 如果转换超过了 'z'，则 回绕 到字母表的开头。例如，如果 s[i] = 'y' 且 nums[24] = 3，则字符 'y' 转换为它后面的 3 个连续字符，结果为 "zab"。
返回 恰好 执行 t 次转换后得到的字符串的 长度。
由于答案可能非常大，返回其对 10……9 + 7 取余的结果。
测试样例：
输入：s = "abcyy", t = 2, nums = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2]
输出：7
解释：
- 第一次转换 (t = 1)
- 'a' 变为 'b' 因为 nums[0] == 1
- ''b' 变为 'c' 因为 nums[1] == 1
- ''c' 变为 'd' 因为 nums[2] == 1
- ''y' 变为 'z' 因为 nums[24] == 1
- ''y' 变为 'z' 因为 nums[24] == 1
- '第一次转换后的字符串为: "bcdzz"
- '第二次转换 (t = 2)
- 'b' 变为 'c' 因为 nums[1] == 1
- 'c' 变为 'd' 因为 nums[2] == 1
- 'd' 变为 'e' 因为 nums[3] == 1
- 'z' 变为 'ab' 因为 nums[25] == 2
- 'z' 变为 'ab' 因为 nums[25] == 2
- 第二次转换后的字符串为: "cdeabab"
- 字符串最终长度： 字符串为 "cdeabab"，长度为 7 个字符。
解答：这题t的范围实在太大了，没办法暴力枚举。想了一下，可以用折半的办法计算。大概思路就是假设当前字符是a，我计算一下最近2^k次方的变化，然后先跳跃一下。依此类推
class Solution {
private static final int mod = 1_000_000_007;
private class InternalData {
private TreeMap<Integer, int[][]> skipTransform;
public InternalData(List<Integer> nums) {
int[][] last = new int[26][26];
skipTransform = new TreeMap<>();
int offset = 0;
for (int n : nums) {
for (int i = 0; i < n; ++i) {
last[offset][(offset + i + 1) % 26] += 1;
}
++offset;
}
skipTransform.put(1, last);
// 计算所有2^n次数的跳跃情况
for (int i = 2; i < Integer.MAX_VALUE / 2; i = i * 2) {
int[][] tmp = new int[26][26];
for (int c = 0; c < 26; ++c) {
for (int t1 = 0; t1 < 26; ++t1) {
if (last[c][t1] > 0) {
long add = last[c][t1];
for (int t2 = 0; t2 < 26; ++t2) {
long mul = (add * last[t1][t2]) % mod;
tmp[c][t2] = (int) ((tmp[c][t2] + mul) % mod);
}
}
}
}
skipTransform.put(i, tmp);
last = tmp;
}
}
public Map.Entry<Integer, int[][]> floor(int key) {
return skipTransform.floorEntry(key);
}
}
public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
InternalData data = new InternalData(nums);
int res = 0;
int[] mem = new int[26];
Arrays.fill(mem, -1);
for (int i = 0; i < s.length(); ++i) {
if (mem[s.charAt(i) - 'a'] == -1) {
mem[s.charAt(i) - 'a'] = getResult(s.charAt(i), t, data);
}
res = (res + mem[s.charAt(i) - 'a']) % mod;
}
return res;
}
// 折半搜索
private int getResult(char c, int t, InternalData data) {
int[] add = new int[26];
add[c - 'a'] += 1;
while (t > 0) {
int[] nextAdd = new int[26];
Map.Entry<Integer, int[][]> floor = data.floor(t);
for (int i = 0; i < 26; ++i) {
if (add[i] > 0) {
long tmp = add[i];
for (int j = 0; j < 26; ++j) {
long mul = tmp * floor.getValue()[i][j] % mod;
nextAdd[j] = (int) ((nextAdd[j] + mul) % mod);
}
}
}
t -= floor.getKey();
add = nextAdd;
}
int res = 0;
for (int n : add) {
res = (res + n) % mod;
}
return res;
}
}