LeetCode-2024 考试的最大困扰度

简介: LeetCode-2024 考试的最大困扰度

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/maximize-the-confusion-of-an-exam

题目描述

一位老师正在出一场由 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 * 104

answerKey[i] 要么是 'T' ,要么是 'F'

1 <= k <= n

解题思路

看起来像个滑动窗口题,确实是滑动窗口,刚刚开始思路是记录TF的变化位置,以变化位置为起点分别求最长的长度,不过时间复杂度为O(n2)并且总漏掉几种情况,那就只能分类讨论了,修改可以将T修改为F,也可以将F修改为T,分两种情况,分别用滑动窗口求出最长长度,取最大值。

求最长的过程可以用一个滑动窗口,并且维护窗口中修改过的字符次数始终小于等于k。

代码展示

class Solution {
public:
    int myMax(string answerKey, int k, char c)
    {
        int iLeft = 0, iRight = 0, iSum = 0, iMax = 0;
        while(iRight < answerKey.size())
        {
            if(answerKey[iRight] == c)
            {
                iRight++;
            }
            else
            {
                if(iSum < k)
                {
                    iSum++;
                    iRight++;
                }
                else
                {
                    if(answerKey[iLeft] != c)
                    {
                        iSum--;
                    }
                    iLeft++;
                }   
            }
            iMax = max(iMax, iRight - iLeft);
        }
        return iMax;
    }
    int maxConsecutiveAnswers(string answerKey, int k) {
        return max(myMax(answerKey, k, 'T'), myMax(answerKey, k, 'F'));
    }
};

运行结果

 

相关文章
|
7月前
|
Go
golang力扣leetcode 2024.考试的最大困扰度
golang力扣leetcode 2024.考试的最大困扰度
42 0
|
7月前
leetcode-2024:考试的最大困扰度
leetcode-2024:考试的最大困扰度
36 0
|
C++ Python
LeetCode每日一题题解:2024. 考试的最大困扰度-题解-python && C++源代码
LeetCode每日一题题解:2024. 考试的最大困扰度-题解-python && C++源代码
|
算法 Windows
[leetcode] 2024. 考试的最大困扰度 | 双指针
题意:给出只含有两种字符的字符串以及一个次数限制k,问最多修改k个位置(T->F/F->T),最大的连续的字符串的长度是多少 思路:双指针/滑动窗口 假如说我们要找修改后连续的T最长的长度,我们可以{ 枚举右端点,并统计当前不等于’T’的字符串的个数,并且统计数量,记为c n t cntcnt 如果说左区间到右区间的c n t cntcnt 是否 小于等于 k{ (1)如果说数量上大于k了,就只能让左端点向右,并记录cnt的减小情况,直到cnt <= k } 过程中统计区间长度并记录最大值 }
118 0
[leetcode] 2024. 考试的最大困扰度 | 双指针
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
58 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
120 2
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
26 1
|
3月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
4月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
65 7