2024. 考试的最大困扰度

解法

滑动窗口，滑动窗口的重点是左右指针变动的时机，这道题目存在两种解法，一种是将T和F的筛选分开，在代码段中使用两个while循环体进行操作

双while循环体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int Topic::maxConsecutiveAnswers(std::string answerKey, int k) {  
    int maxT = 0, maxF = 0;  
// 处理 'T' 的最长连续序列  
int leftT = 0, rightT = 0;  
int flipsT = 0;  
while (rightT < answerKey.length()) {  
    if (answerKey[rightT] == 'F') {  
        ++flipsT;  
    }  
    while (flipsT > k) {  
        if (answerKey[leftT] == 'F') {  
            --flipsT;  
        }  
        ++leftT;  
    }  
    maxT = std::max(maxT, rightT - leftT + 1);  
    ++rightT;  
}  
  
// 重置变量以处理 'F' 的最长连续序列  
int leftF = 0, rightF = 0;  
int flipsF = 0;  
while (rightF < answerKey.length()) {  
    if (answerKey[rightF] == 'T') {  
        ++flipsF;  
    }  
    while (flipsF > k) {  
        if (answerKey[leftF] == 'T') {  
            --flipsF;  
        }  
        ++leftF;  
    }  
    maxF = std::max(maxF, rightF - leftF + 1);  
    ++rightF;  
}  
  
return std::max(maxT, maxF);  
}

单循环体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
   
//使用 位运算符 >> 是因为 TF/2后的
int left = 0, res = 0, cnt[2]{};

	for (int right = 0; right < answerKey.length(); ++right)
	{
		cnt[answerKey[right] >> 1 & 1]++;
		while (cnt[0]>k && cnt[1] > k)
		{
			cnt[answerKey[left++] >> 1 & 1]--;
		}

		res = max(res,right - left +1);	
	}

	return res;
    }

关于使用以上单体循环需要补充的知识点

image-20240902152055512

下面是错误的单体循环使用方式，使用双体循环的判断去处理，逻辑复杂，不容易实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
int Topic::maxConsecutiveAnswers(string answerKey, int k)
{
	int maxT = 0, maxF = 0;
	//和最大连续内容一样，到达一定长度后就舍弃
	int leftT = 0, rightT = 0;
	int leftF = 0, rightF = 0;
	int curKT = 0, curKF = 0;//用来记录执行了多少次操作
	while (rightT < answerKey.length() && rightF < answerKey.length())
	{
		//对T进行处理
		if (answerKey[rightT] == 'T' && rightT < answerKey.length())
		{
			if (curKF > k)
			{
				//准备收缩
				while (curKF > k)
				{
					if (answerKey[leftF] == 'T')
					{
						--curKF;
					}
					++leftF;
				}
			}
			else
			{
				++rightF;
				++curKF;
			}
			++rightT;
			maxT = max(maxT, rightT - leftT + 1);
		}
		else if (answerKey[rightF] == 'F' && rightF < answerKey.length())
		{
			if (curKT > k)
			{
				while (curKT > k)
				{
					if (answerKey[leftT] == 'F')
					{
						--curKT;
					}
					++leftT;
				}
			}
			else
			{
				++rightT;
				++curKT;
			}
			++rightF;
			maxF = max(maxF, rightF - leftF + 1);
		}
	}
 
	return max(maxT, maxF);
}