Re: [閒聊] 每日LeetCode
443. String Compression
給定一個 character array: chars，需要將他壓縮，
把原本的陣列改成壓縮後的結果，並回傳它的長度。
壓縮方式如下:
從一個空的字串 s 開始，
原本的 chars 可以由左至右分成多個 group，
每個 group 都由最長連續的相同字元組成，
如果這個 group 的大小為 1，則將該字元單獨加入 s，
如果大小大於 1，則將該字元以及出現次數加入 s。
額外規定: 只使用常數大小的額外空間
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:
"aabbccc" 壓縮成 "a2b2c3"
長度為 6 並將字串拆成 6 個字元放到 chars 的前6個位置。
Example 2:
Input: chars = ["a"]
Output: Return 1, and the first character of the input array should be:
["a"]
Explanation:
"a" 只單獨出現一個，不需要加入出現次數，因此壓縮後還是 "a"。
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:
"abbbbbbbbbbbb"，a 出現 1 次，b 出現 12 次，壓縮後為 "ab12"。
解題思路:
記住當前比對的是哪個字元，出現幾次，
如果遇到不同字元就把前面的結果直接放進原始陣列就好，
壓縮後一定會變小或是不變，所以不會蓋到還沒處理到的資料。
C++ code:
class Solution {
public:
int compress(vector<char>& chars) {
char temp = chars[0];
int count = 0, pos = 0;
for(int i = 0; i < chars.size(); i++){
if(chars[i] == temp) count++;
if(i + 1 >= chars.size() || chars[i] != chars[i+1]){
chars[pos++] = temp;
if(count > 1){
// input size <= 2000
static vector<int> digits{1000, 100, 10, 1};
for(auto j : digits){
if(count >= j) chars[pos++] = (count / j % 10) + '0';
}
}
if(i + 1 < chars.size()){
temp = chars[i+1];
count = 0;
}
}
}
return pos;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.229.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1677721215.A.B00.html
推
03/02 09:46,
2年前
, 1F
03/02 09:46, 1F
※ 編輯: idiont (140.113.229.216 臺灣), 03/02/2023 09:50:23
推
03/02 12:33,
2年前
, 2F
03/02 12:33, 2F
推
03/02 12:40,
2年前
, 3F
03/02 12:40, 3F
推
03/03 15:51,
2年前
, 4F
03/03 15:51, 4F
討論串 (同標題文章)
完整討論串 (本文為第 256 之 719 篇)：