題目描述:
給定一組字元,使用原地算法将其壓縮。
壓縮後的長度必須始終小于或等于原數組長度。
數組的每個元素應該是長度為1 的字元(不是 int 整數類型)。
在完成原地修改輸入數組後,傳回數組的新長度。
進階:
你能否僅使用O(1) 空間解決問題?
輸入示例1:
輸入:
["a","a","b","b","c","c","c"]
輸出:
傳回6,輸入數組的前6個字元應該是:["a","2","b","2","c","3"]
說明:
"aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。
輸入示例2:
輸入:
["a"]
輸出:
傳回1,輸入數組的前1個字元應該是:["a"]
說明:
沒有任何字元串被替代。
輸入示例3:
輸入:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]
輸出:
傳回4,輸入數組的前4個字元應該是:["a","b","1","2"]。
說明:
由于字元"a"不重複,是以不會被壓縮。"bbbbbbbbbbbb"被“b12”替代。
注意每個數字在數組中都有它自己的位置。
注意:
所有字元都有一個ASCII值在[35, 126]區間内。
1 <= len(chars) <= 1000。
class Solution {
public:
int compress(vector<char>& chars) {
int len=chars.size();
int k=0;
for(int i=0;i<len;){
char target=chars[i];
int count=0;
while(i<len&&target==chars[i]){
i++;
count++;
}
chars[k++]=target;
if(count!=1){
string temp=to_string(count);
for(char c:temp)
chars[k++]=c;
}
}
return k;
}
};