443. String Compression

考实现能力 O(n) time O(1) space

class Solution {
public:
    int compress(vector<char>& chars) {
        int n = chars.size(), res = 0;
        for (int i = 0, j = 1; i < n; i = j) { // 一次循环过后chars[j]已经跟chars[i]不一样，把i设成新的j
            while (j < n && chars[j] == chars[i]) { // j从i开始往后找第一个跟chars[i]不一样的chars[j]
                ++j;
            }
            chars[res++] = chars[i]; // 写chars[i]
            if (i + 1 == j) continue; // 如果chars[i]只有一个字母，则不需要写个数
            for (char c : to_string(j - i)) { // 写字母个数
                chars[res++] = c;
            }
        }
        return res;
    }
};

用write read anchor来控制

class Solution {
public:
    int compress(vector<char>& chars) {
        int n = chars.size();
        int w = 0, a = 0;
        for (int r = 0; r < n; ++r) { // 每次读一个字母
            if (r + 1 == n || chars[r + 1] != chars[r]) { // 如果当前字母跟下一个字母不一样或者到头了
                chars[w++] = chars[a]; // 向指定位置写入锚点指向的字符
                if (r > a) { // 如果需要写入字符个数的话（"a"这种就不需要）
                    for (char c : to_string(r + 1 - a)) { // 统计字符个数并依次写入数字
                        chars[w++] = c;
                    }
                }
                a = r + 1; // 调整锚点到下一个不同的字符
            }
        }
        return w;
    }
};

O(n) time O(1) space

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