leetcode 233 小于等于n的所有正整数中1出现的个数思维

95 阅读 0 评论 63 点赞

我是靠谱客的博主高贵日记本，这篇文章主要介绍leetcode 233 小于等于n的所有正整数中1出现的个数思维，现在分享给大家，希望可以做个参考。

这题思路倒不是很难想，倒是在代码的实现上花了很多时间
举例对于
1506这个数
分别考察个位十位百位千位，
个位上是6 说明出现了一个1
十位上是0 说明除了个位上的6 还出现了0组个位上的（0，1，2，……9）+0
百位上是5 说明该位上出现了一个1，百位上的1，每个都要出现100次， +100
同时十位上，个位上也出现了1，对于各位上的1，每组（0，1，2……9）有50组，所以+50 对于十位上的1，每组(0,1,2,3……9)有5个，每个1出现10次，所以+5*10
同时对于千位上的1，它自己在千位上出现了507次(1000到1506)
在个位上有100个组每组中的1出现1次，所以总共出现100次，在十位上有10个组，每组中的1出现10次，总共100次，在百位上，有1个1千，每组中的1出现100次，
相加一共1008次
总之每位先算出它本身在这个位上1出现的次数，这个分情况讨论，分为0，1，大于1，然后再算出由于这个位的存在，导致在它后面的位上出现的1的次数

复制代码

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define ll long long
#define MAXN 1000
int n;
int main()
{ 
	while (scanf("%d", &n) != EOF)
	{
		ll ans = 0;
		ll temp;
		ll t = 1;
		ll bitsum = 0;
		ll cnt = 0;
		while (n)
		{
			temp = n % 10;
			if (temp >= 1)
			{
				if (temp == 1)
				{
					ans += (bitsum+1);
				}
				else
				{
					ans += t;
				}

				ans += temp * cnt * (t / 10);
			}
			bitsum += temp*t;
			cnt++;
			t *= 10;
			n = n / 10;
		}
		printf("ans=%lldn", ans);
	}
	return 0;
}