[閒聊] 每日leetcode 75 - Day6

[yam276 (史萊哲林的優等生)]

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
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.172 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1749199246.A.489.html
※ 編輯: yam276 (60.248.143.172 臺灣), 06/06/2025 16:41:23