❓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 . l e n g t h < = 1 0 4 1 <= s.length <= 10^4 1<=s.length<=104
s
仅由小写英文组成- 1 < = k < = 1 0 4 1 <= k <= 10^4 1<=k<=104
💡思路:模拟
我们直接按题意进行模拟:
- 反转每个下标从
2k
的倍数开始的,长度为k
的子串。 - 若该子串长度不足
k
,则反转整个子串。
🍁代码:(Java、C++)
Java
class Solution {public String reverseStr(String s, int k) {char[] ch = s.toCharArray();int n = s.length();for(int i = 0; i < n; i += 2 * k){int left = i;int right = Math.min(n - 1, i + k - 1);while(left < right){char temp = ch[left];ch[left++] = ch[right];ch[right--] = temp;}}return new String(ch);}
}
C++
class Solution {
public:string reverseStr(string s, int k) {for(int i = 0; i < s.size(); i += 2 * k){if(i + k - 1 < s.size()){reverse(s.begin() + i, s.begin() + i + k);}else{reverse(s.begin() + i, s.end());}}return s;}
};
🚀 运行结果:
🕔 复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n),其中
n
为字符串s
的长度。 - 空间复杂度: O ( 1 ) O(1) O(1) 或 O ( n ) O(n) O(n),取决于使用的语言中字符串类型的性质。如果字符串是可修改的(
C++
),那么我们可以直接在原字符串上修改,空间复杂度为 O ( 1 ) O(1) O(1),(Java
)否则需要使用 O ( n ) O(n) O(n) 的空间将字符串临时转换为可以修改的数据结构(例如数组),空间复杂度为 O ( n ) O(n) O(n)。
题目来源:力扣。
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!