字符串总结&双指针法

// 时间：O(n)
// 空间：O(1)
class Solution {
public:
    void reverse(vector<char>& s){
        for( int i = 0, j = s.size()-1; i < j; i++,j--){
            swap( s[i], s[j]);
        }
    }
    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--;
        // }
        reverse( s );

        
    }
};

// 时间：O(n)
// 空间：O(1)
class Solution {
public:
    string replaceSpace(string s) {

        // 统计空格出现的次数
        int OldSize = s.size() - 1;
        int count = 0;
        for ( int i = 0; i < s.size(); i++){
            if ( s[i] == ' '){
                count++;
            }
        }
        s.resize(s.size()+2*count);
        int NewSize = s.size() - 1;
        for ( int i = OldSize, j = NewSize; 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;
    }
};

// 时间：O(n)
// 空间：O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;
        for ( int fast = 0; fast < nums.size();fast++){
            if ( nums[fast] != val ){
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
};

class Solution {
public:
    void earseSpace( string& s){ //注意这块函数的写法 & !!!!
        int slow = 0;
        for ( int i = 0; i < s.size(); i++){
            if ( s[i] != ' ' ){
                if ( slow != 0 ) s[slow++] = ' ';
                while ( i < s.size() && s[i] != ' '){
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow);
    }
    // 注意这块&的用法
    void reverse( string& s ,int start,int end){
        for (int i = start , j = end; i < j; i++,j--){
            swap( s[i],s[j]);
        }
    }

    string reverseWords(string s) {

        earseSpace( s );
        reverse( s, 0, s.size()-1);
        
        int start = 0;
        for ( int i = start ; i <= s.size(); i++ ){ //这块第一次写的时候没加等号，注意这里的细节
            if ( i == s.size() || s[i] == ' '){ //这里细节注意，i==s.size()
                reverse ( s,start , i-1 );
                start = i+1;
            }
        }
        return s;

    }
};