前往
大廳
主題

LeetCode - 0967. Numbers With Same Consecutive Differences 解題心得

Not In My Back Yard | 2023-07-22 12:00:09 | 巴幣 0 | 人氣 86

題目連結:


題目意譯:
給定兩整數 n 和 k,回傳一個裝有所有位數長度 n 的整數之陣列,其中每個整數中相鄰位數之差值為 k。你可以按任意順序回傳。

注意到這些整數不應包含前導零。整數如 02 和 043 是不被允許的。

限制:
2 ≦ n ≦ 9
0 ≦ k ≦ 9



範例測資:
範例 1:
輸入: n = 3, k = 7
輸出: [181,292,707,818,929]
解釋: 注意到 070 並非一個合法的數字,因為它包含著前導零。

範例 2:
輸入: n = 2, k = 1
輸出: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]


解題思維:
由於從開頭之後開始(從尾數往前也行),每個位數可以選擇 +k 或是 -k(先忽視超出 0 ~ 9 範圍的情況)。因此總計會有 9 × 2 ^ (n - 1) 種可能性。而 n 最大也才 9,因此總可能性最大也只有 2304 種而已。

因此直接窮舉所有開頭(即 1 ~ 9),然後每個「下一個」位數選擇 +k 或 -k(這邊就要檢查會不會超過範圍了,如果會超過就不走該路徑;兩個都會超過則直接回到上一層),一路到整數變成長度 n 為止。




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

創作回應

更多創作