今日学习记录
1. 3747. 统计移除零后不同整数的数目
关键词：数位dp 数学
问题分析：
题目给出一个 n,要求 1 到 n 中的没有 0 的不同数的个数,其中1<=n<=10^15
核心思路:
数学
可以直接一遍遍历,核心思想是直接构建数字,我们可以从小开始遍历观察
在一位时,有 19 可以选择,在二位时 1099 时,当 10,20,30 出现时,就是 1,2,3,但是这些数字在一位时已经出现过了,所以在讨论二位的时候出现 0 就会降位,但是我们已经计算过了低位的数字,所以我们在讨论高位时就可以不考虑 0 了,即使用 19 的数构建二位数,这个数量不就是 9x9=81 吗,同理在三位,四位数中都是如此,开始时,设 pows 为 m 位-1 的 9 的组合
实现中,我们从高位开始遍历,当首位为 n 时,我们有 1n 个重复的选择,即,每次选了之后把 pow9 除 9
代码:
class Solution {
public:
long long countDistinct(long long n) {
string s = to_string(n);
int m = s.size();
long long sum = pow(9,m);
long long ans = (sum-9)/8;
for(int i = 0;i<m;i++){
char c = s[i];
if(c=='0') break;
int d = c-'1';
if(i==m-1) d++;
sum /= 9;
ans += d*sum;
}
return ans;
}
};数位 dp
比赛时写不到 dp,干脆直接 dfs+记忆化
class Solution {
public:
long long countDistinct(long long n) {
string s = to_string(n);
int len = s.length();
vector arr(len,vector<long long>(2,-1));
auto dfs = [&](this auto&&dfs,int p,bool flge,bool b)->long long{
if(p == len) return b?1:0;
if(arr[p][flge]!=-1) return arr[p][flge];
int limit = flge?s[p] - '0':9;
long long res= 0;
if(!b) res += dfs(p+1,false,false);
for(int i = 1;i<=limit;i++) res += dfs(p+1,flge&&(i==limit),true);
if(b) arr[p][flge] = res;
return res;
};
return dfs(0,true,false);
}
};学到的点：
- 数学
- 数位 dp
2. 3748. 统计稳定子数组的数目
关键词：前缀和 二分搜索
问题分析
核心思路
最终代码：
学到的点： 1.