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的次数

#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;
}

题解里面也有人说是数位DP,再学习学习思路

最后

以上就是高贵日记本为你收集整理的leetcode 233 小于等于n的所有正整数中1出现的个数 思维的全部内容，希望文章能够帮你解决leetcode 233 小于等于n的所有正整数中1出现的个数 思维所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。