541. 反转字符串 II

💒读题

1. 题意是 将K内的字符，全部翻转，但是下一次反转的起始位置要在2*K的位置上开始。
2. 如果下一个起始位置开始，后面的字符<K个 ,则全部翻转。
3. 如果最开始 字符就小于K，那就直接全部翻转。

🧸解题

我看了
class Solution {
public:
    string reverseStr(string s, int k) {
		
        int len = s.size();//记录最后一个字符的下一个位置
        for(int i = 0;i<len;i+=2*k)
        {
            if(i+k<len)
            {
                reverse(s.begin()+i,s.begin()+i+k);
            }
            else{
                reverse(s.begin()+i,s.begin()+len);
            }
        }
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

🧸解读代码

i是每次翻转字符的起始位置。
i+k是每次翻转的结束位置。
len是最后一个字符的下一个位置
for(int i = 0;i<len;i+=2*k)

for循环开始，每次i+=2*k,直接找到了下一次反转字符的起始位置。

if(i+k<len)

i每次+=2*k，则只要i的位置+k，没超过len，就直接反转i到k个字符。

else

i的位置+k，超过了len，说明可以翻转的字符比K小，则直接全部翻转。

尾部的把控

例如k = 2
i + k 要翻转2个字符。
那么结束位置的下标就是2,也就是第三个字符的位置，而reverse正好需要左闭右开，详情看下面解释 。

reverse

reverse(left，right)函数的参数是左闭右开。
官方解释是：翻转的字符：是指在left到right区间的字符，包含left指向的字符，不包含right指向的字符。

🧸我第一次写的代码

    第一次写的算法:写了好长啊 ，思路是遇到了一次问题，解决一次。
        if(s.size()>=k)//避免只有一个字符的翻转，直接return
        {
            int begin = 0, end = s.size();//begin是查找2k的位置，end是结尾
            int count = 0, prev = 0;//count是记录翻转的个数，prev是是k开始反转的位置
            while (begin < end) //begin一直往后走，直到走完
            {
                count = 0;//count 每次开始会被置0，是要被翻转字符的个数
                prev = begin;//重置到下一次k开始反转的位置
                while (begin < end &&count < 2*k)//在计算 够不够2k
                {
                    if (count != 2 * k)
                    {
                        ++begin;
                        ++count;
                    }
                }
                if ((count == 2 * k) || (count < 2 * k && count >= k))
                {
                    reverse(s.begin() + prev, s.begin() + prev+k);//翻转prev到k之间的字符
                }
                else if (count < k && count!=1)
                {
                	//翻转prev到最后的全部字符，因为count只记录到end的位置
                    reverse(s.begin() + prev, s.begin() +prev+count);
                }
            }
        }
        else
        {
            if(s.size() != 1)//这里是 如果k直接大于了 字符个数，直接全部翻转
            {
                reverse(s.begin(),s.end());
            }
        }
        return s;
    }
这个代码写的很冗余，好像有很多没用的变量，我也没再改了。这个代码是可以通过的。
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
30
31
32
33
34
35
36
37
38

🌈加油，祝你早日拿到心仪的offer！