切換
舊版
前往
大廳
主題

ZeroJudge - d139: Compressed String 解題心得

Not In My Back Yard | 2019-01-17 22:41:34 | 巴幣 0 | 人氣 182

題目連結:


題目大意:
給定一個字串 S (長度小於 1, 000 ),對其使用一種壓縮法:將連續出現的字母,替換為出現次數 + 字母本身。沒有節省長度的就維持原樣。

例如:AAABBC,會變為3ABBC。其中BB不變是因為「2B」跟「BB」佔的長度一樣,因此保持原樣即可。



範例輸入:
AAABCDDEFFFF
CCCCCCCCCCBC



範例輸出:
3ABCDDE4F
10CBC



解題思維:
多觀察幾個例子可以發現,維持原樣的字母,其連續出現的長度必為 1 或是 2 。

因此當我們從字串的第二個字元(第一個字元可以不看),看是否跟前面一個字元一樣。如果不一樣,判斷上一字元出現的次數,為 1 或是 2 就不變;若是長度 ≧ 2 ,則套用題目的壓縮法;如果跟前一個字元一樣,就把當前字元的出現次數 + 1 。

以上的替換可以是宣告一個新的字串去做,也可以直接對原字串做修改。最後,輸出即可。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作