首页 > itarticle > [leetcode] problem 443 – string compression

[leetcode] problem 443 – string compression

admin 11月 13, 2020 0

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

No.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”.

No.2

Input:
[“a”]

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

Explanation:
Nothing is replaced.

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
public int (char[] chars) {
    int n = chars.length;
    int idx = 0;

    for (int i = 0, j = 0; i < n; i = j) {
        while (j < n && chars[i] == chars[j])
            j++;

        chars[idx++] = chars[i];

        if (j - i == 1)
            continue;
        
        for (char ch : String.valueOf(j - i).toCharArray())
            chars[idx++] = ch;
    }

    return idx;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能