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

8.20 – 541. Reverse string II

The question

Given a string s and an integer k, invert the first K characters for every 2k characters from the beginning of the string.

If there are less than k characters left, all the remaining characters are reversed. If the remaining characters are less than 2K but greater than or equal to K, the first K characters are reversed and the remaining characters are left as is.

Example 1:

Input: s = "abcdefg", k = 2 Output: "bacdfeg"Copy the code

Example 2:

Input: s = "abcd", k = 2Copy the code

Analysis of the

  • According to the meaning of the question, it can be divided into two steps, divided into complete interception part and incomplete interception part;

  • The first part is math.ceil (sLen/spliceLen) -1. Because it is divisible, it reverses k characters for every 2k characters.

    • SLen: length of s;
    • SpliceLen: Cut length = 2 x K

  • The second part is the last intercepted string, and the remaining last string processing also needs to be divided into two types:

    • Anything greater than or equal to k does exactly the same thing as the whole thing, merges;
    • This is less than k and you just reverse it

  • Return the concatenated string as the answer.

  • If you look at the code comments, there are comments for each step

/ * * *@param {string} s- String *@param {number} k - 
 * @return {string}* /
var reverseStr = function (s, k) {
      let spliceLen = 2 * k;    // Need to cut the length equally
      let str = "";             / / the return value
      let sLen = s.length;
      let spliceNum = Math.ceil(sLen / spliceLen);  // The maximum number of loops required, s is 5, k is 2, only need to loop 2 times
      for (let i = 0; i < spliceNum; i++) {
            let waitStr = s.substr(i * spliceLen, spliceLen); // Each loop waits for a segment to be processed
            if (i < spliceNum - 1 || waitStr.length >= k) {
                // This is a complete cut or a cut with a length greater than or equal to k
                // The first cut is complete; // The first cut is complete; The second time is of length 1, and we do method 2, so let's say it's 7/4, and then we do method 1 again
                let left = waitStr.substr(0, k);
                let right = waitStr.substr(k);
                str += left.split("").reverse().join("");
                str += right;
            } else {
                // If the value is less than k, invert the value
                str += waitStr.split("").reverse().join(""); }}return str;
};
Copy the code

Complexity analysis

  • Time complexity: O (n), where n isMath.ceil(sLen / spliceLen)The length of the
  • Space complexity: do not know, know of convenient inform me next yao?

Running effect

✍, it works really well