This is the 20th day of my participation in the August More Text Challenge

1963. Minimum number of swaps to make a string balanced

Thought analysis

So the balanced string that they define carefully is just another way of defining, one open parenthesis for one close parenthesis.

Return the minimum number of swaps required to turn the string s into a balanced string. We assume that there must be x cases where an open parenthesis does not match a close parenthesis, so the number of swaps is at most x and at least x/2 (because swapping the left and right parentheses once might make two pairs of mismatched parentheses match at the same time). So if you think about the odd and even effect, you can think of it as rounding up x over 2.

We can also do this by changing TMP — to TMP ++.

int minSwaps(string s) {
        int tmp = 0;
        int ret = 0;
        for(int i = 0; i < s.size(a); i++){if (s[i] == '['){
                tmp++;
            }else {
                
                if (tmp == 0){
                    tmp++;
                    ret++;
                }else{ tmp--; }}}return ret;
    }
Copy the code

541. Reverse string II

Thought analysis

As a simple problem, as opposed to an inversion implementation

while (l < r) {
    char c = cs[l];
    cs[l] = cs[r];
    cs[r] = c;
    l++; r--;
}
Copy the code

The only difficulty should be determining whether it is the end of the string or whether you can still truncate a 2k field.

Note in reverse rule:

  • If there are fewer characters leftk, all the remaining characters are reversed.
  • If the remaining characters are less than2kBut greater than or equal tok, then reverse beforekThe rest of the characters remain unchanged.

In fact, it is convenient that we only need to flip the k or n-start length of the string, without the extra judgment of the second time.