「這是我參與2022首次更文挑戰的第12天，活動詳情檢視：2022首次更文挑戰」
日拱算法，日掘一金。本篇帶來雙指針解“壓縮字元串”~
題：
給你一個字元數組 chars ，請使用下述算法壓縮：
從一個空字元串 s 開始。對于 chars 中的每組 連續重複字元 ：
如果這一組長度為 1 ，則将字元追加到 s 中。 否則，需要向 s 追加字元，後跟這一組的長度。 壓縮後得到的字元串 s 不應該直接傳回 ，需要轉儲到字元數組 chars 中。需要注意的是，如果組長度為 10 或 10 以上，則在 chars 數組中會被拆分為多個字元。
請在 修改完輸入數組後 ，傳回該數組的新長度。
你必須設計并實作一個隻使用常量額外空間的算法來解決此問題。
- 示例 1：
輸入：chars = ["a","a","b","b","c","c","c"] 輸出：傳回 6 ，輸入數組的前 6 個字元應該是：["a","2","b","2","c","3"] 解釋： "aa" 被 "a2" 替代。"bb" 被 "b2" 替代。"ccc" 被 "c3" 替代。
- 示例 2：
輸入：chars = ["a"] 輸出：傳回 1 ，輸入數組的前 1 個字元應該是：["a"] 解釋： 沒有任何字元串被替代。
- 示例 3：
輸入：chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"] 輸出：傳回 4 ，輸入數組的前 4 個字元應該是：["a","b","1","2"]。 解釋： 由于字元 "a" 不重複，是以不會被壓縮。"bbbbbbbbbbbb" 被 “b12” 替代。 注意每個數字在數組中都有它自己的位置。
解題思路：
為了實作原地壓縮，我們可以使用雙指針分别标志我們在字元串中讀和寫的位置。每次當讀指針 read 移動到某一段連續相同子串的最右側，我們就在寫指針 write 處依次寫入該子串對應的字元和子串長度即可。
在實際代碼中，當讀指針 read 位于字元串的末尾，或讀指針 read 指向的字元不同于下一個字元時，我們就認為讀指針 read 位于某一段連續相同子串的最右側。
該子串對應的字元即為讀指針 read 指向的字元串。我們使用變量 left 記錄該子串的最左側的位置，這樣子串長度即為 read−left+1。
為了達到 O(1) 空間複雜度，我們需要自行實作将數字轉化為字元串寫入到原字元串的功能。這裡我們采用短除法将子串長度倒序寫入原字元串中，然後再将其反轉即可。
JavaScript 實作：
var compress = function(chars) {
const n = chars.length;
let write = 0, left = 0;
for (let read = 0; read < n; read++) {
if (read === n - 1 || chars[read] !== chars[read + 1]) {
chars[write++] = chars[read];
let num = read - left + 1;
if (num > 1) {
const anchor = write;
while (num > 0) {
chars[write++] = '' + num % 10;
num = Math.floor(num / 10);
}
reverse(chars, anchor, write - 1);
}
left = read + 1;
}
}
return write;
};
const reverse = (chars, left, right) => {
while (left < right) {
const temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
left++;
right--;
}
} 複制
我是掘金安東尼，輸出暴露輸入，技術洞見生活，再會~