LeetCode 2024.考试的最大困扰度

LeetCode 2024.考试的最大困扰度

2024. 考试的最大困扰度

方法一 ： dp；

对字符串进行循环遍历：

**当idx <= k 时 : **
$$ans=i+1$$
当idx > k 时 不难得出 当前字符串的长度为i-f[idx-k-1]
$$ans=max(ans,i?f[idx?k?1])$$

class Solution {
    public  int maxConsecutiveAnswers(String answerKey, int k) {
    char[] arr = answerKey.toCharArray();return Math.max(getMax(arr,k,'T'),getMax(arr,k,'F'));}static int getMax(char[] arr ,int k,char ch){
    int idx = 0,ans = 0;int n  = arr.length;int f[] = new int[n];for(int i = 0 ; i <  n ; i ++){
    if(arr[i] == ch)    f[idx++] = i;if(idx<=k)  ans=i+1;else {
    ans  =  Math.max(ans,i-f[idx-k-1]);}}return ans;}
}// f[i] = f[i-1]

方法二：滑动窗口

l 为窗口的左端 ， r 为窗口的右端，cnt记录 [l,r] 区间内查询T或F的数量

1）当cnt <= k 时 ， r 可以一直右走 同时 记录ans
$$ans=max(ans,r?l+1)$$
2）当cnt > k 时， l 往右走缩紧区间，直到cnt <= k

class Solution {
    public  int maxConsecutiveAnswers(String answerKey, int k) {
    char[] arr = answerKey.toCharArray();int n = arr.length;int cnt = 0, l = 0 ,  r = 0 , ans = 0;char ch = 'F';while( r < n ){
     // search for Fcnt += arr[r] == ch ? 1:0;while(cnt > k){
    cnt -= arr[l++] == ch?1:0;}ans = Math.max(ans,r - l + 1);r++;}ch = 'T'; cnt  = 0; l = 0; r = 0;while( r < n ){
     // search for Tcnt += arr[r] == ch ? 1:0;while(cnt > k){
    cnt -= arr[l++] == ch?1:0;}ans = Math.max(ans,r - l + 1);r++;}return ans;}
}// f[i] = f[i-1]