当前位置:

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

访客 2024-01-15 1338 0

关键词:数位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;};

发表评论

  • 评论列表
还没有人评论,快来抢沙发吧~