443. String Compression字符串压缩

［抄题］：

Given an array of characters, compress it in-place.

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

After you are done modifying the input array in-place, return the new length of the array.

Follow up:
Could you solve it using only O(1) extra space?

Example 1:

Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

Example 2:

Input:
["a"]

Output:
Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.

Example 3:

Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.

[暴力解法]：

时间分析：

空间分析：

[优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

在数组中输入一个1 2时，需要start i同时变

［一句话思路］：

往前走多长，然后截断、更新，属于前向窗口类：end边统计往后走到哪，start边统计可以更新到哪

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

String.valueOf 函数可以将数字转化成字符串。不是.toString，这是针对已有的字符串
只有count != 1时才需要添加，读题时就要备注特殊条件

［二刷］：

用等号表示的最末尾一位是n - 1，也需要备注

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

字符型数组应写成char[], 不是chars[]

［总结］：

［复杂度］：Time complexity: O(n) Space complexity: O(1)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

［关键模板化代码］：

for 循环+ j 满足条件时移动

 for (int end = 0, count = 0; end < chars.length; end++) 
            {
                count++;
            //change if neccessary 
            if (end == chars.length - 1 || chars[end] != chars[end + 1]) {
                chars[start] = chars[end];
                start++;

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

Encode and Decode Strings 用各种类的设计，有基础就还行

[代码风格] ：

写框架时只能把for的重要事项写好，具体换行还是需要自己理解

class Solution {
    public int compress(char[] chars) {
        //cc
        if (chars.length == 0) {
            return 0;
        }
        //ini
        int start = 0;
        
        for (int end = 0, count = 0; end < chars.length; end++) 
            {
                count++;
            //change if neccessary 
            if (end == chars.length - 1 || chars[end] != chars[end + 1]) {
                chars[start] = chars[end];
                start++;
                
            //add to only if (count != 1) 
            if (count != 1) {
                char[] arrs = String.valueOf(count).toCharArray();
                for (int i = 0; i < arrs.length; i++, start++) {
                    chars[start] = arrs[i];
                }
            }
            //reset count           
                count = 0;
            }
            }
        
        //return start;
        return start;
    }
}

View Code