【刷题日记】2024. 考试的最大困扰度

本次刷题日记的第 17 篇，力扣题为：67. 二进制求和 ，简单

一、题目描述：

今天来刷一个中等的题，乍一看是一个考试的题，仔细看了之后发现是一个修改答案的题？

看题目的话就是将给出的字符串中，修改 k 个字符来保证连续的相同字符的数量是最大的，一起来分析一下

二、思路分析：

1、这道题考察了什么思想？你的思路是什么？

这道题给了我们那些重点信息呢，瞅瞅看：

• 题目给出一个字符串，只有 T 和 F ，并给出可以修改的 k 个字符
• 修改的 K 个字符，只能修改成 T 或者是 F
• 看上去不就是一个修改字符的问题吗？那么我们需要如何去修改才能保证连续的相同字符个数达到最大呢

我们画一个图，在草稿上按照常规逻辑去框选我们期望的数据就可以得出我们想要的答案

以题目中给出的示例： answerKey = "TTFTTFTT", k = 1

看上图我们可以知道，我们用滑动的框框去框选符合我们要求的区间的时候

就可以逐个比对出哪些是符合要求的，哪些是不符合要求的，并且同样也可以计算出来连续相同的字符个数，进而计算出最大值

此处需要注意的是，题目给出的可以修改 k 个字符的条件，这个条件加入到逻辑中需要重点关注，那么剩下的，就是来翻译代码的过程了

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码，可以注意查看一下我们对于 k 的处理

编码如下：

func maxConsecutiveAnswers(answerKey string, k int) int {
    return max(helper(answerKey, k, 'T'),helper(answerKey, k, 'F'))
}
// 帮助函数，主要是计算按照要求填充 k 个指定字符的时候，该字符最长连续的个数
func helper(answerKey string, k int, ch byte) (ans int) {
    left, sum := 0, 0
    for right := range answerKey {
        if answerKey[right] != ch {
            sum++
        }
        // 如果识别到目前的区间，已经有大于 k 个非我们期望的字符，那么就要开始移动
        for sum > k {
            if answerKey[left] != ch {
                sum--
            }
            left++
        }
        // 计算符合要求的区间连续指定字符的个数，和上一个区间结果比较，取最大值
        ans = max(ans, right-left+1)
    }
    return
}
func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}

看了上述编码后就知道这个题还是非常简单的，但是思想也是相当重要的，无论做什么事情，基础要牢固 ，思路正确了，设计正确了，编码基本差不了啥了，谁来实现都一样

四、总结：

该题的时间复杂度，是 O(n) ， 此处我们也是循环了 2 次 answerKey 的长度，所以是 O(n)，空间复杂度是 O(1) ， 引入的只是尝试级别的内存消耗

原题地址：2024. 考试的最大困扰度

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~