主題
題目連結：
題目意譯：
給定一整數 n，請統計出數字 1 在所有小於或等於 n 的非負整數中的總出現次數。
限制：
0 ≦ n ≦ 10 ^ 9
範例測資：
範例 1：
輸入： n = 13
輸出： 6
範例 2：
輸入： n = 0
輸出： 0
解題思維：
首先，我們先算出數字 1 在一位數、兩位數、……、九位數數字中各自總共出現多少次。次數分別為：
1、
19、
280、
3700、
46000、
550000、
6400000、
73000000、
820000000。
接著我們定義 S[i]，其代表著數字 1 在一位數 ～ i 位數這些數字中總計出現次數，即：
S[1] = 1、
S[2] = 20、
S[3] = 300、
S[4] = 4000、
S[5] = 50000、
S[6] = 600000、
S[7] = 7000000、
S[8] = 80000000、
S[9] = 900000000。
然後特別定義 S[0] = 0。
定義完以上等下需要的變數之後，我們便可以掃過一次 n 的每一個位數來得出所求。以 n = 7018 為例：
70184
當我們看到開頭的數字 7 時，其代表著從 0 數到 n 已經經過了 0XXXX 、 1XXXX 、 2XXXX 、 …… 、 6XXXX（XXXX 為某個四位數的數字，可能含前導零）這些數字，而數字 1 出現於 XXXX 之中總次數恰好為 S[4]。
而 0 開頭 ～ 6 開頭有 7 個數字，因此可以看到我們會有 7 次的 S[4]。並且因為 7 > 1，所以所有開頭為 1 的數字（即 1XXXX）已經都過去了。因此開頭這個位置的數字 1 會被算到 10 ^ 4 次（即 10000 ～ 19999）。
因此現在數字 1 總次數為 7 × 4000 + 10000 = 38000 次。
70184
接下來是數字 0。很不幸地，這個位置沒有任何貢獻。因此現在數字 1 總次數依舊是 38000 次。
70184
接下來是數字 1。類似於開頭的情況，從 0 數到 n 時 __0XX 的數字已經數過了（「_」代表著前面的位數，對於當前情況不影響），所以貢獻了 1 × S[2] 次的數字 1。
而因為當前位數恰好就是數字 1，因此 __100 ～ __184 會使得當前位數的數字 1 被算到 84 + 1 次（這個 84 是當前位數的右側剩餘部分之數字。如果右側沒有剩餘數字，則視為 0）。
因此現在數字 1 總次數為 38000 + 20 + 85 = 38105 次。
70184
接下來是數字 8。與開頭同理，得到數字 1 總次數為 38105 + 8 × S[1] + 10 = 38123 次。
70184
最後是數字 4。與開頭同理，得到數字 1 總次數為 38105 + 4 × S[0] + 1 = 38124 次。
因此 0 ～ 70184 的所有數字中，數字 1 的總出現次數為 38124 次。而其他 n 值也是同理。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
