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

[Brush question Diary] 2024. The most troubling degree of examination

67. Binary summation, simple

I. Title Description:

Today, I will brush a medium question. At first glance, it is an exam question, but after a careful look, I find it is a question to modify the answer.

In the given string, modify k characters to ensure that the number of consecutive identical characters is maximized

Ii. Analysis of Ideas:

1. What ideas does this question examine? What’s your thinking?

Take a look at the key information given by the question:

• They give you a string, just T and F, and they give you k characters that you can change
• The modified K characters can only be changed to T or F
• Doesn’t it look like a character change problem? So how do we need to modify to ensure that the number of consecutive identical characters is maximized

We draw a picture, box the data we want on the draft according to the usual logic and get the answer we want

Take the example given in the question: answerKey = “TTFTTFTT”, k = 1

Looking at the figure above, we can see that we use the sliding box to select the interval that meets our requirements

You can figure out one by one which is correct and which is not correct, and you can also calculate the number of consecutive characters that are the same, and then calculate the maximum

Note here that the condition given in the question can change k characters, this condition needs to be added to the logic, so the rest is to translate the code process

Three, coding

Based on the above logic and analysis, we can translate into the following code, you can pay attention to our processing of K

The encoding is as follows:

func maxConsecutiveAnswers(answerKey string, k int) int {
    return max(helper(answerKey, k, 'T'),helper(answerKey, k, 'F'))}// The help function calculates the maximum number of consecutive characters when filling k specified characters as required
func helper(answerKey string, k int, ch byte) (ans int) {
    left, sum := 0.0
    for right := range answerKey {
        ifanswerKey[right] ! = ch { sum++ }// If there are more than k undesired characters in the current range, start moving
        for sum > k {
            ifanswerKey[left] ! = ch { sum-- } left++ }// Calculate the number of consecutive specified characters in the specified interval, and compare the result with the previous interval, take the maximum value
        ans = max(ans, right-left+1)}return
}

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

Copy the code

After seeing the above coding, I know this problem is still very simple, but the idea is also quite important, no matter what to do, the foundation should be firm, the idea is correct, the design is correct, the coding is basically not bad what, who will achieve the same

Iv. Summary:

The time complexity of this problem is O(n), and here we’ve also cycled through the answerKey length twice, so it’s O(n), and the space complexity is O(1), introducing only the attempt level memory consumption

Original address: 2024

Today is here, learning, if there is a deviation, please correct

Welcome to like, follow and favorites

Friends, your support and encouragement, I insist on sharing, improve the quality of the power

All right, that’s it for this time

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am Nezha, welcome to like, see you next time ~