443. String Compression

這題就是冗了點, 通常倒讚數多的題目都是如此

規則應該沒有難懂到看不懂, 只須注意幾個點, 當count為1時不用給出壓縮數

另外follow是希望不要用到其他空間

我先過一遍沒有follow up 的

class Solution {
public:
    int compress(vector<char>& chars) {
        int n = chars.size();
        if(n == 0) return 0;
        int count = 1;
        char cur= chars[0];
        int res = 1;
        vector<char> g;
        for(int i = 1; i < n;i++){
            if(chars[i] != cur){
                g.push_back(cur);
                cur = chars[i];
                res++;
                vector<int> cnt;
                if(count > 1){
                    while(count){
                        cnt.push_back(count % 10);
                        res++;
                        count /=10;
                    }
                    reverse(cnt.begin(), cnt.end());
                    for(auto s: cnt){
                        g.push_back(s + '0');
                    }
                }
                count = 1;
            }else{
                count++;
            }
        }
        vector<int> cnt;
        g.push_back(cur);
        if(count == 1){
            chars = g;
            return res;
        }
        while(count){
            cnt.push_back(count % 10);
            res++;
            count /=10;
        }
       
        reverse(cnt.begin(), cnt.end());
            for(auto s: cnt){
            g.push_back((s + '0'));
        }
        chars = g;
        return res;
    }
};

事實證明, 技不如人阿哈哈, follow上有一種非常高級的用法

一開始我想說應該辦不到吧 不是會蓋掉嗎

原來是我們可以這樣想, 會出現的case假設只有 "a", 那他只會有一個值

如果是"aabb", “aa”的部分也會換成”a2”, 所以永遠也不會蓋到下一個人

有結果的話, 可以直接蓋在字母後面

class Solution {
public:
    int compress(vector<char>& chars) {
        if(chars.size() <2) return chars.size();
        int i = 0;
        int j = 0;
        while(i < chars.size()){
            chars[j] = chars[i];
            int count = 0;
            while(i <chars.size() && chars[i] == chars[j]){
                count++;
                i++;
            }
            if(count == 1){
                j++;
            }else{
                string str = to_string(count);
                for(auto c: str){
                    j++;
                    chars[j] = c;
                }
                j++;
            }
        }
        return j;
    }
};