[LeetCode] 每日一题 541. 反转字符串 II
题目链接
题目描述
给定一个字符串 s
和一个整数 k
,从字符串开头算起,每计数至 2k
个字符,就反转这 2k
字符中的前 k
个字符。
如果剩余字符少于
k
个,则将剩余字符全部反转。如果剩余字符小于
2k
但大于或等于k
个,则反转前k
个字符,其余字符保持原样。
示例输入
示例 1
输入:s = "abcdefg", k = 2
输出:"bacdfeg"
示例 2
输入:s = "abcd", k = 2
输出:"bacd"
提示
1 <= s.length <= 10^4
s
仅由小写英文组成1 <= k <= 10^4
解题思路
本题属于基础的字符串操作题目,要求按照特定规则对字符串进行局部反转。遍历字符串时,每次处理 2k
个字符,并反转其中的前 k
个字符。同时,需要根据剩余字符数量调整反转方式:
如果剩余字符少于
k
,则全部反转如果剩余字符在
k
到2k
之间,则仅反转前k
个字符,其余部分保持不变
为了实现这一规则,我们可以:
使用
for
循环,每次步长为2k
,从0
开始遍历整个字符串,这样能直观地定位每个需要处理的区间,避免额外的索引维护将反转逻辑封装到一个独立方法中,提高代码的可读性和复用性,同时符合软件工程中的单一职责原则(SRP),使代码结构更加清晰
代码实现
class Solution {
public String reverseStr(String s, int k) {
char[] ansArray = s.toCharArray();
for (int i = 0; i < s.length(); i += 2 * k) {
reverse(ansArray, i, Math.min(i + k - 1, s.length() - 1));
}
return new String(ansArray);
}
private void reverse(char[] array, int start, int end) {
while (start < end) {
char temp = array[start];
array[start] = array[end];
array[end] = temp;
start++;
end--;
}
}
}
复杂度分析
时间复杂度:O(n),其中
n
是字符串s
的长度。每2k
个字符处理一次,每次最多反转k
个字符,因此整个字符串的反转操作仍是线性复杂度空间复杂度:O(n),主要是由于字符串
s
转换为字符数组char[]
进行操作,但不包含额外的数据结构,因此为 O(n)。如果允许直接修改字符串(如 Python 或 C++),可以优化为 O(1) 额外空间
总结
本题的核心是按规则分段处理字符串,并进行局部反转。通过 for
循环遍历字符串,每次步长 2k
,可以更直观地维护索引,避免 while
方式的复杂性。封装反转逻辑至独立方法,有助于提高代码的复用性和可读性。这种分段遍历 + 局部操作的思想在字符串处理类题目中非常常见,是一个值得掌握的技巧
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。