【LeetCode】541. 反转字符串 II
1 题目描述
541. 反转字符串 II给定一个字符串 s
和一个整数 k
,从字符串开头算起,每计数至 2k
个字符,就反转这 2k
字符中的前 k
个字符。如果剩余字符少于 k
个,则将剩余字符全部反转。如果剩余字符小于 2k
但大于或等于 k
个,则反转前 k
个字符,其余字符保持原样。
2 解题思路
- 转换为字符数组:首先将字符串转换为字符数组,方便进行字符的交换。
- 循环遍历并反转:使用一个指针
i
从字符串的开头开始,每次增加2k
个位置,确定需要反转的子串范围,并执行反转操作。 - 反转操作:对于每个子串,定义两个指针
left
和right
分别指向子串的开始和结束位置,然后交换这两个位置上的字符,直到left
不再小于right
。
3 Java 代码实现
public class Solution {
public String reverseStr(String s, int k) {
// 将字符串转换为字符数组
char[] ch = s.toCharArray();
// 每隔 2k 个字符进行反转操作
for (int i = 0; i < ch.length; i += 2 * k) {
// 计算反转区间的左右边界
int left = i;
int right = Math.min(ch.length - 1, i + k - 1);
// 执行反转操作
while (left < right) {
char temp = ch[left];
ch[left] = ch[right];
ch[right] = temp;
left++;
right--;
}
}
// 将字符数组转换回字符串并返回
return new String(ch);
}
}
- 时间复杂度: O(n),其中 n 是字符串的长度。、
- 空间复杂度: O(n),需要额外的字符数组来存储字符。
4 注意事项
- 字符数组转换:首先将字符串转换为字符数组
ch
,便于进行字符的交换操作。 - 循环步长:每次循环步长为
2k
,这是因为我们要处理每2k
个字符中的前k
个字符。 - 反转区间:反转区间的左端点为
left
,右端点为right
,其中right
需要考虑字符串的实际长度,不能超过。 - 反转操作:使用临时变量
temp
进行字符的交换操作。 - 返回结果:最后将字符数组转换回字符串返回。