题目:输入一个整数n,求1-n这n个整数的十进制表示中1出现的次数。例如,输入12,1-12这些整数中包含1的数字有1、10、11和12,一共出现了5次。
接下来我们用C++进行编程,时间复杂度是O(logn):
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53int NumberOf1Between1AndN(int n) { if(n <= 0) return 0; char strN[50] //功能与printf大致相同,只是把结果输出到指定字符串中 sprintf(strN, "%d", n); return NumberOf1(strN); } int NumberOf1(const char* strN) { if(!strN || *strN < '0' || *strN > '9' || *strN == '') return 0; int first = *strN - '0'; //类型转换 unsigned int length = static_cast<unsigned int>(strlen(strN)); if(length == 1 && first == 0) return 0; if(length == 1 && first > 0) return 1; //假设strN是“21345” //numFirstDigit是数字10000-19999的第一位中的数目 int numFirstDigit = 0; if(first > 1) numFirstDigit = PowerBase10(length - 1); else if(first == 1) //将字符串转换成整数 numFirstDigit = atoi(strN + 1); //numOtherDigits是1346-21345除第一位之外的数位中的数目 int numOtherDigits = first * (length - 1) * PowerBase10(length - 2); //numRecursive是1-1345中的数目 int numRecursive = NumberOf1(strN + 1); return numFirstDigit + numOtherDigits + numRecursive; } int PowerBase10(unsigned int n) { int result = 1; for(unsigned int i = 0; i < n; ++i) result *= 10; return result; }
最后
以上就是落后云朵最近收集整理的关于算法面试_1-n整数中1出现的次数的全部内容,更多相关算法面试_1-n整数中1出现内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复