2 pointer Python C++解Leetcode 3163 String Compression III

An-Wen Deng
4粉絲
92 次觀看·2024年11月4日
2 pointer Python C++解Leetcode 3163 String Compression III
[codes on Leetcode]https://leetcode.com/problems/string-compression-iii/solutions/6004059/string-with-2-pointers-3ms-beats-99-15/
[2-pointer/Sliding window play list]https://www.youtube.com/watch?v=--IlX3x54nk&list=PLYRlUBnWnd5KrCfs7qCFb-Bvn7dvnakFy
好,各位好,我們來解今天 LeetCode 的問題
今天的問題是第 3163 題
所謂的 String Compression 3 第三版的
這個其實它有好幾版
所以它這個題目跟之前的第二版
第一版應該都比較接近
所以它這裡是給一個字串
叫做 Word
那請你將它壓縮
用下面的演算法
那原則上呢
因為它的數字連續次數呢
它會超過 9 次
所以我們看
我們看一下它的一個立體
那這比較清楚它的壓縮的一個方法
比方說是
它這個立體
ABCDE
那它這個根據它的一個壓縮的方法
就是要怎麼樣呢
前面的數字代表它是一個 A
一個 B
一個 C
一個 D
一個 E
結果壓縮方法比原始的方法還要長
所以這個壓縮方法
實際上並沒有真正那麼好
好,那我們再看第二個立體
第二個立體呢
前面有 14 個 A
再來是兩個 B
兩個 B 的部分當然很簡單
就是 2B
好,14 個 A 的話就把它拆解
根據它的題目
它最多 9 次嘛
所以怎麼辦呢
就 9 加 5 等於 14 嘛
所以這是 9A、5A
它採用這樣的方式
這樣我們比較快速的對著題義
有一個瞭解
然後它那個字串的長度
可能最長可以到 20 萬
所以算蠻長的
那 Word 頂多
只有所謂的小寫的英文字母
接下來我們要看我們
在 Python 上大概怎麼解答
好
好,我們先用 Python 來解答
我們看一下
解答的方式當然是用所謂的
two-point 的一個方式
所謂的雙指標
那我們一開始先把我們的
變數的初值都先給定
n 就代表那個 Word 的長度
那我們還有兩個
遊標一個是 L
另外一個是 R
它分別的初值都為 0
所以它一開始是
Length of Words
那其他的話都是 0
這沒有問題
好,然後呢
因為 Python 的字串是不可變的
所以我們先用 list 先去裝
裝它的一個字源
這樣的話比較好處理
所以我們裡面
接下來就用迴圈
迴圈當然你可以用單迴圈或者
多重回圈
我們習慣使用多重回圈
所以只要是
右邊的遊標 R
如果是小於它的長度
我們都去進行下面的事情
那原則上它那個 L 遊標
左標的話
我們就先取它的
字源的
是哪一個字源
說 Words 在 L 的字源
好,然後呢
我們再去考慮
下面的 while loop
只要是 R 是小於 n
而且呢
我們的 Word
在 R 的值
因為我們的 R 是要變動的
是如果是跟前面的 L
L 遊標的那個字源是相同的
跟 C 是相同的話
我們就移動我們的 R
那移到最後當然就這兩個條件
就其中一個不成立
一個剛好是到了尾端
另外一個當然就是
R 的部分它就不等於 C
所以我們這裡就要計算它的長度
它長度當然在這裡的話就是 R 減 L
那因為我們根據它的提議
它最多九個一組
所以我們這邊要做一個除法
我們這個除法是有餘數的除法
所以有餘數的除法是
那長度是 R 減 L
那除以九
好
那我們就看看
如果說
Q 是大於 0
所以我們就重複 Q 次
下面的動作
所以我們這邊就用 Range 函數
裡面放 Q
好
那
所以我們的這個 List
就加兩個字元
一個是 9
另外一個是 C
好 然後呢
如果你的餘數
是大於 0
我們再做下面的動作
就把餘數部分也把它補上去
這個時候就是 ANS
你要加上
我們這邊用簡單一點的 STR
餘數
要把它轉成字串嘛
然後再加上 C
好
然後
我們的迴圈
要下一個迭代之前
當然要移動我們的遊標
L 這個遊標
為 R
然後最後的地方
我們再 Return
Join
透過這樣的方式
喔 函數當然是擺 ANS
好 我們看一下這樣是不是 OK
好 OK
包括我們自己加上的這個例子
所以
都是 OK 的
好 然後我們就 Submit 看看
好
所以它的一個結果大概是
200 多毫秒
速度也還好
大概是
打敗 70% 以上的 Python 3 的使用者
好 接下來我們再看
其他程式語言的部分
像是 C++ 的部分
我們的邏輯也是類似的
只不過就是說
在這邊的話
我們都是採用 Pushback
裡面放的是自圓
用這樣的方式
我們並沒有將它轉為自串
好 那我們要把它
自信一次
好 Submit
好 所以它的速度是滿快的喔
大概
幾毫秒就完成了
打敗了 98% 以上的 C++ 使用者
好 那我們就先談到這裡
謝謝觀看
下次見
