Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

73rd day 2021.03.29

2024. The greatest frustration of exams

  • Leetcode: leetcode-cn.com/problems/ma…
  • Difficulty: Medium
  • Method: double pointer, sliding window

Topic describes

  • A teacher was giving an examination of n true or false questions, each with an answer of true (represented by ‘T’) or false (represented by ‘F’). Teachers want to increase students’ uncertainty about their answers by maximizing the number of questions that have the same result consecutively. (that is, continuous true or continuous false).
  • Give you the string answerKey, where answerKey[I] is the correct result of question I. In addition, you are given an integer k, indicating the maximum number of times you can perform the following operations:
  • For each operation, change the correct answer to the question to ‘T’ or ‘F’ (that is, change answerKey[I] to ‘T’ or ‘F’).
  • Return the maximum number of consecutive ‘T’ or ‘F’ operations without exceeding k operations.

The sample

  • Example 1
Input: answerKey = "TTFF", k = 2 Output: 4 Explanation: We can change both 'F' to 'T' to get answerKey = "TTTT". There are four consecutive'T's.Copy the code
  • Example 2
Input: answerKey = "TFFT", k = 1 Output: 3 Explanation: We can replace the front 'T' with 'F' to get answerKey = "FFFT". Alternatively, we can replace the second 'T' with 'F' and get answerKey = "TFFF". In both cases, there are three consecutive 'F' s.Copy the code

prompt

  • n == answerKey.length
  • 1 <= n <= 5 * 10^4
  • AnswerKey [I] is either ‘T’ or ‘F’
  • 1 <= k <= n

Their thinking

The way we started out

  • You are given an arrayanswerKeyArray, which containsT and F, you need to use no more thanKOperation, to modifyanswerKeyArray, returns the maximum contiguous value that can be obtainedTorFThe number of
  • Note: They say not more thanKSo it can be less than or equal toKTheta doesn’t have to be equal to thetaK
  • foranswerKeyFor each element, you need to find a match laterkThe maximum number of consecutive operations
  • If you do that, you can run, but eventually you run out of time, and the T drops

Classic sliding Windows

  • Look at the solution to learn
  • The most classical solution to sliding Windows is that they can be sliding as a window, so some of them can be used again.
  • Double pointer: left pointerpreAnd right pointerlast
    • Enumerates the right endpoint from left to right, the number of other characters in the maintenance interval isnum
    • num <= k= >last++``forLoop through the conditions, always looking for greater than, because the same characters are also counted in length
    • num > k= >pre++usewhileCycle through the solution until the first unsatisfactory situation is found, breaking the balance already held.
  • Interval length:last - pre + 1

ACcode

var maxConsecutiveAnswers = function(answerKey, k) {
  // The whole idea should be clear, sliding window you need to reuse the middle part
  function getCnt(curChar) {
    // Two Pointers are required
    let pre = 0,last = 0,maxx = 0,num = 0, len = answerKey.length;
    // Interval length: r-l + 1
    for(pre = 0, last = 0; last < len; last++) {
      if(answerKey[last] === curChar) num++;
      while(num > k){
        // Need to handle interval length and pre
        if(answerKey[pre++] === curChar) num--;
      }
      maxx = Math.max(maxx, (last - pre + 1))}return maxx;
  }
  return Math.max(getCnt('T'), getCnt('F'))};Copy the code

conclusion

  • Classic sliding Windows, invariants and interval lookups are particularly important