题意很简单，给定一个正整数n，求1-n中，1出现在各个数中的位数的次数之和。
比如针对特定的数12312，global count += 2;因为出现了两个1，输入n，要统计1-n的情况。
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
53
54
|
int VerifyCountOneNumberAns(int n)
{
int ans = 0;
for (int i = 1; i <= n; i++)
{
int tmp = i;
while(tmp)
{
if (1 == tmp%10) ans++;
tmp /= 10;
}
}
return ans;
}
int CountOneNumber(int n)
{
if (n == 0)
return 0;
if (n < 10)
return 1;
vector<int> vNumber;
vNumber.clear();
int tmp = n;
while(tmp)
{
vNumber.push_back(tmp%10);
tmp /= 10;
}
int count = 0;
int vSize = vNumber.size();
count = (vSize - 1) * vNumber[vSize - 1] * (int)pow(10.0, (int)(vSize - 2));
if (vNumber[vSize - 1] > 1)
{
count += (int)pow(10.0, (int)(vSize - 1));
}
else
{
count += n - vNumber[vSize - 1] * (int)pow(10.0, vSize - 1) + 1;
}
count += CountOneNumber(n - vNumber[vSize - 1] * (int)pow(10.0, vSize - 1));
return count;
}
int main()
{
vector<int> ids;
for (int i = 1; i <= 10000; i++)
{
int count = CountOneNumber(i);
int ans = VerifyCountOneNumberAns(i);
if (ans != count)
cout << i << '\t' << ans << '\t' << count << endl;
}
return 0;
}
|
代码中有验证程序，验证程序的正确性是不用怀疑的，然后题目给出了一种递归的方法，时间上还可以接受，应该和数的位数成正比。
PS：自己果然不擅长数学，做起来挺吃力的。不过逻辑还挺好使的。。