首页 > 代码库 > 1的数目

1的数目

2024-07-02 17:29:48   230人阅读

给定一个十进制正整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有“1”的个数
例如：
N = 2， 写下1， 2.这样纸出现了1个“1”。
N = 12， 我们会写下1， 2， 3， 4， 5， 6， 7， 8，9， 10， 11， 12。这样，1的个数为5.
问题：
写一个函数f（N），返回1到N之间出现的“1”的个数。比如f（12）=5

 

 1 #include <iostream>
 2 using namespace std;
 3 // o(nlogn)，判断每个数中有多少个1
 4 int numOfOnes1(int n)
 5 {
 6     int i, j, count;
 7     count = 0;
 8     for (i = 1; i <= n; i++)
 9     {
10         j = i;
11         while (j)
12         {
13             if (j % 10 == 1)
14                 count++;
15             j /= 10;
16         }
17     }
18     return count;
19 }
20 /*
21     通过不断例子，我们发现了一定的规律
22     不失一般性, 对于5位数而言，N = abcde
23     我们可以分别求各个位数上"1"的个数，下面我们先求百位上"1"的个数
24     若c > 1, 百位上"1"的个数为100 * （高位数字 +１）
25     若c = 1, 百位上"1"的个数为100 * 高位数字 + （低位数字 + 1）
26     若c = 0, 百位上"1"的个数为100 * 高位数字
27     简单分析就可以知道为o(len)的时间复杂度，快了很多倍啊
28 */
29 int numOfOnes2(int n)
30 {
31     int i, count, high, low, cur;
32     i = 1;
33     count = 0;
34     while (n >= i)
35     {
36         high = n / (i * 10);
37         cur = (n / i) % 10;
38         low = n % i;
39         if (cur == 0)
40             count += high * i;
41         else if (cur == 1)
42             count += high * i + low + 1;
43         else
44             count += (high + 1) * i;
45         i *= 10;
46     }
47     return count;
48 }
49 int main()
50 {
51     int n;
52     n = 120;
53     //test
54     cout<<numOfOnes1(n)<<endl;
55     cout<<numOfOnes2(n)<<endl;
56     system("pause");
57     return 0;
58 }

 

 


联系
我们