当前位置: 代码迷 >> 综合 >> 面试题43:1-n整数中1出现的次数(数位dp)
  详细解决方案

面试题43:1-n整数中1出现的次数(数位dp)

热度:62   发布时间:2024-01-16 18:03:15.0

题意:给定一个数n,问从1到n中,0~9这10个数字分别出现了多少次。比如366这个数,3出现了1次,6出现了2次。

我用的数位dp,dfs参数有些东西没用,仅仅为了调试。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
using namespace std;class Solution {
public:int dfs(int pos,int now,string str, bool lead, bool limit,vector<vector<int>> &dp, int num, string str2){if (pos == -1 ){//cout << str2 << '\t' << num << endl;return num;}if (!limit && !lead && dp[pos][num] != 0) return dp[pos][num];int result = 0;int maxn = limit ? str[pos] - '0':9 ;for (int i = 0; i <= maxn; i++){char c = i + '0';result += dfs(pos - 1, i,str, lead && i == 0, limit && (i == str[pos]-'0'), dp, i == 1 ? num + 1 : num, str2 + c);}if (!limit && !lead && dp[pos][num] == 0) dp[pos][num] = result;return result;}int NumberOf1Between1AndN_Solution(int n){vector<vector<int>> dp(10,vector<int> (10,0));string str = "";while (n){str += n % 10 + '0';n /= 10;}int ans = 0;ans = dfs(str.size()-1, 0,str, 1, 1, dp, 0, "");return ans;}
};
int main()
{Solution ss;int ans = ss.NumberOf1Between1AndN_Solution(1000000);cout << ans << endl;return 0;
}

 

  相关解决方案