Solved
Medium
Topics
Companies
Hint
Given an array of characters chars, compress it using the following algorithm:
Begin with an empty string s. For each group of consecutive repeating characters in chars:
- If the group's length is
1, append the character tos. - Otherwise, append the character followed by the group's length.
The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.
After you are done modifying the input array, return the new length of the array.
You must write an algorithm that uses only constant extra space.
Example 1:
Input: chars = ["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: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".
Example 2:
Input: chars = ["a"] Output: Return 1, and the first character of the input array should be: ["a"] Explanation: The only group is "a", which remains uncompressed since it's a single character.
Example 3:
Input: chars = ["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: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".
Constraints:
1 <= chars.length <= 2000chars[i]is a lowercase English letter, uppercase English letter, digit, or symbol.
google 翻譯：
給定一個字元數組 chars，使用以下演算法對其進行壓縮：
以空字串 s 開頭。 對於 chars 中的每組連續重複字元：
如果群組的長度為 1，則將字元附加到 s。
否則，附加字符，後跟組的長度。
壓縮後的字串 s 不應單獨傳回，而應儲存在輸入字元數組 chars 中。
請注意，長度為 10 或更長的群組將被拆分為 chars 中的多個字元。
修改完輸入數組後，返回數組的新長度。
您必須編寫一個僅使用恆定額外空間的演算法。
想法一：
剛開始我一直困在「這樣要怎麼反解壓縮」，後來去看了大神的寫法，
才發現這個題目跟本就不管解壓縮，那就好辦了。
存目前字元的變數，然後判斷相同的個數，最後再寫入回傳陣列
寫法一：
int compress(char* chars, int charsSize) {
int write = 0, count = 0, read = 0;
char current, buf[8];
// 讀完所有字元
while(read < charsSize) {
current = chars[read];
// 判斷有幾個字元相同
count = 0;
while(read < charsSize && current == chars[read]) {
count++;
read++;
}
// 把這個字元寫入回傳陣列
chars[write++] = current;
if(count > 1) {
// 相同的字元大於1個，要把數值用字串的方式寫回陣列
sprintf(buf, "%d", count);
memcpy(&chars[write], buf, strlen(buf));
write += strlen(buf);
}
}
/* 因為這一行，所以一直跑出
* ==22==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000051
* at pc 0x55fefc1d2377 bp 0x7ffd2f4582f0 sp 0x7ffd2f4582e0
* 最後才發現是死在傳進這個 func 的 char* chars 長度只有 1
* 而我在上面有執行 write++，所以到這一行時是 chars[1] = '\0'
* 已經超過它的記憶體，才會報錯，找了很久，哈哈哈
*/
// chars[write] = '\0';
// 回傳陣列長度
return write;
}
結果一：
想法二：
改進數字寫回陣列的地方，先計算有幾位數，再從高位數依序寫回陣列。
寫法二：
int compress(char* chars, int charsSize) {
int write = 0, count = 0, read = 0;
char current;
while(read < charsSize) {
current = chars[read];
// 判斷有幾個字元相同
count = 0;
while(read < charsSize && current == chars[read]) {
count++;
read++;
}
// 把這個字元寫入回傳陣列
chars[write++] = current;
if(count > 1) {
// 相同的字元大於1個，要把數值用字串的方式寫回陣列
// 先看有幾位數
int div = 1;
while(count / div >= 10)
div *= 10;
// 先從高位數寫回陣列
while(div > 0) {
chars[write++] = (count / div) + '0';
count %= div;
div /= 10;
}
}
}
// 回傳陣列長度
return write;
}
結果二：
想法三：
改進數字寫回陣列的地方，用判斷的方式判斷有幾位數，再從高位數依序寫回陣列。
寫法三：
int compress(char* chars, int charsSize) {
int write = 0, read = 0, count = 0;
char current;
while(read < charsSize) {
current = chars[read];
// 判斷有幾個字元相同
count = 0;
while(read < charsSize && current == chars[read]) {
count++;
read++;
}
// 把這個字元寫入回傳陣列
chars[write++] = current;
if(count > 1) {
// 相同的字元大於1個，要把數值用字串的方式寫回陣列
int k = count;
// 用判斷的方法決定位數，寫回陣列
if(count >= 1000) { chars[write++] = (k / 1000) + '0'; k %= 1000; }
if(count >= 100) { chars[write++] = (k / 100) + '0'; k %= 100; }
if(count >= 10) { chars[write++] = (k / 10) + '0'; k %= 10; }
chars[write++] = k + '0';
}
}
// 回傳陣列長度
return write;
}
結果三：
後記：
看到有人這樣判斷位數，覺得好厲害啊
if(count > 1) {
int k = floor(log10(count))+1; // 計算共有幾位數 (floor 是無條件捨去)
int tmp;
while(k--) {
tmp = pow(10, k); // pow 是次方，所以這裡是 10的k次方
chars[write++] = count / tmp + '0';
count %= tmp;
}
}
但在這裡的效果差異不大，記錄一下...
沒有留言:
張貼留言