主題

LeetCode - 806. Number of Lines To Write String 解題心得

Not In My Back Yard | 2021-01-16 00:00:03 | 巴幣 0 | 人氣 50

題目連結:


題目意譯:
你被給定一小寫英文字母字串 s 以及一個陣列 widths 代表著每個小寫英文字母有多少像素寬。特定地,widths[0] 為 'a' 的寬度 、 widths[1] 為 'b' 的寬度 、 ……以此類推。

你試圖輸出字串 s 到好幾行上,其中每行不超過 100 個像素長。從 s 的開頭開始,寫出盡可能地多的字母到第一行使得總寬度不超過 100 個像素。接著從你上一次在 s 中停留的位置開始,繼續寫盡可能多地字母到第二行上。持續此步驟直到你將 s 中所有字母印出。

回傳一個長度為 2 的陣列 result,其中:
result[0] 為總行數。
result[1] 為最後一行的總像素寬度。

限制:
widths.length == 26
2 ≦ widths[i] ≦ 10
1 ≦ s.length ≦ 1000
s 只包含小寫英文字母。



範例測資:
範例 1:
輸入: widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10] 、 s = "abcdefghijklmnopqrstuvwxyz"
輸出: [3,60]
解釋: 你可以寫出 s 如下:
abcdefghij  // 100 像素寬
klmnopqrst  // 100 像素寬
uvwxyz      // 60 像素寬
總共有 3 行,且最後一行的長度為 60 像素寬。

範例 2:
輸入: widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10] 、 s = "bbbcccdddaaa"
輸出: [2,4]
解釋: 你可以寫出 s 如下:
bbbcccdddaa  // 98 像素寬
a            // 4 像素寬
總共有 2 行,且最後一行的長度為 4 像素寬。


解題思維:
模擬即可。

將一個變數 T 作為一個累加器(一開始為 0)。掃過 s 中每個字母,對於某字母 X ,其在 widths 中對應長度為 W。

先判斷 T + S 是否超過 100。如果有則表示此行已經滿了不能再輸出了,所以要換新的一行,所以將 T 歸零。判斷完之後,將 T 加上 W 之值。

模擬完以上流程後,期間用了多少行還有 T 最後的值即分別是 result[0] 以及 result[1] 之值。




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

創作回應

更多創作