443 - String Compression

解法一 - Run-length encoding

我們可以在每一個 char 轉換時都去計算這個 char 出現幾次,然後再寫進原本的 array 中,實作如下:

class Solution {
public:
    int compress(vector<char>& chars) {
        int n = chars.size(), compressed = 0;

        for(int i = 0; i < n; ++i) {
            int count = 1, start = i;

            while( i < n - 1 && chars[i] == chars[i + 1] ) {
                ++count;
                ++i;
            }

            // Write char at compressed, write count from compressed + 1
            chars[compressed++] = chars[i];
            if(count == 1) { 
                continue; 
            }
            else {
                // https://stackoverflow.com/a/10847317
                string count_s = to_string(count);
                const char *count_char = count_s.c_str();
                int j = 0;
                while(count_char[j] != '\0') {
                    chars[ compressed++ ] = count_char[j++];
                }
            }
        }

        return compressed;
    }
};

results matching ""

    No results matching ""