LeetCode 541. Reverse String II(反转字符串 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
个字符就翻转k
个字符,框架就是:
for (int i = 0; i < length; i += 2 * k) {
if (i + k >= length) {
reverse(str, i, length - 1);
} else {
reverse(str, i, i + k - 1);
}
}
而reverse(str, start, end)
就是简单的反转字符串了。
Python
class Solution(object):
def reverseStr(self, s, k):
"""
:type s: str
:type k: int
:rtype: str
"""
length = len(s)
for i in range(0, length, 2 * k):
if i + k >= length:
s = s[:i] + s[i:][::-1]
else:
s = s[:i] + s[i:i + k][::-1] + s[i + k:]
return s
Java
public class Solution {
public String reverseStr(String s, int k) {
class Utils {
void reverse(char[] str, int start, int end) {
while (start < end) {
char temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}
}
Utils utils = new Utils();
int length = s.length();
char[] str = s.toCharArray();
for (int i = 0; i < length; i += 2 * k) {
if (i + k >= length) {
utils.reverse(str, i, length - 1);
} else {
utils.reverse(str, i, i + k - 1);
}
}
return new String(str);
}
}
C++
class Solution {
public:
string reverseStr(string s, int k) {
class Utils {
public:
void reverse(string &str, int start, int end) {
while (start < end) {
char temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}
};
Utils utils;
int length = s.length();
for (int i = 0; i < length; i += 2 * k) {
if (i + k >= length) {
utils.reverse(s, i, length - 1);
} else {
utils.reverse(s, i, i + k - 1);
}
}
return s;
}
};