leetcode （String Compression）

Title：String Compression  443

Difficulty：Easy

原题leetcode地址：https://leetcode.com/problems/string-compression

 

1.    双指针

时间复杂度：O(n^2)，嵌套循环，最长可能不需要到n^2。

空间复杂度：O(1)，没有申请额外空间。

    /**
     * 双指针，一个指针指向重复字符串的第一个，另一个指针向后遍历并计数
     * 当计数是一位数时，不需要放入其中
     * 当计数是两位数及两位数以上，需要对这两位数进行拆分
     * @param chars
     * @return
     */
    public static int compress(char[] chars) {

        int len = chars.length;
        int cur = 0;

        for (int i = 0, j =0; i < len; i = j) {
            while (j < len && chars[i] == chars[j]) {
                j++;
            }
            chars[cur++] = chars[i];
            if (j - i == 1) {
                continue;
            }
            for (char c : (j - i + "").toCharArray()) {
                chars[cur++] = c;
            }
        }

        return cur;

    }