LeetCode 541 反转字符串 II 简单

1. 541 反转字符串 II 简单

1. 题目详情

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

1. 原题链接

LeetCode 541 反转字符串 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$下标开始剩余的字符数量$num$，对$num$进行判断；
$(3)$ $num$ 大于等于 $2\ast k$ ，则逆置从$start$开始的前$k$个字符，start更新加上$2\ast k$；
$(4)$ $num$ 小于$2\ast k$但大于等于$k$，则逆置从$start$开始的前$k$个字符，此时是最后一次逆置，$start$更新为整个字符串的大小；
$(5)$ $num$小于$k$，则逆置从$start$开始的剩余字符，此时是最后一次逆置，$start$更新为整个字符串的大小；

2. 时间复杂度

$O(N/k)$
每次处理$2\ast k$个字符，长度为n的字符串处理$n/(2\ast k)+1$次；

3. 代码实现

class Solution {
public:
    string reverseStr(string s, int k) {
        // [0, 2k-1]
        // [2k, 4k-1]
        // [4k, 6k-1]
        // ...
        // start
        int 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;
    }
};