关于算法-数据结构:PAT甲级1049-Counting-Ones

题目粗心：

给出一个数字 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;
}