月度归档： 2024 年 9 月

目标

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，其中 n 是班级中学生的总数。班主任希望能够在让所有学生保持开心的情况下选出一组学生：

如果能够满足下述两个条件之一，则认为第 i 位学生将会保持开心：

• 这位学生被选中，并且被选中的学生人数 严格大于 nums[i] 。
• 这位学生没有被选中，并且被选中的学生人数 严格小于 nums[i] 。

返回能够满足让所有学生保持开心的分组方法的数目。

示例 1：

输入：nums = [1,1]
输出：2
解释：
有两种可行的方法：
班主任没有选中学生。
班主任选中所有学生形成一组。 
如果班主任仅选中一个学生来完成分组，那么两个学生都无法保持开心。因此，仅存在两种可行的方法。

示例 2：

输入：nums = [6,0,3,3,6,7,2,7]
输出：3
解释：
存在三种可行的方法：
班主任选中下标为 1 的学生形成一组。
班主任选中下标为 1、2、3、6 的学生形成一组。
班主任选中所有学生形成一组。

说明：

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

思路

从数组中选择一组元素，使之满足该组元素个数严格大于组中所有元素值并且严格小于未被选择的元素值，求满足条件的所有选择数。

注意到元素值不超过数组长度，可以先统计各元素值的出现次数 cnt[i]，然后遍历 cnt。

这道题的关键是要意识到：值相同的元素要么同时被选，要么同时不被选。因为选择的元素个数 sum 应该大于所有选择的元素值，小于所有未选择的元素值，一个元素不可能既小于 sum 又大于 sum。题目的本质是将学生成两组（被选择的和未被选择的），选择的标准是根据所选人数动态变化的，水平相同的学生要么都选，要么都不选，要一碗水端平，这就是题目名想要表达的处世哲学吧。

• 当 cnt[0] == 0 时，说明所有元素都大于0，因此可以一个都不选。
• 当 cnt[i] != 0 时，如果我们想要选择这些元素值为i的学生，需要满足选择后的学生总数 sum 大于 i，并且 cnt[i+1] ~ cnt[sum] 应该都为0，否则就存在小于 sum 但是未被选的学生了。

官网题解使用的是排序，满足 sorted[i - 1] < i && i < sorted[i] 时累加计数。不过排序的复杂度是O(nlogn)，其实我们的计数数组也是有序的，算是计数排序吧，时间复杂度为O(n)。

代码

/**
 * @date 2024-09-04 10:29
 */
public class CountWays2860 {
    public int countWays(List<Integer> nums) {
        int n = nums.size();
        int[] cnt = new int[n];
        for (Integer num : nums) {
            cnt[num]++;
        }
        int[] prefix = new int[n];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + cnt[i];
        }
        int res = cnt[0] > 0 ? 0 : 1;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += cnt[i];
            if (sum > i && cnt[i] != 0 && prefix[Math.min(n - 1, sum)] == prefix[i]) {
                res++;
            }
        }
        return res;
    }
}

性能

目标

给你一个下标从 0 开始的整数数组 nums ，它表示一个班级中所有学生在一次考试中的成绩。老师想选出一部分同学组成一个 非空 小组，且这个小组的 实力值 最大，如果这个小组里的学生下标为 i0, i1, i2, ... , ik ，那么这个小组的实力值定义为 nums[i0] * nums[i1] * nums[i2] * ... * nums[ik​] 。

请你返回老师创建的小组能得到的最大实力值为多少。

示例 1：

输入：nums = [3,-1,-5,2,5,-9]
输出：1350
解释：一种构成最大实力值小组的方案是选择下标为 [0,2,3,4,5] 的学生。实力值为 3 * (-5) * 2 * 5 * (-9) = 1350 ，这是可以得到的最大实力值。

示例 2：

输入：nums = [-4,-5,-4]
输出：20
解释：选择下标为 [0, 1] 的学生。得到的实力值为 20 。我们没法得到更大的实力值。

说明：

• 1 <= nums.length <= 13
• -9 <= nums[i] <= 9

思路

有一个存在负数的数组，求它的非空子序列使得子序列的乘积最大。

首先，要选择所有正数，不能选零（除非全是零），负数必须成对的选（可以使用栈来保存）。可以将数组从小到大排序，从后向前取所有大于零的值，然后再从前向后取，判断栈是否为空，为空入栈，非空出栈，直到零。特别需要注意的是初值的设置需要分情况讨论，如果全是零或者至多一个负数，直接返回零。如果至少有一个正数，则初值设为1。如果全是负数，初值设为第一个元素，之所以不设为1是因为如果只有一个负数，那么就应该取这个值，如果设为1后面再配对的话就不对了，所以需要特殊处理成对匹配的情况。

代码

/**
 * @date 2024-09-03 8:57
 */
public class MaxStrength2708 {

    public long maxStrength(int[] nums) {
        long res = 1L;
        Arrays.sort(nums);
        int n = nums.length;
        int i = n - 1;
        for (; i >= 0; i--) {
            if (nums[i] > 0) {
                res *= nums[i];
            } else if (nums[i] < 0) {
                // 跳过0，使i指向最后一个负数
                break;
            }
        }
        int j = 0;
        boolean flag = true;
        // 至多一个负数，其余全是0，返回0。
        if (i <= 0 && nums[n - 1] == 0) {
            return 0L;
        } else if (i == n - 1) {
            // 如果全是负数
            res = nums[0];
            flag = false;
            j = 1;
        }
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (; j <= i; j++) {
            if (nums[j] < 0) {
                if (stack.isEmpty() && flag) {
                    stack.push(nums[j]);
                } else {
                    if (!flag) {
                        res *= nums[j];
                    } else {
                        res *= stack.pop() * nums[j];
                    }
                    flag = true;
                }
            }
        }
        return res;
    }

}

性能

目标

一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。（也就是连续出现 true 或者连续出现 false）。

给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：

• 每次操作中，将问题的正确答案改为 'T' 或者 'F' （也就是将 answerKey[i] 改为 'T' 或者 'F' ）。

请你返回在不超过 k 次操作的情况下，最大 连续 'T' 或者 'F' 的数目。

示例 1：

输入：answerKey = "TTFF", k = 2
输出：4
解释：我们可以将两个 'F' 都变为 'T' ，得到 answerKey = "TTTT" 。
总共有四个连续的 'T' 。

示例 2：

输入：answerKey = "TFFT", k = 1
输出：3
解释：我们可以将最前面的 'T' 换成 'F' ，得到 answerKey = "FFFT" 。
或者，我们可以将第二个 'T' 换成 'F' ，得到 answerKey = "TFFF" 。
两种情况下，都有三个连续的 'F' 。

示例 3：

输入：answerKey = "TTFTTFTT", k = 1
输出：5
解释：我们可以将第一个 'F' 换成 'T' ，得到 answerKey = "TTTTTFTT" 。
或者我们可以将第二个 'F' 换成 'T' ，得到 answerKey = "TTFTTTTT" 。
两种情况下，都有五个连续的 'T' 。

说明：

• n == answerKey.length
• 1 <= n <= 5 * 10^4
• answerKey[i] 要么是 'T' ，要么是 'F'
• 1 <= k <= n

思路

有一个字符串 answerKey 由 T 或 F 组成, 允许我们执行 k 次操作，每次操作可以将字符串中的 T 改为 F 或者 F 改为 T。问 T 或 F 可能的最大连续个数。

这道题没有做出来，想着使用动态规划去做，但是没有找到合适的状态定义。比如 dp[i][j][k] 表示 [0,i] 以 T 或 F 结尾剩余操作次数 k 时的最大连续个数。2 x 10^8 的存储空间肯定不行。

题解说是滑动窗口、或者 前缀和 + 二分查找，也有使用动态规划的。

这道题的难点在于想明白这 k 次操作必须统一，要么全部从 T 改为 F，要么全部从 F 改为 T，才能使连续个数最大。因为如果 T 的连续个数最多，并且存在将 T 改为 F 的操作，那么我们总可以撤回该操作，并将一个 F 改为 T（如果存在的话，如果不存在说明全是T，撤销操作也会加一） 使得连续个数至少加一。

网友题解中的动态规划是这样定义的 dp[i] 表示 [0,i] 中以 answerKey[i] 结尾的连续后缀个数。这里的前提就是遇到不连续的统一从 T 改为 F 或者 从 F 改为 T 使之连续，如果超过了可操作的次数，需要撤回最早的操作，使得当前后缀连续。后缀连续个数可以用当前下标减去最早进行操作的下标计算得到（使用链表保存操作的下标，获取链表head记录的下标后将其删，再将当前下标加入链表末尾）。在计算dp过程中记录其最大值即为最大连续个数。如果对这个动态规划进行存储优化，那就是滑动窗口。

寻找一个窗口，使得窗口内的 T 或者 F 个数小于等于 k，并且使 F 或者 T 的个数最大。滑动窗口的套路一般是枚举右边界，如果条件不满足，更新左边界直到条件满足。

二分的做法本质也是滑动窗口，枚举左边界，二分查找能够到达的最远右边界。

代码

/**
 * @date 2024-09-02 16:55
 */
public class MaxConsecutiveAnswers2024 {

    /**
     * 前缀和 + 二分查找
     * 其实本质也是滑动窗口，枚举左边界，二分查找最远的右边界
     * O(nlogn) 62ms
     */
    public int maxConsecutiveAnswers_v1(String answerKey, int k) {
        int n = answerKey.length();
        int[] prefix = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            if (answerKey.charAt(i - 1) == 'T') {
                prefix[i] = prefix[i - 1] + 1;
            } else {
                prefix[i] = prefix[i - 1];
            }
        }
        int res = 0;
        for (int i = 1; i <= n; i++) {
            int l = i, r = n;
            int mid = l + (r - l) / 2;
            while (l <= r) {
                int num = mid - i + 1;
                int cnt = prefix[mid] - prefix[i - 1];
                if (num - cnt <= k || cnt <= k) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
                mid = l + (r - l) / 2;
            }
            res = Math.max(res, r - i + 1);
        }
        return res;
    }

    /**
     * 滑动窗口 O(n)
     * 21ms
     */
    public int maxConsecutiveAnswers(String answerKey, int k) {
        return Math.max(process(answerKey, k, 'T'), process(answerKey, k, 'F'));
    }

    public int process(String answerKey, int k, char turnTo) {
        int n = answerKey.length();
        int res = 0;
        List<Integer> optsIndex = new LinkedList<>();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (answerKey.charAt(i) != turnTo) {
                if (k > 0) {
                    k--;
                    optsIndex.add(i);
                    cnt++;
                } else {
                    cnt = i - optsIndex.remove(0);
                    optsIndex.add(i);
                }
            } else {
                cnt++;
            }
            res = Math.max(res, cnt);
        }
        return res;
    }

}

性能