1. 541 反轉(zhuǎn)字符串 II 簡單

1. 題目詳情

給定一個字符串 s 和一個整數(shù) k，從字符串開頭算起，每計數(shù)至 2k 個字符，就反轉(zhuǎn)這 2k 字符中的前 k 個字符。

如果剩余字符少于 k 個，則將剩余字符全部反轉(zhuǎn)。
如果剩余字符小于 2k 但大于或等于 k 個，則反轉(zhuǎn)前 k 個字符，其余字符保持原樣。

1. 原題鏈接

LeetCode 541 反轉(zhuǎn)字符串 II 簡單

2. 題目要求

示例 1：
輸入：s = “abcdefg”, k = 2
輸出：“bacdfeg”

示例 2：
輸入：s = “abcd”, k = 2
輸出：“bacd”

提示：
1 <= s.length <= 104
s 僅由小寫英文組成
1 <= k <= 104

3. 基礎框架

● Cpp代碼框架

class Solution {
public:string reverseStr(string s, int k) {
};

2. 解題思路

1. 思路分析

$(1)$ 一個變量$start$記錄需要逆置的部分的起始下標；
$(2)$ 計算從$start$下標開始剩余的字符數(shù)量$num$，對$num$進行判斷；
$(3)$ $num$ 大于等于 $2?k$ ，則逆置從$start$開始的前$k$個字符，start更新加上$2?k$；
$(4)$ $num$ 小于$2?k$但大于等于$k$，則逆置從$start$開始的前$k$個字符，此時是最后一次逆置，$start$更新為整個字符串的大小；
$(5)$ $num$小于$k$，則逆置從$start$開始的剩余字符，此時是最后一次逆置，$start$更新為整個字符串的大小；

2. 時間復雜度

$O(N/k)$
每次處理$2?k$個字符，長度為n的字符串處理$n/(2?k)+1$次；

3. 代碼實現(xiàn)

class Solution {
public:string reverseStr(string s, int k) {// [0, 2k-1]// [2k, 4k-1]// [4k, 6k-1]// ...// startint start = 0;while(start < s.size()){if(s.size() - start >= 2 * k){reverse(s.begin() + start, s.begin() + start + k);start += 2 * k;}else if(s.size() - start >= k){reverse(s.begin() + start, s.begin() + start + k);start = s.size();}else{reverse(s.begin() + start, s.end());start = s.size();}}return s;}
};

---