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:

1
2
3
4
5
6
7
8
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:

1
2
3
4
5
6
7
8
Input:
["a"]

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

Explanation:
Nothing is replaced.

Example 3:

1
2
3
4
5
6
7
8
9
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.

分析

双指针问题。

解决方案1（Python）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def compress(self, chars: List[str]) -> int:
        charsLen = len(chars)
        left = 0
        now = 0
        
        while left < charsLen:
            right = left
            
            while right < charsLen and chars[right] == chars[left]:
                right += 1
            chars[now] = chars[left]
            now += 1
            if right-left > 1:
                for ch in str(right-left):
                    chars[now] = ch
                    now += 1
            left = right
        return now

解决方案2(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int compress(char[] chars) {
        int n = chars.length, current = 0;
        
        for (int i = 0, j = 0; i < n; i = j) {
            int nowCount = 0;
            while(j < n && chars[j] == chars[i]) {
                j++;
                nowCount++;
            }
            chars[current++] = chars[i];
            
            if (nowCount > 1) {
                char[] digits = String.valueOf(nowCount).toCharArray();
                for (char digit: digits) {
                    chars[current++] = digit;
                }
            }
        }
        return current;
    }
}

相关问题

题目来源