题目粗心：
给出一个数字N，求1~N的所有数字中呈现1的个数
算法思路:
自己采纳了暴力遍历求解，然而只得了22分,参考了算法笔记的思路,间接写在上面思考30710这个数：
首先思考开端为0
咱们计算开端有多少个数是笼罩了1的，那么开端为1的时候后面是只能取0-3070，因为如果取3071，那么就是30711>30710了，共有3071种抉择
而后思考倒数第二位1
它为1，那么后面为0-306的时候，前面一位轻易取都行，当后面为307时，前四位为3071，开端只能取0，那么有306*10+1种取法
而后思考倒数第三位
它为7，如果它为1的话，后面前面都能够轻易取，因为它为7比1要大，只有他们组成的数不大于30710，都是无效的，那么取法共有（30+1）*102种
同理倒数第四位为0
那要令它为1，后面只能取0-2，前面能够任取，共有3*103种
最初倒数第五位
它是3，比1要大，所以它为1时，前面能够任取,共有104种
总结
如果把某个数右边取为leftNum,左边取为rightNum,那么失去的后果有三种可能,expo是以后数字的位数次方（例如123中的2,其位数为1，对应的expo就为10^1）;
1.以后位为0，count += leftNum * expo;
2.以后位为1，count += leftNum*expo+rightNum+1;
3.以后为>1,count += (leftNum+1)*expo
留神点：
1、通过测试，PAT的数据最大数字不超过5位数字，所以数组开到4就好了。
提交后果
AC代码：
#include <cstdio>#include <algorithm>using namespace std;int a[4] = {};int main(){ int N,n; scanf("%d",&N); n = N; int index = 0; while(N!=0){ a[index++] = N%10; N /= 10; } // 逆置 for (int i = 0; i < index/2; ++i) { swap(a[i],a[index-i-1]); } int count = 0;//统计1的个数 int expo = 1;// a[i]对应的10^i int leftNum = n/10; int rightNum = 0; for (int i = index-1; i >= 0; --i) { if(a[i]>1){ // 以后位大于1 count += (leftNum+1)*expo; } else if(a[i]==1){ count += leftNum*expo+rightNum+1; } else { count += leftNum * expo; } expo *= 10; rightNum = n%expo; leftNum /= 10; } printf("%d",count); return 0;}