标签： hard

目标

给你一个整数数组 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;
    }

}

性能

目标

给你两个 正 整数 n 和 k 。

如果一个整数 x 满足以下条件，那么它被称为 k 回文 整数 。

• x 是一个 回文整数 。
• 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

说明：

• 1 <= n <= 10
• 1 <= k <= 9

思路

求长度为 n 的正整数中有多少个可以重新排列成回文整数并且能够整除 k。

// todo

代码

性能

目标

Alice 是 n 个花园的园丁，她想通过种花，最大化她所有花园的总美丽值。

给你一个下标从 0 开始大小为 n 的整数数组 flowers ，其中 flowers[i] 是第 i 个花园里已经种的花的数目。已经种了的花 不能 移走。同时给你 newFlowers ，表示 Alice 额外可以种花的 最大数目 。同时给你的还有整数 target ，full 和 partial 。

如果一个花园有 至少 target 朵花，那么这个花园称为 完善的 ，花园的 总美丽值 为以下分数之 和 ：

• 完善 花园数目乘以 full.
• 剩余 不完善 花园里，花的 最少数目 乘以 partial 。如果没有不完善花园，那么这一部分的值为 0 。

请你返回 Alice 种最多 newFlowers 朵花以后，能得到的 最大 总美丽值。

示例 1：

输入：flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1
输出：14
解释：Alice 可以按以下方案种花
- 在第 0 个花园种 2 朵花
- 在第 1 个花园种 3 朵花
- 在第 2 个花园种 1 朵花
- 在第 3 个花园种 1 朵花
花园里花的数目为 [3,6,2,2] 。总共种了 2 + 3 + 1 + 1 = 7 朵花。
只有 1 个花园是完善的。
不完善花园里花的最少数目是 2 。
所以总美丽值为 1 * 12 + 2 * 1 = 12 + 2 = 14 。
没有其他方案可以让花园总美丽值超过 14 。

示例 2：

输入：flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6
输出：30
解释：Alice 可以按以下方案种花
- 在第 0 个花园种 3 朵花
- 在第 1 个花园种 0 朵花
- 在第 2 个花园种 0 朵花
- 在第 3 个花园种 2 朵花
花园里花的数目为 [5,4,5,5] 。总共种了 3 + 0 + 0 + 2 = 5 朵花。
有 3 个花园是完善的。
不完善花园里花的最少数目为 4 。
所以总美丽值为 3 * 2 + 4 * 6 = 6 + 24 = 30 。
没有其他方案可以让花园总美丽值超过 30 。
注意，Alice可以让所有花园都变成完善的，但这样她的总美丽值反而更小。

说明：

• 1 <= flowers.length <= 10^5
• 1 <= flowers[i], target <= 10^5
• 1 <= newFlowers <= 10^10
• 1 <= full, partial <= 10^5

思路

有一个整数数组 flowers，flowers[i] 表示下标为 i 的花园种植的花的数目。花园的美丽值通过以下方式计算：

• 花园中花的数目大于等于 target，称该花园是完善的，美丽值 = 所有完善花园的个数 * full
• 花园中花的数目小于 target，美丽值 = 所有花园中花的最小数目 * partial

Alice 可以向任意花园中种花，新种的花的数目不超过 newFlowers，求花园的最大美丽值。

// todo

代码

性能

目标

给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。

当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

示例 1：

输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。

示例 2：

输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。

说明：

• 3 <= s.length <= 2000
• s​​​​​​ 只包含小写英文字母。

思路

判断能否将给定字符串分割成三个非空回文子串。

核心逻辑：

• 计算所有子串是否是回文。
• 从起点 i = 0 开始，枚举所有终点 j，如果是 s[i~j] 是回文，k-- 接着以 j + 1 为起点继续递归搜索。
• 结束条件是 i == s.length() || k < 0，如果 k == 0 返回 true。

代码

/**
 * @date 2025-03-04 15:58
 */
public class CheckPartitioning1745 {

    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (boolean[] row : isPalindrome) {
            Arrays.fill(row, true);
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && isPalindrome[i + 1][j - 1];
            }
        }
        char[][] mem = new char[n][4];
        return dfs(0, 3, isPalindrome, s, mem);
    }

    public boolean dfs(int i, int k, boolean[][] isPalindrome, String s, char[][] mem) {
        int n = s.length();
        if (i == n || k < 0) {
            return k == 0;
        }
        if (mem[i][k] != '\u0000') {
            return mem[i][k] == 'T';
        }
        boolean res = false;
        for (int j = i; j < n; j++) {
            if (isPalindrome[i][j]) {
                res = res || dfs(j + 1, k - 1, isPalindrome, s, mem);
            }
        }
        mem[i][k] = res ? 'T' : 'F';
        return res;
    }

}

性能