徐州网站建设 网站推广,城乡建设工程信息网,广州番禺区核酸检测点,自由设计师是什么意思2024. 考试的最大困扰度
一位老师正在出一场由 n 道判断题构成的考试#xff0c;每道题的答案为 true #xff08;用 ‘T’ 表示#xff09;或者 false #xff08;用 ‘F’ 表示#xff09;。老师想增加学生对自己做出答案的不确定性#xff0c;方法是 最大化 有 连续相…2024. 考试的最大困扰度
一位老师正在出一场由 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.length1 n 5 * 10410^4104answerKey[i] 要么是 ‘T’ 要么是 ‘F’1 k n
解题思路
使用两次滑动窗口
第一次维护窗口内T的数量我们需要保证我们窗口内T的数量小于或者等于K这样才能保证窗口内的元素在不超过 k 次操作的情况下可以保证全部转化为F每次尝试扩大窗口如果T的数量超出了K我们需要缩小窗口将原窗口内多余的T淘汰掉第一次维护窗口内F的数量操作与第一次相同。
代码
class Solution {
public:int maxConsecutiveAnswers(string answerKey, int k) {int l0,r0,t0,m0;while (ranswerKey.size()){while (tk){if (lranswerKey[l]T)t--;l;}mmax(m,r-l);if (answerKey[r]T)t;r;}l0,r0,t0;while (ranswerKey.size()){while (tk){if (lranswerKey[l]F)t--;l;}mmax(m,r-l);if (answerKey[r]F)t;r;}return m;}
};
