LeetCode周记 EP11

2024-09-08

字数统计: 2.3k字 | 阅读时长: 11分

前言

这周感觉还可以吧，有两道周赛做过的题。

一个感悟是，做题要遵守基本法，空间和时间是此消彼长的，动态规划的状态定义也是有章可循的。

本周主题：滑动窗口、枚举、动态规划

题目：

240902每日一题—Maximize the Confusion of an Exam
240905每日一题—Happy Students
240907每日一题—Find the Maximum Length of a Good Subsequence II
Maximize the Confusion of an Exam

Maximize the Confusion of an Exam

A teacher is writing a test with n true/false questions, with ‘T’ denoting true and ‘F’ denoting false. He wants to confuse the students by maximizing the number of consecutive questions with the same answer (multiple trues or multiple falses in a row).

You are given a string answerKey, where answerKey[i] is the original answer to the ith question. In addition, you are given an integer k, the maximum number of times you may perform the following operation:
Change the answer key for any question to ‘T’ or ‘F’ (i.e., set answerKey[i] to ‘T’ or ‘F’).

Return the maximum number of consecutive ‘T’s or ‘F’s in the answer key after performing the operation at most k times.

这道题本来想考虑DP，状态为“最后一个元素为i，替换次数为j时的最大连续子串长度”，但有问题，最后一个元素可能会被替换，且最大子串只在全替换为T或F时才出现，怎么弄怎么别扭，还是用滑窗吧。

滑动窗口

在指定字符的情况下，可以计算其最大连续数目。使用滑动窗口的方法，从左到右枚举右端点，维护区间中另一种字符的数量为 sum，当 sum 超过 k，我们需要让左端点右移，直到 sum≤k。移动过程中，我们记录滑动窗口的最大长度，即为指定字符的最大连续数目。答案为分别指定字符为 T 和 F 时的最大连续数目的较大值。

class Solution {
    public int maxConsecutiveAnswers(String answerKey, int k) {
        return Math.max(maxConsecutiveChar(answerKey, k, 'T'), maxConsecutiveChar(answerKey, k, 'F'));
    }

    public int maxConsecutiveChar(String answerKey, int k, char ch) {
        int n = answerKey.length();
        int ans = 0;
        for (int left = 0, right = 0, sum = 0; right < n; right++) {
            sum += answerKey.charAt(right) != ch ? 1 : 0;
            while (sum > k) {
                sum -= answerKey.charAt(left++) != ch ? 1 : 0;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

Happy Students

Happy Students

You are given a 0-indexed integer array nums of length n where n is the total number of students in the class. The class teacher tries to select a group of students so that all the students remain happy.

The ith student will become happy if one of these two conditions is met:

The student is selected and the total number of selected students is strictly greater than nums[i].

The student is not selected and the total number of selected students is strictly less than nums[i].

Return the number of ways to select a group of students so that everyone remains happy.

一开始拿到没想出好办法，回溯暴力了一下，超时了。

// author: SilenceZheng66
class Solution {
    public int res;
    public Set<Set<Integer>> mem;

    public int countWays(List<Integer> nums) {
        int n = nums.size();
        res = 0;
        mem = new HashSet<>();
        Set<Integer> set = new HashSet<>();
        bt(nums, set, 0);
        return res;
    }

    public void bt(List<Integer> nums, Set<Integer> selected, int p){
        boolean success = true;
        for(int i=0;i<nums.size();i++){
            if(selected.contains(i)){
                if(selected.size()<=nums.get(i)){
                    success = false;
                    break;
                }
            }else{
                if(selected.size()>=nums.get(i)){
                    success = false;
                    break;
                }
            }
        }
        if(success&&!mem.contains(selected)){
            mem.add(selected);
            res++;
        }
        // System.out.println(selected.toString());
        if(p==nums.size()) return;
        for(int i=p;i<nums.size();i++){
            if(selected.contains(i)) continue;
            selected.add(i);
            bt(nums, selected, p+1);
            selected.remove(i);
        }
    }
}

实际上需要想明白选中人数为k时方案唯一，再按照这个思路去枚举就可以了。

枚举

根据题意可知，假设数组 nums 的长度为 n，此时设选中学生人数为 k，此时 k∈[0,n]，k 应满足如下：

所有满足 nums[i]<k 的学生应被选中；
所有满足 nums[i]>k 的学生不应被选中；
不能存在 nums[i]=k 的学生；

这意味着在确定当前已择中学生人数的前提下，则此时选择方案是唯一的，为方便判断，我们把 nums 从小到大排序。我们枚举选中的人数 k，由于 nums 已有序，此时最优分组一定是前 k 个学生被选中，剩余的 n−k 个学生不被选中，此时只需要检测选中的 k 个学生中的最大值是否满足小于 k，未被选中的学生中的最小值是否满足大于 k 即可，如果同时满足上述两个条件，则该分配方案可行，最终返回可行的方案计数即可，需要注意处理好边界 0 与 n。

class Solution {
    public int countWays(List<Integer> nums) {
        int n = nums.size();
        int res = 0;
        Collections.sort(nums);
        for (int k = 0; k <= n; k++) {
            // 前 k 个元素的最大值是否小于 k
            if (k > 0 && nums.get(k - 1) >= k) {
                continue;
            }
            // 后 n - k 个元素的最小值是否大于 k
            if (k < n && nums.get(k) <= k) {
                continue;
            }
            res++;
        }
        return res;
    }
}

Find the Maximum Length of a Good Subsequence II

Find the Maximum Length of a Good Subsequence II

You are given an integer array nums and a non-negative integer k. A sequence of integers seq is called good if there are at most k indices i in the range [0, seq.length - 2] such that seq[i] != seq[i + 1].

Return the maximum possible length of a good subsequence of nums.

周赛原题，当时DP都没想出来，这周把基础DP想通了，先写一下。

拆分子问题：从seq中取出最后一个，则有两种情况
- 情况一：seq中的前后不等对数量不变，则原问题变成了[0,i]上不超过k的
- 情况二：不等对数量减1，原问题变成了[0,i]上不超过k-1的
定义状态dp[i][j]表示最后一个数为i时不超过j的最大长度
状态转移：dp[i][j] = Max(遍历0到i-1中和i位置元素相同的j取最大, 遍历[0,i-1][j-1]取最大)

// author: SilenceZheng66
class Solution {
    public int maximumLength(int[] nums, int k) {
        int n = nums.length;
        int[][] dp = new int[n][k+1];
        for(int i=0;i<k+1;i++){
            dp[0][i] = 1;
        }
        // 计算
        for(int i=1;i<n;i++){
            for(int j=0;j<k+1;j++){
                int max = 0;
                int maxInd = 0;
                for(int o=0;o<i;o++){
                    if(nums[o]==nums[i]&&max<=dp[o][j]){
                        max = dp[o][j];
                        maxInd = o;
                    }
                }
                if(j>0){
                    int max2 = 0;
                    int maxInd2 = 0;
                    for(int o=0;o<i;o++){
                        if(max2<=dp[o][j-1]){
                            max2 = dp[o][j-1];
                            maxInd2 = o;
                        }
                    }
                    if(max2>max){
                        max = max2;
                        maxInd = maxInd2;
                    }
                }
                dp[i][j] = max+1;
            }
        }
        int res = 0;
        for(int i=0;i<n;i++) res=Math.max(res, dp[i][k]);
        return res;
    }
}

那么为什么这道题不能用01背包的状态来做呢？看起来不就是一个从一堆元素中选若干个的问题吗？这是因为01背包中，背包容量实际上包含了前序选择信息的最优解，即在当前背包容量支持放入当前物品时一定会选择放入。而对于本题来说，当前状态的前一个或上一个（指j-1和i-1）状态并不一定是对于本状态转移来说最优的，因为当前元素和前序元素中的某个值匹配时产生了更优解，而这个更优解是随遍历元素不断变动的。

想通了这一点，舒服多了。。。当时困扰我好几天。

然而上面的方法在大数据范围下还是不行，存在太多循环计算，下面介绍优化方案。

动态规划

PS：这题解写的依托，还是看我之前周赛时候的题解吧。

我们在上面的方案基础上优化，上面的时间复杂度是$O(n^2k)$。假设当前元素i的前序元素为x，可以枚举两种情况：

nums $[i] \neq n u m s[x]$, 对于此情况, 可以维护一个长度为 $k$ 的辅助数组 $z d$ 。其中 $z d[j]$ 表示枚举到位置 $i$ 之前，有 $j$ 个数字与其在序列中的后一个不相等的最长合法序列的长度，那么可以直接写出转移 $d p[i][j]=z d[j-1]+1$ 。
nums $[i]=n u m s[x]$, 假设有下标 $a<b<c$, 并且 nums $[a]=$ $n u m s[b]=\operatorname{nums}[c]$, 对于 $c$ 来说如果选取由 $a$ 转移过来计算答案, 那么一定不如 $a \rightarrow b \rightarrow c$ 更优, 所以会选取下标最近的相同的数进行转移。针对这种情况， $d p$ 使用哈希表维护能节省一些空间，并且在哈希表中用 $n u m s[i]$ 替换 $i$ 。

在每一次遍历 $i$ 计算完后更新 $z d$ ，最后的 $z d[k]$ 就是答案。

class Solution {
    public int maximumLength(int[] nums, int k) {
        int len = nums.length;
        Map<Integer, int[]> dp = new HashMap<Integer, int[]>();
        int[] zd = new int[k + 1];

        for (int i = 0; i < len; i++) {
            int v = nums[i];
            dp.putIfAbsent(v, new int[k + 1]);

            int[] tmp = dp.get(v);
            for (int j = 0; j <= k; j++) {
                tmp[j] = tmp[j] + 1;
                if (j > 0) {
                    tmp[j] = Math.max(tmp[j], zd[j - 1] + 1);
                }
            }
            for (int j = 0; j <= k; j++) {
                zd[j] = Math.max(zd[j], tmp[j]);
            }
        }
        return zd[k];
    }
}