[leetcode] 443. String Compression
程序员文章站
2024-03-14 13:50:40
...
题目:
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:
- All characters have an ASCII value in
[35, 126]
. -
1 <= len(chars) <= 1000
.
代码:
class Solution {
2
public:
3
int compress(vector<char>& chars) {
4
if(chars.size() == 0) return 0;
5
int cnt = 1;
6
int place = 0;
7
for(int i = 1; i < chars.size(); i++){
8
if(chars[i] != chars[i-1]){
9
chars[place++] = chars[i-1];
10
if(cnt != 1){
11
string num = to_string(cnt);
12
for(int j = 0; j < num.size(); j++){
13
chars[place++] = num[j];
14
}
15
cnt = 1;
16
}
17
}else{
18
cnt++;
19
}
20
}
21
chars[place++] = chars[chars.size() - 1];
22
if(cnt != 1){
23
string num = to_string(cnt);
24
for(int j = 0; j < num.size(); j++){
25
chars[place++] = num[j];
26
}
27
}
28
return place;
29
}
30
};
Custom
上一篇: Centos修改主机名hostname
下一篇: js 实现DES加密解密
推荐阅读
-
[leetcode] 443. String Compression
-
Leetcode——443. String Compression
-
LeetCode 443. String Compression
-
443. String Compression
-
LeetCode443. String Compression
-
leetcode 443. String Compression
-
leetcode 443. String Compression
-
[leetcode]443. String Compression
-
[leetcode]443. String Compression
-
443. String Compression