主題
題目連結：
題目意譯：
如果某個正整數的所有位數都不一樣，則我們稱呼該整數為特殊的。
給定一正整數 n，回傳位於區間 [1, n] 之內的特殊整數之個數為何。
限制：
1 ≦ n ≦ 2 × 10 ^ 9
範例測資：
範例 1：
輸入： n = 20
輸出： 19
解釋： 除了 11 以外，所有從 1 到 20 的整數都是特殊的。因此有 19 個特殊整數。
範例 2：
輸入： n = 5
輸出： 5
解釋： 所有從 1 到 5 的整數都是特殊的。
範例 3：
輸入： n = 135
輸出： 110
解釋： 從 1 到 135 之間有 110 個整數是特殊的。
某些不特殊的整數為：22 、 114 和 131。
解題思維：
跟以前這種題目的精神一致：
假設 n 的位數長為 L，並將 n 視為一字串（即 n[0] 為最左邊的位數、n[1] 為左邊數來第二個位數、……以此類推）
則我們先計算出長度 < L（即 1 ～ L - 1）的數字有幾個是特殊整數（把這邊的答案合計稱為 A1）：
對於每個長度值 x，第一個（最左邊）位數有 9 種（1 ～ 9），而第二個位數則有 9 種（除了第一個位數選擇的都可以），第三個位數則有 8 種……以此類推直到第 x 位數為止。
因此對於這個長度來說，特殊整數之數量為 9 × (9 × 8 × …… × (11 - x))。
接著是長度恰好是 L 且開頭數字 < n[0] （即以 1 ～ n[0] - 1 開頭）的數字。跟上面類似，第一個位數有 n[0] - 1 種選擇，而第二個位數有 9 種，第三個位數則有 8 種……以此類推直到第 L 位數為止。因此總數量為 (n[0] - 1) × (9 × 8 × …… × (11 - x))。把這邊的答案稱為 A2。
最後是長度剛好 L 且開頭數字又剛好是 n[0] 的數字（稱此部分的總和形成的答案為 A3）：
接下來看 n[1]，其實就跟求 A2 的方式差不多，我們先看第二個位數 < n[1] 的數字。這樣子的第二個位數有 n[1] - 1 個……除了可能要排除掉 n[0] 這個數字（如果 n[0] < n[1] 你就需要排除；反之則不用。稱其為 X）。所以數量為 X × (10 - 2) × (10 - 3) × ……直到把所有的剩餘位數都求完。
而此時如果 n[1] 剛好等於 n[0]，則不需要繼續看下去了；反之，則我們需要考慮第二個位數等於 n[1] 的數字。
因此這樣子的過程可以把推廣成：
假設現在在 n[i]，第 i - 1 位數 < n[i]。如此的位數大約有 n[i] - 1 個，但要記得要扣掉先前看過的數字（即 n[0] ～ n[i - 1]。稱正確的數量為 X'）。其數量為 X' × (10 - i - 1) × (10 - i - 2) × ……直到剩餘位數算完為止。
而此時如果 n[i] 等於先前的某個位數，則沒有必要繼續看下去；反之則繼續考慮下一位數 n[i + 1]。
而如果過程中沒有中途中斷，也就是說 n 的每一個位數都不一樣。而這表示 n 本身也是特殊整數，但過程中不會算到它本身，因此我們需要把它也加進去。
最後把所有部分的答案加總，即 A1 + A2 + A3，即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
