Title source

• leetcode

title

title

Double pointer

In order to achieve in-situ compression , We can use double pointers to identify where we read and write in the string . Every time you read the pointer read Move to the rightmost side of a continuous substring , We're just writing pointers write Write the character and the length of the substring corresponding to the substring in turn .

• When reading pointer read At the end of the string , perhaps read When the character pointed to is different from the next character , We think it's time to read Located on the rightmost side of a continuous and identical substring . The pointer of the character string is the corresponding character string read The string pointed to . We use variables left Record the leftmost position of the substring , In this way, the length of the substring is read−left+1.
• Be careful , In order to achieve O(1) Spatial complexity , We need to realize the function of converting numbers into strings and writing them into the original strings . Here, we use the short division method to write the length of the substring in reverse order into the original string , Then reverse it .

class Solution {
    
public:
    int compress(vector<char>& chars) {
    
        int len = chars.size();
        int write = 0, left = 0;
        for (int read = 0; read < len; ++read) {
    
            if(read == len - 1 || chars[read] != chars[read + 1]){
    
                chars[write++] = chars[read];
                int num = read - left + 1;
                if(num > 1){
    
                    int anchor = write;
                    while (num > 0){
    
                        chars[write++] = num % 10 + '0';
                        num /= 10;
                    }
                    std::reverse(&chars[anchor], &chars[write]);
                }
                left = read + 1;
            }
        }
        return write;
    }
};

class Solution {
    
public:
    int compress(vector<char>& chars) {
    
        int len = chars.size(), curr = 0;
        for (int i = 0, j = 0; i < len; i = j) {
    
            while (j < len && chars[j] == chars[i]){
    
                ++j;
            }
            chars[curr++] = chars[i];
            if(j - i == 1){
    
                continue;
            }
            for(char c : std::to_string(j - i)){
    
                chars[curr++] = c;
            }
        }
        return curr;
    }
};