LWC 56：443. String Compression
LWC 56：443. String Compression
LWC 56：443. String Compression
Problem:
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.
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:
All characters have an ASCII value in [35, 126].
1 <= len(chars) <= 1000.
思路： 非常暴力，按顺序计数即可，遇到不同重新归零，记录上一回合信息。
代码如下：
public int compress(char[] chars) {
int n = chars.length;
if (n == 0) return 0;
StringBuilder sb = new StringBuilder();
char p = chars[0];
int cnt = 1;
for (int i = 1; i < n; ++i) {
if (chars[i] == p) {
cnt ++;
}
else {
if (cnt == 1) {
sb.append(p);
}
else {
sb.append(p + "" + cnt);
}
cnt = 1;
}
p = chars[i];
}
if (cnt == 1) {
sb.append(p);
}
else {
sb.append(p + "" + cnt);
}
for (int i = 0; i < sb.length(); ++i) {
chars[i] = sb.charAt(i);
}
return sb.length();
}优化一下：
public int compress(char[] chars) {
int n = chars.length;
if (n == 0) return 0;
char p = chars[0];
int cnt = 1;
int tot = 0;
for (int i = 1; i < n; ++i) {
if (chars[i] == p) {
cnt ++;
}
else {
if (cnt == 1) {
chars[tot++] = p;
}
else {
chars[tot++] = p;
String num = String.valueOf(cnt);
for (int j = 0; j < num.length(); ++j) {
chars[tot++] = num.charAt(j);
}
}
cnt = 1;
}
p = chars[i];
}
if (cnt == 1) {
chars[tot++] = p;
}
else {
chars[tot++] = p;
String num = String.valueOf(cnt);
for (int j = 0; j < num.length(); ++j) {
chars[tot++] = num.charAt(j);
}
}
return tot;
}腾讯云开发者
