題目: 233. Number of Digit One
難度: Hard
目前下列解法的時間複雜度: O(lg(n))
題目說明
給一個 >=0 的整數 n ，
求 0 到 n (包含) 的所有整數中，位數中的 1 加總共有幾個。
(例如 11 中出現 2 次 1 ； 0~11 中，位數中的 1 共有 4 個：1有1個、10有1個、11有2個)
解法: 分析然後WA再分析、建表建一點點(相較於n)
0. 表:
int tbl[10]={0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000};
// tbl[0]=0; for(int x=1;x!=10;++x) tbl[x] = tbl[x-1]*10 + pow(10,x-1);
1. 只建立 n 為 0, 9, 99, 999, ... 時的表。簡單來說就是 pow(10,位數)-1 。
2. 每新增一個位數，最高位數可能是 0 到 9 ，每種最高位數都有前一次的數量，再加上最高位數是 1 的那些 1 個數量：
tbl[位數] = tbl[位數-1] * 10 + pow(10,位數-1);
3. 每次 n 先 +1 ，然後從最高位數開始看，分為:
a. 最高位數是 0 ，即未滿這麼多。
b. 最高位數是 1 。
c. 最高位數是 >1 。
4. 分情況處理:
a 的情形就是等等再看。
b 的情形就是把最高位數是 1 的部分加完。然後把它去掉最高位數，變成 a 的情形，再看一輪。
c 的情形則是：b 的情形，加上 2xxx 到未達最高位數之前，xxx中1的數量(查表) * 不同的最高位數。然後把它去掉最高位數，變成 a 的情形，再看一輪。
5. 加一加答案就出來了。
source code
難度: Hard
目前下列解法的時間複雜度: O(lg(n))
題目說明
給一個 >=0 的整數 n ，
求 0 到 n (包含) 的所有整數中，位數中的 1 加總共有幾個。
(例如 11 中出現 2 次 1 ； 0~11 中，位數中的 1 共有 4 個：1有1個、10有1個、11有2個)
解法: 分析然後WA再分析、建表建一點點(相較於n)
0. 表:
int tbl[10]={0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000};
// tbl[0]=0; for(int x=1;x!=10;++x) tbl[x] = tbl[x-1]*10 + pow(10,x-1);
1. 只建立 n 為 0, 9, 99, 999, ... 時的表。簡單來說就是 pow(10,位數)-1 。
2. 每新增一個位數，最高位數可能是 0 到 9 ，每種最高位數都有前一次的數量，再加上最高位數是 1 的那些 1 個數量：
tbl[位數] = tbl[位數-1] * 10 + pow(10,位數-1);
3. 每次 n 先 +1 ，然後從最高位數開始看，分為:
a. 最高位數是 0 ，即未滿這麼多。
b. 最高位數是 1 。
c. 最高位數是 >1 。
4. 分情況處理:
a 的情形就是等等再看。
b 的情形就是把最高位數是 1 的部分加完。然後把它去掉最高位數，變成 a 的情形，再看一輪。
c 的情形則是：b 的情形，加上 2xxx 到未達最高位數之前，xxx中1的數量(查表) * 不同的最高位數。然後把它去掉最高位數，變成 a 的情形，再看一輪。
5. 加一加答案就出來了。
source code
