主題

LeetCode - 1663. Smallest String With A Given Numeric Value 解題心得

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

題目連結:


題目意譯:
一個小寫字元之數值定義為其於字母表中的位置值(索引值從 1 開始),所以 a 的數值為 1 、 b 的數值為 2 、 c 的數值為 3,以此類推。

一個由小寫字元組成的字串之數值定義為其字元之數值總和。例如,字串 "abe" 之數值等於 1 + 2 + 5 = 8。

你被給定兩整數 n 和 k。回傳字母序最小的字串其長度等於 n 且數值等於 k。

注意一個字串 x 視為字母序小於字串 y 如果 x 在字典序中先於 y,即要嘛 x 為 y 的一個前綴,抑或是如果 i 為第一個位置滿足 x[i] ≠ y[i] 則 x[i] 在字母順序先於 y[i]。

限制:
1 ≦ n ≦ 10 ^ 5
n ≦ k ≦ 26 × n



範例測資:
範例 1:
輸入: n = 3, k = 27
輸出: "aay"
解釋: 字串數值為 1 + 1 + 25 = 27,且其為有著此數值之長度等於 3 之最小字串。

範例 2:
輸入: n = 5, k = 73
輸出: "aaszz"


解題思維:
因為要讓字典序盡量地小,因此所以「大」字母應排於後面。如果 (k - n) 為 25 的倍數的話,我們的所求字串應為以下形式:
a……az……z
其中 z 的數量為 (k - n) ÷ 25,而當中要先減 n 是因為整個字串應至少充滿著 'a'(數值 1);而 a 的數量為 (n - z 的數量)。
若 (k - n) 不為 25 的倍數的話則為以下:
a……aXz……z
其中 z 的數量為 floor((k - n) ÷ 25),而當中 floor() 為下高斯函數(對於正數來說等價於無條件捨去小數點); a 的數量為 (n - z 的數量 - 1);而 X 為一字母,其數值為 (k - n) % 25(即取餘數)。

這樣便可以確保字串總和為 k 且大字母都集中於尾端(因此字典序最小)。




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

創作回應

更多創作