算法力扣刷题记录二十一【344.反转字符串和541. 反转字符串II】

前言

字符串篇开张。
记录二十一【344.反转字符串和541. 反转字符串II】

一、344题目阅读和解答

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

1 <= s.length <= 105
s[i] 都是 ASCII 码表中的可打印字符

代码实现

class Solution {
public:
    void reverseString(vector<char>& s) {        
        for(int i = 0,j = s.size()-1; i < j ; i++,j--){//i 
            //swap(s[i],s[j]);
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
        }
    }
};

总结：不再多说，一个专栏，做到这步可以想到“双指针法”。

二、541. 反转字符串II 题目阅读和实现

题目阅读

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

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

示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2
输出："bacd"

提示：

1 <= s.length <= 104
s 仅由小写英文组成
1 <= k <= 104

思路

仍然是反转操作，双指针法可以很好解决（会反转操作）。那么每一轮i,j的位置怎么确定？确定好每一次反转的两端，题目就解决了。
（1）每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

2k为一组，遇到一个2k，就反转一次。总长size = s.size()，有多少个2k？就反转多少次。所以次数：num = size/(2*k)。
第一次反转：i = 0;j = k-1; //前k个字符
第二次反转：i = 2k;j = 2k + k -1; //前k个字符
第三次反转：i = 2k * 2 = 4k ; j = 4k + k -1; //前k个字符
发现规律：第n次反转：i = 2k * (n-1) ; j = i + k -1; //前k个字符
for循环可以知道当前是第几次。

（2）处理剩余字符：剩余多少个字符呢？size%(2*k)就是剩余的字符。

如果等于0，直接return s;
如果小于k，再来一次反转全部剩余字符。i = 2k * num; j = s.size() -1;
如果大于k，反转前k个：i = 2k * num; j = i + k -1;

代码实现（测试通过）

class Solution {
public:
    string reverseStr(string s, int k) {
        int size = s.size();
        int num = size/(2*k);
        int m = num;
        while(m){ //反转，写for循环也可以。
            int i = (num - m) * 2 * k;  //j--如果在while中作减法，这里还要用j。
            int j = i + k -1;
            for(;i < j;i++,j--){
                swap(s[i],s[j]);
            } 
            m--;
        }
        //处理剩余不足2k的字符
        if(size%(2*k) != 0){
            int i,j;
            if(size%(2*k) < k){//剩余字符少于 k 个，则将剩余字符全部反转。
                 i = 2*k*num;
                 j = size-1;
            }else{  //剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
                i = 2*k*num;
                j = i+k-1;  
            }
            for(;i < j;i++,j--){
                    swap(s[i],s[j]);
            }
        }else{
            return s;
        }
        return s;
        
    }
};