leetcode2024_go_考试的最大困扰度

题目

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

解题思路分析

1、滑动窗口-双指针；时间复杂度O(n)，空间复杂度O(n)

func maxConsecutiveAnswers(answerKey string, k int) int {
   n := len(answerKey)
   arr := make([]int, n)
   for i := 0; i < n; i++ {
      if answerKey[i] == 'T' {
         arr[i] = 1
      }
   }
   a := longestOnes(arr, k)
   arr = make([]int, n)
   for i := 0; i < n; i++ {
      if answerKey[i] == 'F' {
         arr[i] = 1
      }
   }
   b := longestOnes(arr, k)
   return max(a, b)
}

// leetcode 1004.最大连续1的个数III
func longestOnes(A []int, K int) int {
   res := 0
   left, right := 0, 0
   count := 0
   for right = 0; right < len(A); right++ {
      if A[right] == 0 {
         count++
      }
      for count > K {
         if A[left] == 0 {
            count--
         }
         left++
      }
      res = max(res, right-left+1)
   }
   return res
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

2、滑动窗口-双指针；时间复杂度O(n)，空间复杂度O(1)

func maxConsecutiveAnswers(answerKey string, k int) int {
   n := len(answerKey)
   res := 0
   left, right := 0, 0
   countA, countB := 0, 0
   for ; right < n; right++ {
      if answerKey[right] == 'T' {
         countA++
      } else {
         countB++
      }
      for countA > k && countB > k { // 都大于k时，滑动窗口才移动
         if answerKey[left] == 'T' {
            countA--
         } else {
            countB--
         }
         left++
      }
      res = max(res, right-left+1)
   }
   return res
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

3、滑动窗口-双指针；时间复杂度O(n)，空间复杂度O(n)

func maxConsecutiveAnswers(answerKey string, k int) int {
   arr := []byte(answerKey)
   return max(longestOnes(arr, k, 'T'), longestOnes(arr, k, 'F'))
}

func longestOnes(A []byte, K int, target byte) int {
   res := 0
   left, right := 0, 0
   count := 0
   for right = 0; right < len(A); right++ {
      if A[right] == target {
         count++
      }
      for count > K {
         if A[left] == target {
            count--
         }
         left++
      }
      res = max(res, right-left+1)
   }
   return res
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}