541. 反转字符串 II
给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例:
输入: s = "abcdefg", k = 2
输出: "bacdfeg"
提示：
- 该字符串只包含小写英文字母。
- 给定字符串的长度和 k 在 [1, 10000] 范围内。
方法1：双指针法
算法思路：
- 每 2k 为一组，前 k 个元素反转，后 k 个保持不变；
- 前 k 个元素的下标为：(i, i+k-1)，此处需要判断是否超出数组范围；
- 当前反转之后 i = i + 2k，进行下一组的反转；
参考代码1:
class Solution {
public String reverseStr(String s, int k) {
char[] chars = s.toCharArray();
int n = chars.length;
// 每2k个元素为一组进行反转
for (int i = 0; i < n; i += 2 * k) {
int left = i;
//判断下标是否越界
int right = i + k - 1 < n ? i + k - 1 : n -1;
// 双指针交换
while (left < right) {
char temp = chars[left];
chars[left++] = chars[right];
chars[right--] = temp;
}
}
return String.valueOf(chars);
}
}
复杂度分析:
- 时间复杂度：
。其中 N 是 s 的大小。我们建立一个辅助数组，用来翻转 s 的一半字符。
- 空间复杂度：
。
方法2: 自带的reverse方法
参考代码2:
class Solution {
public String reverseStr(String s, int k) {
int start = 0, end = s.length() - 1;
StringBuilder sb = new StringBuilder();
while (start <= end) {
// 剩余字符的个数
int size = end - start + 1;
if (size < k) {
sb.append(new StringBuilder(s.substring(start)).reverse());
} else {
// 前k个元素反转
sb.append(new StringBuilder(s.substring(start, start + k)).reverse());
// 后k个元素保持原样
sb.append(new StringBuilder(s.substring(start + k, start+Math.min(size, 2 * k))));
}
start += 2 * k;
}
return sb.toString();
}
}
以上谢谢大家，求赞求赞求赞！
