数据结构学习 jz43 数字 1 的个数

发布时间:2024年01月15日

关键词:数位dp 记忆化搜索 dfs

专门写了数位dp的笔记,里面的第一题和这个是一模一样的。建议直接看链接。

题目:

复杂度计算:

时间复杂度O(log^2 n)

时间复杂度 = 状态个数 * 单个状态的转移次数,状态个数就是 dp 数组的长度,即 O(log^2 n) ,而单个状态的转移次数 = O(10) = O(1),所以时间复杂度为 O(log^2 n)

空间复杂度O(log^2 n)?

代码:

class Solution {
public:
    int fun(int pose,bool islimit,int count, vector<vector<int>>& dp)
    {
        if(pose<0) return count;
        if(!islimit&&dp[pose][count]>=0) return dp[pose][count];
        int temp=0;
        int up=islimit?s[pose]:9;
        for(int i=0;i<=up;++i)
        {
            temp=temp+fun(pose-1,islimit&&i==s[pose],count+(i==1),dp);
        }
        if(!islimit)dp[pose][count]=temp;
        return temp;
    }
    int countDigitOne(int n) {
        while(n)
        {
            s.push_back(n%10);
            n=n/10;
        }
        vector<vector<int>> dp(s.size(),vector<int>(s.size()+1,-1));
        return fun(s.size()-1,true,0,dp);
    }
    vector<int> s;
};

文章来源:https://blog.csdn.net/rainssssss/article/details/135597988
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。