压缩字符串（将连续出现的字符转换为字符+个数）String Compression

矫情吗；* 2022-01-14 10:05 195阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

问题：

Given an array of characters, compress it [**in-place**][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`.

解决：

① 双指针。

class Solution \{ //10ms  
public int compress(char\[\] chars) \{  
int index = 0;  
int cur = 1;  
int count = 1;  
while(cur < chars.length)\{  
if (chars\[cur\] == chars\[cur - 1\])\{  
count ++;  
\}else\{  
chars\[index ++\] = chars\[cur - 1\];  
if (count >= 2)\{  
char\[\] tmp = String.valueOf(count).toCharArray();  
for (int i = 0;i < tmp.length;i ++)\{  
chars\[index ++\] = tmp\[i\];  
\}  
\}  
count = 1;  
\}  
cur ++;  
\}  
chars\[index ++\] = chars\[chars.length - 1\];  
if (count >= 2)\{  
char\[\] tmp = String.valueOf(count).toCharArray();  
for (int i = 0;i < tmp.length;i ++)\{  
chars\[index ++\] = tmp\[i\];  
\}  
\}  
return index;  
\}  
\}

② 在discuss中看到的。

class Solution \{//8ms  
public int compress(char\[\] chars) \{  
int index = 0;  
int i = 0;  
while(i < chars.length) \{  
char currentChar = chars\[i\];  
int count = 0;  
while(i < chars.length && chars\[i\] == currentChar) \{  
i ++;  
count ++;  
\}  
chars\[index ++\] = currentChar;  
if(count != 1) \{  
for(char c : Integer.toString(count).toCharArray()) \{  
chars\[index ++\] = c;  
\}  
\}  
\}  
return index;  
\}  
\}

转载于:https://my.oschina.net/liyurong/blog/1602611

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220114/b8df959b77674ea992f0f4960ccfe74b.png
[in-place]: https://en.wikipedia.org/wiki/In-place_algorithm