443. String Compression
https://leetcode.com/problems/string-compression/
題意：
給你一個如 a, a, b, b, b, c, c 的字元陣列
你要讓他們變成 a, 2, b, 3, c, 2 這種簡化陣列
並只能修改原陣列 要 in-place 並回傳修改後陣列的邊界 index
思路：
雙指標
當 chars[left] 不等於 chars[right] 的時候 就開始修改
但還需要一個 write 指標
我一開始想讓 left 做太多事情結果手忙腳亂
正確應該是這樣
示意圖：
Step 1.
遇到 字元[左] 不等於 字元[右]
寫
左 右
↓ ↓
a, a, a, b, b, ...
Step 2.
寫 +1 並寫入 右減左(3-0) 就是 count
左 寫 右
↓ ↓ ↓
a, 3, a, b, b, ...
Step 3.
寫 +1 並 左=右
左
寫 右
↓ ↓
a, 3, a, b, b, ...
Step 4.
右持續 +1 直到遇到 Step 1. 的情況或跑完陣列
寫 左 右
↓ ↓ ↓
a, 3, a, b, b, ...
Step 5.
回傳 write 而不是 left
Code:
impl Solution {
pub fn compress(chars: &mut Vec<char>) -> i32 {
let mut write = 0;
let mut left = 0;
let length = chars.len();
for right in 0..=length {
if right == length || chars[left] != chars[right] {
let count = right - left;
chars[write] = chars[left];
write += 1;
if count > 1 {
for c in (count).to_string().chars() {
chars[write] = c;
write += 1;
}
}
left = right;
}
}
write as i32
}
}