当前位置：首页 > article >正文

每日一题(LeetCode)----字符串--反转字符串 II

article 2024/11/16 19:57:34

每日一题(LeetCode)----字符串–反转字符串 II

1.题目（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

2.解题思路

思路一：找到要反转的子串使用双指针实现反转

1.我们先看需要反转几次

反转的次数分为两部分一部分是我们用字符串的总长度除以2*k得到的数另一部分是字符串的总长度取余2 * k后得到的数与k和2 * k进行对比，以判断剩下的字符串是否需要进行反转

2.创建两个指针来对要进行反转的地方进行反转

思路：找到要反转的子串使用库函数实现反转

反转每个下标从 2k的倍数开始的，长度为 k的子串。若该子串长度不足 k，则反转整个子串。

作者：力扣官方题解

链接：https://leetcode.cn/problems/reverse-string-ii/

3.写出代码

思路一的代码

class Solution {
public:
    string reverseStr(string s, int k) {
        int length=s.size();

        int loop=length/(2*k);
        int residue=length%(2*k);
        char* left=&s[0];
        char* right=left+k-1;
        char* leTemp;
        char* riTemp;
        while(loop--){
            leTemp=left;
            riTemp=right;
            while(riTemp>leTemp){
                if((*leTemp)!=(*riTemp)){
                (*leTemp)=(*leTemp)^(*riTemp);
                (*riTemp)=(*leTemp)^(*riTemp);
                (*leTemp)=(*leTemp)^(*riTemp);
                }
                leTemp++;
                riTemp--;
            }
            left+=2*k;
            right=left+k-1;
        }

        if(residue<k){
            right=left+residue-1;

            leTemp=left;
            riTemp=right;
            while(riTemp>leTemp){
                if((*leTemp)!=(*riTemp)){
                (*leTemp)=(*leTemp)^(*riTemp);
                (*riTemp)=(*leTemp)^(*riTemp);
                (*leTemp)=(*leTemp)^(*riTemp);
                }
                leTemp++;
                riTemp--;
            }
        }

        if(residue>=k&&residue<2*k){
            leTemp=left;
            riTemp=right;
            while(riTemp>leTemp){
                if((*leTemp)!=(*riTemp)){
                (*leTemp)=(*leTemp)^(*riTemp);
                (*riTemp)=(*leTemp)^(*riTemp);
                (*leTemp)=(*leTemp)^(*riTemp);
                }
                leTemp++;
                riTemp--;
            }
        }
        return s;
    }
    
};

思路二的代码

class Solution {
public:
    string reverseStr(string s, int k) {
        int n = s.length();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(s.begin() + i, s.begin() + min(i + k, n));
        }
        return s;
    }
};