[LeetCode] 443. String Compression

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:

Example 2:

Example 3:

字元串壓縮。

題意是給一個字元串，請按規則壓縮。壓縮的結果還是存在char array中但是最後輸出的是新的char array的長度。

基本邏輯是要求你把連續出現多個的字母轉化成字母 + 出現次數的組合。要求是不使用額外空間。這個題我也不知道該歸為什麼算法或者方法，我這裡解釋一下我的思路吧。做一個while循環和一個指針，首先確定指針不能跳出while循環，條件自然是指針指向的index不能大于input字元串的長度。在周遊input的時候，如果遇到一個新的字母c，先記下這個字母，然後往後周遊看看這個字母是否有連續出現，若有，則需要記錄連續出現的次數count。當連續出現的字元停止之後，此時可以試着将已經周遊過的部分寫入res，因為你有了c和他的count，是以就可以寫入res了。注意需要将count先轉化成String.valueOf然後再轉化成charArray，才能将比如12轉化成"1", "2"這樣的形式。隻要count不等于1，那麼這個數字就一定要被寫入最後的char array。

時間O(n)

空間O(1) - 題目要求

Java實作

相關題目

38. Count and Say

271. Encode and Decode Strings

443. String Compression

604. Design Compressed String Iterator

1313. Decompress Run-Length Encoded List

LeetCode 題目總結