541.反转字符串II

发表于： 分类于：
字数： 686 阅读：≈ 2分钟

🤸 541.反转字符串II

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

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。

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

思路

基本思想

因为每2*k个元素就要反转前k个元素，也就是字符串被分成了若干段，每一段都是2*k个字符，最后一段除外

此时对于每一段元素，逆转前k个元素即可，最后一段如果不足k个元素，就将剩下所有的元素都逆转一遍

那么核心就是找到每一段的开头位置，为了实现段的跳跃，for循环的步数可以设置为2*k，此时每走一步就是下一段的开始位置，从这个位置开始逆转即可

逆转时需要判断当前是否有k个元素，因为最后一段可能没有k个元素

执行流程

  1. 外层for循环一次走2*k步，找到每一段逆转的开头位置
  2. 判断当前端是否还有k个元素
    1. 有k个元素直接逆转k个元素
    2. 没有k个元素就逆转剩下的元素
  3. 返回逆转之后的结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    //每次找到需要翻转的起点，也就是一步走2k长
    //然后翻转k个字符
    string reverseStr(string s, int k) {
        for(int i=0;i<s.size();i+=2*k){
            //从头开始逆转k个字符
            //逆转需要分两种情况，第一种是够k个元素，第二种是不够k个元素
            //够k个元素直接逆转
            if(i+k<s.size()){
                swap(s,i,i+k-1);
            }
            //不够k个元素
            else{
                swap(s,i,s.size()-1);
            }
        }
        return s;
    }
    //根据给定的范围逆转元素
    //为了将改变传回形参，需要使用引用传递的方式
    void swap(string &s,int begin,int end){
        for(int i=begin,j=end;i<j;++i,--j){
            char temp=s[i];
            s[i]=s[j];
            s[j]=temp;
        }
    }
};

总结

核心有两点：

  1. for循环一次走2*k步，找到每次逆转的开头位置
  2. 每次逆转都需要判断是否还有k个元素，为了处理最后一个分段不足k个元素的情况