1 題目描述 求出1~13的整數中1出現的次數,並算出100~1300的整數中1出現的次數？為此他特別數了一下1~13中包含1的數字有1、10、11、12、13因此共出現6次,但是對於後面問題他就沒轍了。ACMer希望你們幫幫他,並把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數（從1 ...
1 題目描述
求出1~13的整數中1出現的次數,並算出100~1300的整數中1出現的次數？為此他特別數了一下1~13中包含1的數字有1、10、11、12、13因此共出現6次,但是對於後面問題他就沒轍了。ACMer希望你們幫幫他,並把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數（從1 到 n 中1出現的次數）。2 思路和方法
統計整數n中的每個十進位位中1出現的次數，再累加起來。 對於每一位來說可以把一個數拆分為 前面（ begin）+中間（ middle）+後面（end ）。 1234的百位 = 1+2+34
（編程之美）找數字規律，五行代碼：
首先要知道以下規律：
從 1 至 10，在它們的個位數中，1出現了 1 次；
從 1 至 100，在它們的十位數中，1出現了 10 次；
從1至1000，在它們的百位數中，1出現了100次；
依次類推，從 1 至 10 i，在它們的左數第二位(右數第 i 位)，1出現了 (10 i-1)次。這個規律很容易驗證。
我們以n=21345為例來使用這個規律。首先分析個位1出現了幾次。從1~21340數字1總共出現了2134*1次，最後剩下21341、21342、21343、21344、21345，所有還出現1次數字1。所以個位共出現1的次數為2135次。
接下來分析十位中1出現了幾次。從1~21300數字1總共出現了213*10次，剩下的數字從 21301至 21345，它們最大的十位數是 4 > 1，所以還有10次。所以十位共出現2140次。
接下來分析百位中1出現了幾次。從1至21000數字1共出現了21*100次。剩下的數字是21001~21345，最大的百位數是3，大於1，所以還有100次。所以百位中1共出現了2200次。
接下來分析千位中1出現了幾次。從120000數字1共出現了2*1000次。剩下的數字是2000121345，最大的千位數是1，等於1，這種情況稍微比較複雜，因為它並不包括所有千位為1的數字，即1000個，這種情況取決於低位上的數字，為345+1=346次。最後總計2346次。
接下來分析萬位中1出現了幾次。因為它是最高位了因此直接看最高位的數字，即2,2>1。很顯然10000~19999中1在萬位共出現了10000次。如果最高位等於1那就和上一步的思想一樣。
通過以上幾步的分析我們可以得出結果：1~21345中1共出現了18821次。
3 C++核心代碼
簡潔版：https://blog.csdn.net/typantk/article/details/88386888（講解的太好了）
1 class Solution { 2 public: 3 int NumberOf1Between1AndN_Solution(int n) 4 { 5 int ones = 0; 6 for (long m = 1; m <= n; m *= 10) 7 ones += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0); 8 return ones; 9 } 10 };View Code
代碼較多
1 class Solution { 2 public: 3 int NumberOf1Between1AndN_Solution(int n) 4 { 5 int temp = n; 6 int last; 7 int result = 0; 8 int base = 1; 9 while(temp){ 10 last = temp%10; //個位數是否為1 11 temp = temp/10; //去掉個位數 12 result += temp*base; 13 if (last==1){ 14 result += n%base + 1; 15 } 16 else if(last>1){ 17 result += base; 18 } 19 base *= 10; 20 } 21 return result; 22 } 23 };View Code
4. C++完整代碼
1 #include <iostream> 2 3 using namespace std; 4 5 long long fun(long long n) 6 { 7 if (n < 1) 8 return 0; 9 long long count = 10, num = 0, begin, middle, end, m; 10 begin = n; 11 middle = 0; 12 end = 0; 13 while (begin) 14 { 15 begin = n / count; 16 m = n%count; 17 middle = m / (count / 10); 18 end = m % (count / 10); 19 if (middle > 1) 20 num = num + (count / 10) * (begin + 1); 21 else if (middle == 1) 22 num = num + (count / 10) * begin + (end + 1); 23 else 24 num = num + (count / 10) * begin; 25 count = count * 10; 26 } 27 return num; 28 } 29 30 int main() 31 { 32 long long n, m; 33 while (scanf("%lld %lld", &n, &m) != EOF) 34 { 35 if (n>m) 36 printf("%lld\n", fun(n) - fun(m - 1)); 37 else 38 printf("%lld\n", fun(m) - fun(n - 1)); 39 } 40 printf("%\n"); 41 42 system("pause"); 43 return 0; 44 }View Code
https://blog.csdn.net/zhoubin1992/article/details/47361969
參考資料
https://blog.csdn.net/typantk/article/details/88386888（講解的太好了）
https://blog.csdn.net/u012477435/article/details/83351659#_873
https://blog.csdn.net/qq_25343557/article/details/79330274（講解的太好了）
