541. 反轉(zhuǎn)字符串 II
給定一個(gè)字符串 s 和一個(gè)整數(shù) k，你需要對(duì)從字符串開(kāi)頭算起的每隔 2k 個(gè)字符的前 k 個(gè)字符進(jìn)行反轉(zhuǎn)台夺。
如果剩余字符少于 k 個(gè)虐秋，則將剩余字符全部反轉(zhuǎn)邑时。
如果剩余字符小于 2k 但大于或等于 k 個(gè)咐蝇，則反轉(zhuǎn)前 k 個(gè)字符，其余字符保持原樣鹏倘。
示例:
輸入: s = "abcdefg", k = 2
輸出: "bacdfeg"
提示：
- 該字符串只包含小寫(xiě)英文字母薯嗤。
- 給定字符串的長(zhǎng)度和 k 在 [1, 10000] 范圍內(nèi)。
方法1：雙指針?lè)?/h3>
算法思路：
- 每 2k 為一組纤泵，前 k 個(gè)元素反轉(zhuǎn)骆姐，后 k 個(gè)保持不變；
- 前 k 個(gè)元素的下標(biāo)為：(i, i+k-1)捏题，此處需要判斷是否超出數(shù)組范圍玻褪；
- 當(dāng)前反轉(zhuǎn)之后 i = i + 2k，進(jìn)行下一組的反轉(zhuǎn)公荧；
參考代碼1:
class Solution {
public String reverseStr(String s, int k) {
char[] chars = s.toCharArray();
int n = chars.length;
// 每2k個(gè)元素為一組進(jìn)行反轉(zhuǎn)
for (int i = 0; i < n; i += 2 * k) {
int left = i;
//判斷下標(biāo)是否越界
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);
}
}
復(fù)雜度分析:
- 時(shí)間復(fù)雜度：
)
带射。其中 N 是 s 的大小。我們建立一個(gè)輔助數(shù)組循狰，用來(lái)翻轉(zhuǎn) s 的一半字符窟社。
- 空間復(fù)雜度：
)
券勺。
方法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) {
// 剩余字符的個(gè)數(shù)
int size = end - start + 1;
if (size < k) {
sb.append(new StringBuilder(s.substring(start)).reverse());
} else {
// 前k個(gè)元素反轉(zhuǎn)
sb.append(new StringBuilder(s.substring(start, start + k)).reverse());
// 后k個(gè)元素保持原樣
sb.append(new StringBuilder(s.substring(start + k, start+Math.min(size, 2 * k))));
}
start += 2 * k;
}
return sb.toString();
}
}
class Solution {
public String reverseStr(String s, int k) {
char[] chars = s.toCharArray();
int n = chars.length;
// 每2k個(gè)元素為一組進(jìn)行反轉(zhuǎn)
for (int i = 0; i < n; i += 2 * k) {
int left = i;
//判斷下標(biāo)是否越界
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);
}
}
class Solution {
public String reverseStr(String s, int k) {
int start = 0, end = s.length() - 1;
StringBuilder sb = new StringBuilder();
while (start <= end) {
// 剩余字符的個(gè)數(shù)
int size = end - start + 1;
if (size < k) {
sb.append(new StringBuilder(s.substring(start)).reverse());
} else {
// 前k個(gè)元素反轉(zhuǎn)
sb.append(new StringBuilder(s.substring(start, start + k)).reverse());
// 后k個(gè)元素保持原樣
sb.append(new StringBuilder(s.substring(start + k, start+Math.min(size, 2 * k))));
}
start += 2 * k;
}
return sb.toString();
}
}
以上謝謝大家，求贊求贊求贊灿里！
?? 大佬們隨手關(guān)注下我的wx公眾號(hào)【一角錢小助手】和 掘金專欄【一角錢】 更多題解干貨等你來(lái)～～
