JZ31 题解 | #整数中1出现的次数（从1到n整数中1出现的次数）#

题意分析

• 给出1-n之间的数字，我们需要找出所有的数里面的1个数位的个数有多少。

思路分析

解法一 暴力求解

• 直接暴力写法，从1-n开始进行遍历，我们对每个数进行数位的拆解，然后统计1的个数就行了。

• 代码如下

  • 我们从1-n进行遍历直接判断，时间复杂度为O(n)
  • 我们的代码只开了少部分变量存储值，空间复杂度为(1)

class Solution {
public:
    int getsum(int x){
        int sum=0;
        // 对每个数字进行数位的拆解，统计其中的1的个数
        while(x){
            // 进行数位的拆解
            if(x%10==1){
                sum++;
            }
            x/=10;
        }
        return sum;
    }
    int NumberOf1Between1AndN_Solution(int n) {
        int ans=0;
        // 循环遍历n个数字
        for(int i=1;i<=n;i++){
            ans+=getsum(i);
        }
        return ans;
    }
};

解法二 数位DP

• 这个题目如果数据小的话可以使用直接暴力的方法进行求解。但是如果遇到数据很大的时候就不行了。下面，我使用的是数位DP的方法进行求解。数位DP就是在一个数位的基础上面进行考虑。利用DFS的记忆化搜索的方法进行求解。
  
• 代码如下
  • 这种的写法比较复杂和难懂，但是适用范围大，需要DFS枚举所有位数的情况，时间复杂度为O(状态数*转移数），这个状态数和转移数要看具体的结果。
  • 我们开了一个二维的数组存储当前数位1的个数的情况数目，空间复杂度为O(n^2)

class Solution {
public:
    int a[20];
    int f[25][20];
    // pos表示当前枚举的位置，cnt表示当前的记录的1的个数，limit表示是否有上限的限制
    int dfs(int pos,int cnt,int limit){
        if(pos==0) return cnt;
        // 如果没有最高位的限制才能进行记忆化处理
        if(!limit&&f[pos][cnt]!=-1) return f[pos][cnt];
        // 求出最大可以的数字
        int v=limit?a[pos]:9;
        int res=0;
        // 枚举填充的数字
        for(int i=0;i<=v;i++){
            res+=dfs(pos-1,cnt+(i==1),limit&&(i==v));
        }
        return limit?res:f[pos][cnt]=res;
    }
    // 预处理出上限的数位
    int NumberOf1Between1AndN_Solution(int n) {
        memset(f,-1,sizeof(f));
        int k=0;
        // 对n进行数位的拆解
        while(n){
            a[++k]=n%10;
            n/=10;
        }
        return dfs(k,0,1);
    }
};