给你两个整数 m 和 n 。构造一个 m x n 的网格，其中每个单元格最开始是白色。请你用 红、绿、蓝 三种颜色为每个单元格涂色。所有单元格都需要被涂色。
涂色方案需要满足：不存在相邻两个单元格颜色相同的情况 。返回网格涂色的方法数。因为答案可能非常大， 返回 对 10^9 + 7 取余 的结果。
示例 1：
输入：m = 1, n = 1
输出：3
解释：如上图所示，存在三种可能的涂色方案。示例 2：
输入：m = 1, n = 2
输出：6
解释：如上图所示，存在六种可能的涂色方案。示例 3：
输入：m = 5, n = 5
输出：580986说明：
// todo 状压DP
给你一个由小写英文字母组成的字符串 s，一个整数 t 表示要执行的 转换 次数，以及一个长度为 26 的数组 nums。每次 转换 需要根据以下规则替换字符串 s 中的每个字符：
返回 恰好 执行 t 次转换后得到的字符串的 长度。
由于答案可能非常大，返回其对 10^9 + 7 取余的结果。
示例 1：
输入： 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 个字符。示例 2：
输入： s = "azbk", t = 1, nums = [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]
输出： 8
解释：
第一次转换 (t = 1)
'a' 变为 'bc' 因为 nums[0] == 2
'z' 变为 'ab' 因为 nums[25] == 2
'b' 变为 'cd' 因为 nums[1] == 2
'k' 变为 'lm' 因为 nums[10] == 2
第一次转换后的字符串为: "bcabcdlm"
字符串最终长度： 字符串为 "bcabcdlm"，长度为 8 个字符。说明：
对字符串执行 t 次转换，求字符串的最终长度。每次转换需要将字符 s[i] 转换为字母表中后面的 nums[s[i] - 'a'] 个连续字符，如果超过了 z 则回到字母表开头。
与 3335.字符串转换后的长度I 的区别是替换为后面的连续 nums[s[i] - 'a'] 个字符。
定义 dp[k][i] 表示第 k 次转换后，字符 (char)(i + 'a') 的出现次数。但是转换次数高达 10^9 会超出内存限制。
转换次数太大，必须想办法降低它的复杂度。想到了倍增与快速幂，可以使用矩阵描述每一次字符的转换，考虑矩阵快速幂。
定义矩阵 matrix 的第 i 行表示字母 (char)(i + 'a') 转换后的字符集合，使用行向量表示， 第 j 列为 1 表示转换后的字母为 (char)(j + 'a')。于是问题转换为 vector * matrix^t，其中 vector 表示字符串每个字符的出现次数。
/**
* @date 2025-05-14 8:56
*/
public class LengthAfterTransformations3337 {
public int lengthAfterTransformations(String s, int t, List<Integer> nums) {
int mod = 1000000007;
int[] vector = new int[26];
char[] chars = s.toCharArray();
for (char c : chars) {
vector[c - 'a']++;
}
int[][] matrix = new int[26][26];
for (int i = 0; i < 26; i++) {
for (int j = 1; j <= nums.get(i); j++) {
int index = (i + j) % 26;
matrix[i][index] = 1;
}
}
int[] cnt = pow(vector, matrix, t, mod);
int res = 0;
for (int num : cnt) {
res = (res + num) % mod;
}
return res;
}
public int[] pow(int[] vector, int[][] matrix, int exponent, int mod) {
int[] res = vector;
while (exponent > 0) {
if ((exponent & 1) == 1) {
res = multiply(res, matrix, mod);
}
matrix = square(matrix, mod);
exponent >>= 1;
}
return res;
}
public int[][] square(int[][] matrix, int mod) {
int n = matrix.length;
int[][] res = new int[n][n];
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
for (int i = 0; i < n; i++) {
res[row][col] = (int) ((res[row][col] + (long) matrix[row][i] * matrix[i][col]) % mod);
}
}
}
return res;
}
public int[] multiply(int[] vector, int[][] matrix, int mod) {
int n = vector.length;
int[] res = new int[n];
for (int col = 0; col < n; col++) {
for (int i = 0; i < n; i++) {
res[col] = (int) ((res[col] + (long) vector[i] * matrix[i][col]) % mod);
}
}
return res;
}
}
给你一个字符串 num 。如果一个数字字符串的奇数位下标的数字之和与偶数位下标的数字之和相等，那么我们称这个数字字符串是 平衡的 。
请你返回 num 不同排列 中，平衡 字符串的数目。
由于答案可能很大，请你将答案对 10^9 + 7 取余 后返回。
一个字符串的 排列 指的是将字符串中的字符打乱顺序后连接得到的字符串。
示例 1：
输入：num = "123"
输出：2
解释：
num 的不同排列包括： "123" ，"132" ，"213" ，"231" ，"312" 和 "321" 。
它们之中，"132" 和 "231" 是平衡的。所以答案为 2 。示例 2：
输入：num = "112"
输出：1
解释：
num 的不同排列包括："112" ，"121" 和 "211" 。
只有 "121" 是平衡的。所以答案为 1 。示例 3：
输入：num = "12345"
输出：0
解释：
num 的所有排列都是不平衡的。所以答案为 0 。说明：
//todo
给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从 0 开始的整数数组 tasks 中，第 i 个任务需要 tasks[i] 的力量才能完成。每个工人的力量值保存在下标从 0 开始的整数数组 workers 中，第 j 个工人的力量值为 workers[j] 。每个工人只能完成 一个 任务，且力量值需要 大于等于 该任务的力量要求值（即 workers[j] >= tasks[i] ）。
除此以外，你还有 pills 个神奇药丸，可以给 一个工人的力量值 增加 strength 。你可以决定给哪些工人使用药丸，但每个工人 最多 只能使用 一片 药丸。
给你下标从 0 开始的整数数组tasks 和 workers 以及两个整数 pills 和 strength ，请你返回 最多 有多少个任务可以被完成。
示例 1：
输入：tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1
输出：3
解释：
我们可以按照如下方案安排药丸：
- 给 0 号工人药丸。
- 0 号工人完成任务 2（0 + 1 >= 1）
- 1 号工人完成任务 1（3 >= 2）
- 2 号工人完成任务 0（3 >= 3）示例 2：
输入：tasks = [5,4], workers = [0,0,0], pills = 1, strength = 5
输出：1
解释：
我们可以按照如下方案安排药丸：
- 给 0 号工人药丸。
- 0 号工人完成任务 0（0 + 5 >= 5）示例 3：
输入：tasks = [10,15,30], workers = [0,10,10,10,10], pills = 3, strength = 10
输出：2
解释：
我们可以按照如下方案安排药丸：
- 给 0 号和 1 号工人药丸。
- 0 号工人完成任务 0（0 + 10 >= 10）
- 1 号工人完成任务 1（10 + 10 >= 15）示例 4：
输入：tasks = [5,9,8,5,9], workers = [1,6,4,2,6], pills = 1, strength = 5
输出：3
解释：
我们可以按照如下方案安排药丸：
- 给 2 号工人药丸。
- 1 号工人完成任务 0（6 >= 5）
- 2 号工人完成任务 2（4 + 5 >= 8）
- 4 号工人完成任务 3（6 >= 5）说明：
//todo
一个数组的 分数 定义为数组之和 乘以 数组的长度。
给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数 严格小于 k 的 非空整数子数组数目。
子数组 是数组中的一个连续元素序列。
示例 1：
输入：nums = [2,1,4,3,5], k = 10
输出：6
解释：
有 6 个子数组的分数小于 10 ：
- [2] 分数为 2 * 1 = 2 。
- [1] 分数为 1 * 1 = 1 。
- [4] 分数为 4 * 1 = 4 。
- [3] 分数为 3 * 1 = 3 。
- [5] 分数为 5 * 1 = 5 。
- [2,1] 分数为 (2 + 1) * 2 = 6 。
注意，子数组 [1,4] 和 [4,3,5] 不符合要求，因为它们的分数分别为 10 和 36，但我们要求子数组的分数严格小于 10 。示例 2：
输入：nums = [1,1,1], k = 5
输出：5
解释：
除了 [1,1,1] 以外每个子数组分数都小于 5 。
[1,1,1] 分数为 (1 + 1 + 1) * 3 = 9 ，大于 5 。
所以总共有 5 个子数组得分小于 5 。说明：
统计 正整数 数组中 子数组元素和 * 子数组长度 < k 的子数组个数。
统计满足条件的子数组个数，首先考虑滑动窗口。枚举右端点 right，只要 [left, right] 的分数小于 k，那么任意以 i ∈ [left, right] 为左端点的子数组的分数都小于 k，共有 right - left + 1 个。如果窗口内的分数大于等于 k，需要移出左端点，直到窗口内的分数小于 k。
/**
* @date 2025-04-28 8:41
*/
public class CountSubarrays2302 {
public long countSubarrays(int[] nums, long k) {
long res = 0L;
int n = nums.length;
int left = 0;
long sum = 0L;
int len = 0;
for (int right = 0; right < n; right++) {
sum += nums[right];
len++;
while (left < n && sum * len >= k) {
sum -= nums[left++];
len--;
}
res += right - left + 1;
}
return res;
}
}
给你一个整数数组 nums 和两个整数 minK 以及 maxK 。
nums 的定界子数组是满足下述条件的一个子数组：
返回定界子数组的数目。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [1,3,5,2,7,5], minK = 1, maxK = 5
输出：2
解释：定界子数组是 [1,3,5] 和 [1,3,5,2] 。示例 2：
输入：nums = [1,1,1,1], minK = 1, maxK = 1
输出：10
解释：nums 的每个子数组都是一个定界子数组。共有 10 个子数组。说明：
统计满足条件的子数组个数，子数组中必须包含 minK 和 maxK，并且其它元素值在 [minK, maxK] 内。
明显的滑动窗口问题，求窗口内 minK 和 maxK 的计数均大于等于 1 且元素值在 [minK, maxK] 内的子数组个数。
如果遇到不在范围内的元素，直接从下一个位置重新开始滑动，关键点是记录滑动的开始位置 start。
/**
* @date 2025-04-26 0:25
*/
public class CountSubarrays2444 {
public long countSubarrays(int[] nums, int minK, int maxK) {
int n = nums.length;
int minCnt = 0, maxCnt = 0;
int left = 0, start = 0;
long res = 0L;
for (int right = 0; right < n; right++) {
if (nums[right] < minK || nums[right] > maxK) {
left = right + 1;
start = left;
minCnt = 0;
maxCnt = 0;
continue;
}
if (nums[right] == minK) {
minCnt++;
}
if (nums[right] == maxK) {
maxCnt++;
}
while (minCnt > 0 && maxCnt > 0) {
if (nums[left] == minK) {
minCnt--;
}
if (nums[left] == maxK) {
maxCnt--;
}
left++;
}
res += left - start;
}
return res;
}
}
给你两个整数 n 和 maxValue ，用于描述一个 理想数组 。
对于下标从 0 开始、长度为 n 的整数数组 arr ，如果满足以下条件，则认为该数组是一个 理想数组 ：
返回长度为 n 的 不同 理想数组的数目。由于答案可能很大，返回对 10^9 + 7 取余的结果。
示例 1：
输入：n = 2, maxValue = 5
输出：10
解释：存在以下理想数组：
- 以 1 开头的数组（5 个）：[1,1]、[1,2]、[1,3]、[1,4]、[1,5]
- 以 2 开头的数组（2 个）：[2,2]、[2,4]
- 以 3 开头的数组（1 个）：[3,3]
- 以 4 开头的数组（1 个）：[4,4]
- 以 5 开头的数组（1 个）：[5,5]
共计 5 + 2 + 1 + 1 + 1 = 10 个不同理想数组。示例 2：
输入：n = 5, maxValue = 3
输出：11
解释：存在以下理想数组：
- 以 1 开头的数组（9 个）：
- 不含其他不同值（1 个）：[1,1,1,1,1]
- 含一个不同值 2（4 个）：[1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2]
- 含一个不同值 3（4 个）：[1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3]
- 以 2 开头的数组（1 个）：[2,2,2,2,2]
- 以 3 开头的数组（1 个）：[3,3,3,3,3]
共计 9 + 1 + 1 = 11 个不同理想数组。说明：
//todo
给你两个下标从 0 开始且长度为 n 的整数数组 nums1 和 nums2 ，两者都是 [0, 1, ..., n - 1] 的 排列 。
好三元组 指的是 3 个 互不相同 的值，且它们在数组 nums1 和 nums2 中出现顺序保持一致。换句话说，如果我们将 pos1v 记为值 v 在 nums1 中出现的位置，pos2v 为值 v 在 nums2 中的位置，那么一个好三元组定义为 0 <= x, y, z <= n - 1 ，且 pos1x < pos1y < pos1z 和 pos2x < pos2y < pos2z 都成立的 (x, y, z) 。
请你返回好三元组的 总数目 。
示例 1：
输入：nums1 = [2,0,1,3], nums2 = [0,1,2,3]
输出：1
解释：
总共有 4 个三元组 (x,y,z) 满足 pos1x < pos1y < pos1z ，分别是 (2,0,1) ，(2,0,3) ，(2,1,3) 和 (0,1,3) 。
这些三元组中，只有 (0,1,3) 满足 pos2x < pos2y < pos2z 。所以只有 1 个好三元组。示例 2：
输入：nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]
输出：4
解释：总共有 4 个好三元组 (4,0,3) ，(4,0,2) ，(4,1,3) 和 (4,1,2) 。说明：
提示：
有两个 0 ~ n - 1 的排列，好三元组指这两个排列的公共子序列，求好三元组的总数目。
// todo
给你两个 正 整数 n 和 k 。
如果一个整数 x 满足以下条件，那么它被称为 k 回文 整数 。
如果一个整数的数位重新排列后能得到一个 k 回文整数 ，那么我们称这个整数为 好 整数。比方说，k = 2 ，那么 2020 可以重新排列得到 2002 ，2002 是一个 k 回文串，所以 2020 是一个好整数。而 1010 无法重新排列数位得到一个 k 回文整数。
请你返回 n 个数位的整数中，有多少个 好 整数。
注意 ，任何整数在重新排列数位之前或者之后 都不能 有前导 0 。比方说 1010 不能重排列得到 101 。
示例 1：
输入：n = 3, k = 5
输出：27
解释：
部分好整数如下：
551 ，因为它可以重排列得到 515 。
525 ，因为它已经是一个 k 回文整数。示例 2：
输入：n = 1, k = 4
输出：2
解释：
两个好整数分别是 4 和 8 。示例 3：
输入：n = 5, k = 6
输出：2468说明：
求长度为 n 的正整数中有多少个可以重新排列成回文整数并且能够整除 k。
// todo
给你三个整数 start ，finish 和 limit 。同时给你一个下标从 0 开始的字符串 s ，表示一个 正 整数。
如果一个 正 整数 x 末尾部分是 s （换句话说，s 是 x 的 后缀），且 x 中的每个数位至多是 limit ，那么我们称 x 是 强大的 。
请你返回区间 [start..finish] 内强大整数的 总数目 。
如果一个字符串 x 是 y 中某个下标开始（包括 0 ），到下标为 y.length - 1 结束的子字符串，那么我们称 x 是 y 的一个后缀。比方说，25 是 5125 的一个后缀，但不是 512 的后缀。
示例 1：
输入：start = 1, finish = 6000, limit = 4, s = "124"
输出：5
解释：区间 [1..6000] 内的强大数字为 124 ，1124 ，2124 ，3124 和 4124 。这些整数的各个数位都 <= 4 且 "124" 是它们的后缀。注意 5124 不是强大整数，因为第一个数位 5 大于 4 。
这个区间内总共只有这 5 个强大整数。示例 2：
输入：start = 15, finish = 215, limit = 6, s = "10"
输出：2
解释：区间 [15..215] 内的强大整数为 110 和 210 。这些整数的各个数位都 <= 6 且 "10" 是它们的后缀。
这个区间总共只有这 2 个强大整数。示例 3：
输入：start = 1000, finish = 2000, limit = 4, s = "3000"
输出：0
解释：区间 [1000..2000] 内的整数都小于 3000 ，所以 "3000" 不可能是这个区间内任何整数的后缀。说明：
返回指定区间 [start, finish] 内，后缀为 s 且每个数字不超过 limit 的数字个数。
数位dp，需要特殊处理后缀，比如 s = 10，start = 101, finish = 521 还剩两位时，01 < 10, 21 > 10 都不能计数。
/**
* @date 2025-04-10 20:19
*/
public class NumberOfPowerfulInt2999 {
public long numberOfPowerfulInt(long start, long finish, int limit, String s) {
long suffix = Long.parseLong(s);
if (finish < suffix) {
return 0L;
}
int[] high = Long.toString(finish).chars().map(x -> x - '0').toArray();
int hl = high.length;
long[] mem = new long[hl];
int[] low = new int[hl--];
long tmp = start;
while (tmp > 0) {
low[hl--] = (int) (tmp % 10);
tmp /= 10;
}
Arrays.fill(mem, -1L);
return dfs(0, low, high, true, true, mem, limit, s);
}
public long dfs(int index, int[] low, int[] high, boolean isLowLimit, boolean isHighLimit, long[] mem, int limit, String s) {
if (index == high.length - s.length()) {
boolean unaviable = false;
if (isHighLimit) {
StringBuilder hr = new StringBuilder();
int tmp = index;
while (tmp < high.length) {
hr.append(high[tmp++]);
}
unaviable = Long.parseLong(hr.toString()) < Long.parseLong(s);
}
if (isLowLimit) {
StringBuilder lr = new StringBuilder();
while (index < high.length) {
lr.append(low[index++]);
}
unaviable = unaviable || Long.parseLong(lr.toString()) > Long.parseLong(s);
}
return unaviable ? 0 : 1;
}
if (!isLowLimit && !isHighLimit && mem[index] != -1) {
return mem[index];
}
long res = 0;
int up = isHighLimit ? Math.min(high[index], limit) : limit;
int down = isLowLimit ? low[index] : 0;
for (int i = down; i <= up; i++) {
res += dfs(index + 1, low, high, isLowLimit && i == low[index], isHighLimit && i == high[index], mem, limit, s);
}
if (!isHighLimit && !isLowLimit) {
mem[index] = res;
}
return res;
}
}
