标签： hard

目标

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

说明：

• n == ratings.length
• 1 <= n <= 2 * 10^4
• 0 <= ratings[i] <= 2 * 10^4

思路

n 个孩子站成一排，ratings 表示每个孩子的评分。现在需要给孩子分发糖果，要求每个孩子至少分配一个糖果，并且相邻的两个孩子，评分高的孩子分得的糖果大于评分低的孩子分得的糖果，返回需要准备的最少糖果数目。

官网题解提供了一种常数空间复杂度的写法，记录评分严格递增与严格递减序列长度：

• 当处于严格递增序列时，分配的糖果比前面的多一个即可
• 如果评分相同，则分配一个糖果并重置序列长度
• 当处于严格递减序列时，分配递减序列长度个糖果，相当于递增序列的逆过程
• 需要特殊处理递增序列与递减序列长度相同的情况

看下面的例子：

评分 4 5 4 3 2 1，
    a b c d e f
    1 2 1
当处理到 c 时，处于下降序列，我们给他分配 1 个糖果
    1 3 2 1
当处理到 d 时，仍处于下降序列，需要给 c 多分配一个糖果，即 2 个，发现这时与 b 分配的相同，不满足要求，需要给 b 也多分配一个，共 3 个
    1 4 3 2 1
当处理到 e 时，仍处于下降序列，需要给 b c d 多分配一个，共 4 个
    1 5 4 3 2 1
当处理到 f 时，仍处于下降序列，需要给 b c d e 多分配一个糖果，共 5 个

相当于往递减序列的头部插入递减序列长度个糖果，视为反向的递增，当递增序列与递减序列长度相同时需要特殊处理。

代码

/**
 * @date 2024-12-11 9:18
 */
public class Candy135 {

    public int candy_v3(int[] ratings) {
        int n = ratings.length;
        int increase = 1;
        int decrease = 0;
        int res = 1;
        int prev = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] >= ratings[i - 1]) {
                prev = ratings[i] == ratings[i - 1] ? 1 : prev + 1;
                res += prev;
                increase = prev;
                decrease = 0;
            } else {
                decrease++;
                if (decrease == increase) {
                    decrease++;
                }
                res += decrease;
                prev = 1;
            }
        }
        return res;
    }

}

性能

目标

给你两个整数 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

说明：

• 1 <= m <= 5
• 1 <= n <= 1000

思路

// todo 状压DP

代码

性能

目标

给你一个由小写英文字母组成的字符串 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 取余的结果。

示例 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 个字符。

说明：

• 1 <= s.length <= 10^5
• s 仅由小写英文字母组成。
• 1 <= t <= 10^9
• nums.length == 26
• 1 <= nums[i] <= 25

思路

对字符串执行 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;
    }

}

性能

目标

给你 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）

说明：

• n == tasks.length
• m == workers.length
• 1 <= n, m <= 5 * 10^4
• 0 <= pills <= m
• 0 <= tasks[i], workers[j], strength <= 10^9

思路

//todo

代码

性能

目标

一个数组的 分数 定义为数组之和 乘以 数组的长度。

• 比方说，[1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 。

给你一个正整数数组 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 。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5
• 1 <= k <= 10^15

思路

统计 正整数 数组中 子数组元素和 * 子数组长度 < 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 的定界子数组是满足下述条件的一个子数组：

• 子数组中的 最小值 等于 minK 。
• 子数组中的 最大值 等于 maxK 。

返回定界子数组的数目。

子数组是数组中的一个连续部分。

示例 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 个子数组。

说明：

• 2 <= nums.length <= 10^5
• 1 <= nums[i], minK, maxK <= 10^6

思路

统计满足条件的子数组个数，子数组中必须包含 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;
    }

}

性能