主題
題目連結：
題目意譯：
給定一個位數陣列 digits，其按非降序排序。我們可以使用任意次的 digits[i] 來寫下數字。例如，如果 digits = ['1', '3', '5']，則我們可以寫下如 '13' 、 '551' 和 '1351315' 等等的數字。
給定一整數 n，回傳我們可以生出來的小於或等於 n 之正整數的個數。
限制：
1 ≦ digits.length ≦ 9
digits[i].length == 1
digits[i] 為從 '1' 到 '9' 的一位數。
digits 中的數值皆相異。
digits 按非降序排列。
1 ≦ n ≦ 10 ^ 9
範例測資：
範例 1：
輸入： digits = ["1","3","5","7"], n = 100
輸出： 20
解釋：
可以寫下的 20 個數字為：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77。
範例 2：
輸入： digits = ["1","4","9"], n = 1000000000
輸出： 29523
解釋：
我們可以寫下 3 個一位數數字、9 個兩位數數字、27 個三位數數字、
81 個四位數數字、243 個五位數數字、729 個六位數數字、
2187 個七位數數字、6561 個八位數數字以及 19683 個九位數數字。
總計，從陣列 digits 可以寫出 29523 個整數。
範例 3：
輸入： digits = ["7"], n = 8
輸出： 1
解題思維：
假設 n 的位數長為 L 而陣列 digits 的長度為 s，則我們可以任意地使用 digits 來 1 位數、2 位數、……、L - 1 位數長的數字，因為不管怎樣都不會大過 n。例如範例輸入 2 就是一個很好的例子。因此這部分將貢獻
s + s ^ 2 + …… s ^ (L - 1)
個方法數。
（雖然 digits 裡面的是數字字串，但是每次都寫出「""」有點麻煩，因此以下將其省略）
digits = [1, 2, 5]、n = 247，可以看到
247
目前所看到的 2，其代表的是所有位數長 L 且為 1 開頭的數字我們都可以寫出來，例如 111 、 121 、 152 等等。而 1 開頭的數字總共有 3 ^ 2 個。此時 digits 中第一個大於 1 的數字為 2，由於 n = 247 也是以 2 作為開頭，因此我們可能還有機會寫下更多的數字。
因此我們跑到下一位
247
此時看到了 4，代表我們可以有 21 開頭以及 22 開頭的數字（例如 212 或是 225 等等），而這兩類數字總計有 2 × 3 ^ 1 個。但是此時我們可以看到下一個開頭，也就是 25 開頭的數字已經大於現在已經看過的 24 了，所以我們不可能繼續寫出更多的數字。
因此上例中可以寫出的數字為
1 ～ 2 位數數字：3 ^ 1 + 3 ^ 2 個；
3 位數且為 1 開頭： 3 ^ 2 個；
3 位數且為 21 或 22 開頭：2 × 3 ^ 1 個。
總計 27 個。
那如果我們把上例的 n 改成 267，則我們在第二個步驟（21 、 22 開頭那邊）將變為 25 開頭也是可行的，因此能寫下數字總數變為 27 + 3 ^ 1 = 30 個。
而此時可以看到我們一樣不需要繼續往右看新的位數，因為現在看到的這個 6 大於我們 digits 中所有數字。也就是說不管原本的是 260 、 261 還是多少，都會大過我們以 2 開頭的數字（其中最大的即 255）。
那此時如果我們再把 n 改成 252，則當我們看到 5 時做的事情跟第一個例子一樣。因為目前我們只能確認 21 開頭、 22 開頭的，25 開頭要等到我們往右邊看到新的位數才能確認。因此我們產生了第三個步驟
252
此時我們看到了 2。因此我們多了 251 這個數字，注意單看現在的 2 無法確認「252 開頭」的數字是否可以被寫出來。接著我們往右看之後發現現在這個 2 右邊沒有數字了，因此我們此時才能確認 252 是一個可以被寫下來的數字。
也就是說這個例子中可寫下的數字總數為 27 + 1 + 1 = 29 個。
觀察完上面幾個例子之後，我們可以統整為以下：
(陣列 digits 的索引值從 0 開始算)
首先算出 1 ～ L - 1 位數長的數字有多少個，此即為 s + s ^ 2 + …… s ^ (L - 1) 個。
接著從左至右（即高位到低位）掃過數字 n。當我們目前遇到數字 i 且假設數字 i 後面還有 x 個位數要看時，去 digits 裡面找第一個大於或等於 i 的數字 digits[j]（當 i 大過 digits 全部數字時，設 j = s）。此時可以看到此部分將確定出
j × s ^ x
個可以被寫下的數字。此時判斷 i 是否等於 digits[j] 或是 i 大過 digits 所有數字。如果是，則代表我們再繼續下去也不會有新的數字出現（如上面的第二個例子）；反之，則我們繼續看數字 i 右邊的數字。
最後如果整個數字 n 有被成功掃完，則代表 n 本身是由 digits 中的數字所組成的。而上述過程並不會計算到 n 本身，因此還需要再加上 1。而此時所有過程中找到的可寫下數字之總數即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
