📃 题目描述

题目链接：443. 压缩字符串 (opens new window)

🔔 解题思路

常规思路，快慢指针，快指针用来找和慢指针相同的数

需要注意的是这题需要添加一个写指针，用来在 chars 数组上进行原地修改。

class Solution {
    public int compress(char[] chars) {
        // 左指针
        int left = 0;
        // 右指针，用于遍历和 left 相同的数
        int right = 1;

        // 写指针，用于在 chars 中写最终结果
        int write = 0;

        // 这里 right 取到 chars.length 是为了处理最后一串连续数
        while (right <= chars.length) {
            // 遇到相等数，右指针 ++
            if (right != chars.length && chars[left] == chars[right]) {
                right ++;
            }
            else {
                chars[write] = chars[left];
                write ++;

                int len = right - left;
                int anchor = write;
                if (len > 1) {
                    //  如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符
                    while (len > 0) {
                        chars[write] = (char)(len % 10 + '0');
                        len /= 10;
                        write ++;
                    }
                    // 反转 chars[anchro, write - 1];
                    reverse(chars, anchor, write - 1);
                }

                // 进入下一个数字的处理
                left = right;
                right = left + 1;
            }
        }

        // 返回该数组的新长度
        return write;
    }

    public void reverse(char[] chars, int left, int right) {
        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }

}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：