Leetcode 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.

Note:

1. All characters have an ASCII value in [35, 126].
2. 1 <= len(chars) <= 1000.

 

package com.string;

/**
 * Title:
 *
 * @Author
 * @CreateTime 2019/6/19 15:41
 */
public class Leetcode_443_StringCompression {

    /**
     * Runtime: 1 ms, faster than 97.82% of Java online submissions for String Compression.
     * Memory Usage: 36 MB, less than 100.00% of Java online submissions for String Compression.
     *
     * @param chars
     * @return
     */
    public int compress(char[] chars) {
        if (chars.length == 1) {
            return 1;
        }
        int count = 1;
        int index = 0;
        for (int i = 0; i < chars.length; i++) {
            if (i + 1 < chars.length && chars[i] == chars[i + 1]) {
                count++;
            } else {//如果i + 1 >= chars.length 或者 chars[i] != chars[i + 1] 才走这个else
                chars[index] = chars[i];
                if (count == 1) {
                    index += 1;
                } else if (count >= 2 && count <= 9) {
                    chars[index + 1] = getInt(count)[0];
                    index += 2;
                } else if (count >= 10 && count <= 99) {
                    chars[index + 1] = getInt(count)[0];
                    chars[index + 2] = getInt(count)[1];
                    index += 3;
                } else if (count >= 100 && count <= 999) {
                    chars[index + 1] = getInt(count)[0];
                    chars[index + 2] = getInt(count)[1];
                    chars[index + 3] = getInt(count)[2];
                    index += 4;
                } else if (count >= 1000) {
                    chars[index + 1] = getInt(count)[0];
                    chars[index + 2] = getInt(count)[1];
                    chars[index + 3] = getInt(count)[2];
                    chars[index + 4] = getInt(count)[3];
                    index += 5;
                }
                count = 1;
            }
        }//for
        return index;
    }


    public char[] getInt(int dec) {
        return String.valueOf(dec).toCharArray();
    }

    public static void main(String[] args) {
        Leetcode_443_StringCompression object = new Leetcode_443_StringCompression();
        //下面的这个example没有给出，但是这个example很重要！！！
        System.out.println(object.compress(new char[]{'a', 'a', 'b', 'b', 'c', 'c', 'c', 'a', 'a'}));//{a,2,b,2,c,3,a,2},8
        System.out.println(object.compress(new char[]{'a'}));//{a},1
        System.out.println(object.compress(new char[]{'a', 'b', 'c'}));//{a,b,c},3
        System.out.println(object.compress(new char[]{'a', 'a'}));//{a,2},2
    }

}

这个题目很好，但是example给的不全面，

而且不是只输出正确的长度就行的，还需要有正确的字符数组才行，但是题目也没说是用现有chars，还是新生成字符数组，既然是说使用in-place，觉得还是使用chars比较好，只要chars的前n位正确即可，后面的字符无所谓！！