LeetCode 0541.反转字符串 II：模拟

news/2025/2/1 7:55:37/

【LetMeFly】541.反转字符串 II：模拟

力扣题目链接：https://leetcode.cn/problems/reverse-string-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⁴
s 仅由小写英文组成
1 <= k <= 10⁴

解题方法：模拟

使用l从0到len(s) - 1遍历要翻转字符串的左端点，那么要翻转字符串的右端点就是min(l + r, len(s)) - 1。每次l += 2*k。

对于字符串s[l, r]，如何翻转？若不能调用编程语言内置函数，可在l ＜ r时交换s[l]和s[r]并右移l和左移r各一次。

时间复杂度 $O (l e n (s))$
空间复杂度 $O (1)$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-01-31 11:58:52* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-31 12:02:00*/
class Solution {
private:inline void reverse_(string& s, int l, int r) {reverse(s.begin() + l, s.begin() + r);}
public:string reverseStr(string& s, int k) {for (int l = 0; l < s.size(); l += k * 2) {reverse_(s, l, min(l + k, (int)s.size()));}return s;}
};

Python

'''
Author: LetMeFly
Date: 2025-01-31 12:02:40
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-31 12:08:02
'''
class Solution:def reverseStr(self, s: str, k: int) -> str:s = list(s)for l in range(0, len(s), k * 2):s[l:l + k] = s[l:l + k][::-1]return ''.join(s)

Java

/** @Author: LetMeFly* @Date: 2025-01-31 12:11:33* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-31 12:16:13*/
class Solution {private void reverse(char[] s, int l, int r) {  // [l, r]while (l < r) {char temp = s[l];s[l++] = s[r];s[r--] = temp;}}public String reverseStr(String s1, int k) {char[] s = s1.toCharArray();for (int l = 0; l < s.length; l += k * 2) {reverse(s, l, Math.min(l + k, s.length) - 1);}// return s.toString();  // 不可！return new String(s);}
}

Go

/** @Author: LetMeFly* @Date: 2025-01-31 12:17:35* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-31 12:18:54*/
package mainimport "slices"func reverseStr(s1 string, k int) string {s := []byte(s1)for i := 0; i < len(s); i += k * 2 {slices.Reverse(s[i:min(i + k, len(s))])}return string(s)
}