JLUVicent

344反转字符串&541反转字符串II&剑指Offer05替换空格&151反转字符串中的单词&剑指Offer58-II左旋转字符串

 
  • 2023年 02月22日
  • 0 阅读

day8

344.反转字符串

题目链接：344. 反转字符串

解题思路：双指针思路，原地修改数组了我还给return s，傻了，去掉之后直接AC

注意C++中交换的几种方法

image-20230222191826503

class Solution {
public:
    void reverseString(vector<char>& s) {
        // 双指针法
        int left = 0;
        int right = s.size()-1;
        while( left < right ){
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++;
            right--;
        }
    }
};

541.反转字符串II

题目链接：541. 反转字符串 II

解题思路：可以自定义reverse函数也可以使用reverse函数，注意

class Solution {
public:
    // 自定义reverse 注意区间，左闭右闭
    void reverse( string& s , int start, int end){
        for ( int i = start, j = end ; i< j; i++,j--){
            swap (s[i],s[j]);
        }
    }

    string reverseStr(string s, int k) {
        // 定义函数
        for( int i = 0; i < s.size(); i += 2*k){
            if ( i + k <= s.size()){
                // 官方库函数的区间是左闭右开
                // reverse( s.begin() + i , s.begin()+i+k );
                reverse( s, i, i+k-1);
            }
            else{
                // reverse (s.begin() + i , s.end());
                reverse( s, i, s.size()-1);
            }
        }
        return s;
    }
};

剑指Offer 05.替换空格

题目链接：剑指 Offer 05. 替换空格

解题思路：使用双指针，先将数组扩充为填充后的大小，然后使用两个指针，一个指向扩充后数组，一个指向扩充前数组，判断扩充前数组指针对应的值是否为” “，如果不是，直接填充到末尾，如果是，用”%20”替换

class Solution {
public:
    string replaceSpace(string s) {
        // 时间 O(n)
        // 空间 O(1)
        int count = 0;
        int OldSize = s.size();
        // 计算原字符串中空格的数量
        for ( int i = 0; i < s.size() ; i++){
            if ( s[i] == ' ' ){
                count++;
            }
        }
        // 扩充新数组
        s.resize( s.size() + count*2 );

        int NewSize = s.size();

        for ( int i = OldSize -1 , j = NewSize - 1; i < j ;  i--,j--){

            if ( s[i] != ' '){
                s[j] = s[i];
            }
            else{
                s[j] = '0';
                s[j-1] = '2';
                s[j-2] = '%';
                j -=2;
            }
        }
        return s;
    }
};

151.反转字符串中的单词

题目链接：151. 反转字符串中的单词

解题思路：关键在于如何去除字符串中的空格，使用快慢指针，和删除数组中的元素一个原理

class Solution {
public:
    void reverse(string& s, int start, int end){ //翻转，区间写法：左闭右闭 []
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针。
        int slow = 0;   
        for (int i = 0; i < s.size(); ++i) { //
            if (s[i] != ' ') { //遇到非空格就处理，即删除所有空格。
                if (slow != 0) s[slow++] = ' '; //手动控制空格，给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
                while (i < s.size() && s[i] != ' ') { //补上该单词，遇到空格说明单词结束。
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow); //slow的大小即为去除多余空格后的大小。
    }

    string reverseWords(string s) {
        removeExtraSpaces(s); //去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。
        reverse(s, 0, s.size() - 1);
        int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是0。
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { //到达空格或者串尾，说明一个单词结束。进行翻转。
                reverse(s, start, i - 1); //翻转，注意是左闭右闭 []的翻转。
                start = i + 1; //更新下一个单词的开始下标start
            }
        }
        return s;
    }
};

剑指Offer58-II.左旋转字符串

题目链接：剑指 Offer 58 - II. 左旋转字符串

解题思路：感觉有点技巧题的意思，就是两次反转然后再反转就解决了哈哈哈

image-20230222221436711

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse( s.begin() , s.begin() + n );
        reverse( s.begin() + n , s.end());
        reverse( s.begin() , s.end());
        return s;
    }
};
搜索