[剑指Offer] 31.整数中1出现的次数

题目描述

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

【思路1】暴力...另写一个辅助函数判断某个数字中有几个1，在主函数中只要遍历时调用即可。

 1 class Solution
 2 {
 3 public:
 4     int Num_of_one(int x)
 5     {
 6         int num = 0;
 7         while(x)
 8         {
 9             if((x-1)%10 == 0)
10                 num++;
11             x = x/10;
12         }
13         return num;
14     }
15 
16     int NumberOf1Between1AndN_Solution(int n)
17     {
18         int num = 0;
19         for(int i = 1; i <= n; i ++)
20         {
21             num += Num_of_one(i);
22         }
23         return num;
24     }
25 };

【思路2】

设定整数点（如1、10、100等等）作为位置点i（对应n的各位、十位、百位等等），分别对每个数位上有多少包含1的点进行分析
根据设定的整数位置，对n进行分割，分为两部分，高位n/i，低位n%i

下面以百位上的1为例（其余位数同理）：
·当i表示百位，且百位对应的数>=2,如n=31456,i=100，则高位a=314,低位b=56，此时百位为1的次数有a/10+1=32（最高两位0~31），每一次都包含100个连续的点，即共有(a/10+1)*100个点的百位为1
·当i表示百位，且百位对应的数为1，如n=31156,i=100，则高位a=311,低位b=56，此时百位对应的就是1，则共有a/10(最高两位0-30)次是包含100个连续点，当最高两位为31（即a=311），本次只对应局部点00~56，共b+1次，所有点加起来共有a/10*100+b+1，这些点百位对应为1
·当i表示百位，且百位对应的数为0,如n=31056,i=100，则高位a=310,低位b=56，此时共有a/10=31（最高两位0~30）次是包含100个连续点，所有点加起来共有a/10*100个

 1 class Solution {
 2 public:
 3     int NumberOf1Between1AndN_Solution(int n)
 4     {
 5         int i = 1;
 6         int a = n / i,b = n % i;
 7         int num = 0;
 8         while(i <= n)
 9         {
10             if(a % 10 >= 2)
11                 num += (a/10 + 1)*i;
12             else if(a % 10 == 1)
13                 num += a/10*i+b+1;
14             else
15                 num += a/10*i;
16             i = i * 10;
17             a = n / i;
18             b = n % i;
19         }
20         return num;
21     }
22 };