[LeetCode] 541. Reverse String II

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.

Example:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Restrictions:

The string consists of lower English letters only.
Length of the given string and k will in the range [1, 10000]

反转字符串二。题意跟版本一很接近，多一个限制条件K。需要反转每2K个字符，如果剩下的字符长度不足，就整个反转他们。

这个题出的不是很好。题目不难但是题意讲的非常绕，差评很多。既然是反转每2K个字母，则正常逻辑会认为反转部分的轴是在第K个字母附近，但是根据例子，因为K = 2所以涉及到的字母是前四个ABCD，但是实际被反转的字母只有前K个，AB。所以这个题可以理解为每2K个字母，只反转前K个字母。

时间O(n^2)

空间O(n) - 因为convert成了数组

JavaScript实现

 1 /**
 2  * @param {string} s
 3  * @param {number} k
 4  * @return {string}
 5  */
 6 var reverseStr = function (s, k) {
 7     let t = s.split('');
 8     for (let i = 0; i < s.length; i += 2 * k) {
 9         let start = i;
10         let end = i + k - 1;
11         while (start < end) {
12             const temp = t[start];
13             t[start] = t[end];
14             t[end] = temp;
15             start++;
16             end--;
17         }
18     }
19     return t.join('');
20 };

Java实现

 1 class Solution {
 2     public String reverseStr(String s, int k) {
 3         char[] input = s.toCharArray();
 4         for (int i = 0; i < input.length; i += 2*k) {
 5             int start = i;
 6             int end = Math.min(start + k - 1, input.length - 1);
 7             while (start < end) {
 8                 char temp = input[start];
 9                 input[start] = input[end];
10                 input[end] = temp;
11                 start++;
12                 end--;
13             }
14         }
15         return String.valueOf(input);
16     }
17 }