Leetcode 443. 压缩字符串 Java

给定一组字符，使用原地算法将其压缩。

压缩后的长度必须始终小于或等于原数组长度。

数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。

在完成原地修改输入数组后，返回数组的新长度。

进阶：
你能否仅使用O(1) 空间解决问题？

示例 1：

输入：
["a","a","b","b","c","c","c"]

输出：
返回6，输入数组的前6个字符应该是：["a","2","b","2","c","3"]

说明：
"aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。

看到题目的时候，没有原地算法的思路，所有先用了一个StringBuilder里进行记录

    public int compress(char[] chars) {
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (i < chars.length) {
            int sum = 1;
            for (int j = i + 1; j < chars.length; j++) {
                if (chars[j] != chars[i]) {
                    break;
                }
                sum++;
            }
            sb.append(chars[i]);
            if(sum > 1) {
                sb.append(sum);
            }
            i += sum;
        }
        String ans = sb.toString();
        for (int j = 0; j < ans.length(); j++) {
            chars[j] = ans.charAt(j);
        }
        return ans.length();
    }

写过之后，发现既然可以用StringBuilder里记录， 为什么不直接就从chars的开始来记录呢？因为chars遍历后的数据就没有用处了，直接替换chars前面的数据即可。

public int compress(char[] chars) {
        int index = 0; //用来更新chars
        int i = 0; //用来遍历chars
        while (i < chars.length) {
            int sum = 1;
            for (int j = i + 1; j < chars.length; j++) { //找到有几个相等的字符
                if (chars[j] != chars[i]) {
                    break;
                }
                sum++;
            }
            chars[index++] = chars[i];
            if (sum > 1) {
                String s = String.valueOf(sum);
                for (int k = 0; k < s.length(); k++) {
                    chars[index++] = s.charAt(k);
                }
            }
            i += sum;
        }
        return index;
    }

其实在解决问题的时候，刚开始不一定能得到最优解，不过在一步一步的过程中，往往会更加靠近，多思考多动手总没错的。