Leetcode第306场周赛（附数位DP总结）
2022/10/18 14:24:50
本文主要是介绍Leetcode第306场周赛（附数位DP总结），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
1、矩阵中的局部最大值
简单题，n×n的矩阵，最后得到(n-2)×(n-2)的矩阵，做法就是枚举每个起点。
class Solution {
public:
int find_max(vector<vector<int>>& grid,int start_i,int start_j){
int num_max = 0;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
num_max = max(num_max,grid[i+start_i][j+start_j]);
}
}
return num_max;
}
vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
int n=grid.size();
vector<vector<int>> ans;
vector<int >ve;
for(int i = 0;i<n-2;i++){
for(int j = 0;j<n-2;j++){
int number = find_max(grid,i,j);
ve.push_back(number);
}
ans.push_back(ve);
ve.clear();
}
return ans;
}
};
2、边积分最高的节点
虽然是一个中档题，但是比第一题还要简单一点，爆int值得注意。
class Solution {
public:
long long edge_num[100000+7];
int edgeScore(vector<int>& edges) {
int n = edges.size();
memset(edge_num,0,sizeof(edge_num));
for(int i=0;i<n;i++){
edge_num[edges[i]]+=i;
}
int ans_num = 0;
long long ans_number = edge_num[0];
for(int i =1;i<n;i++){
if(edge_num[i]>ans_number){
ans_number = edge_num[i];
ans_num = i;
}
}
return ans_num;
}
};
3、根据模式串构造最小数字
本题是一个中档题，根据模式串构造符合条件的字典序最下的新字符串。 思路：贪心。在满足要求的前提下尽可能使用较小的数字去填充。起始数字为s=1，当遇到字符 I 时，填入s即可，然后使s+1，当前字符I之后的数字无论填什么，一定是一个比s大的数，一定可以满足I 的条件。当遇到字符 D 的时候，首先应计算字符 D 往后有多少个连续的字符 D ，假如说当一共有num个字符 D 相连，那么当前位置（首个D之前的待填充数字）所填的数字应该是 s+num ，然后依次递减填充，直到填完 num+1 个数，即填完相连字符D的后边的那个待填充数字。 值得注意的是，字符D前后的数字都会被填充了，但字符I一次只会填充1个数字，即I之前的数字，所以循环结束后，应判断模式串的最后一个字符是I还是D，如果是I的话，应该再补上一个数字。
class Solution {
public:
string smallestNumber(string pattern) {
int start = 1;
int n = pattern.size();
string ans = "";
for(int i =0;i<n;i++){
if(pattern[i]==I)
ans += (0+start);
int pos = 0;
if(pattern[i]==D){
int num = 0 ;
for(int j=i;j<n;j++){
if(pattern[j]==D){
num++;
}
else break;
}
start = start+num;
pos = start;
for(int p = num+1;p>0;p--){
ans+=(0+pos);
pos = pos-1;
}
i = i + num;
}
start++;
}
if(pattern[n-1]==I)
ans+=(0+start);
return ans;
}
};
4、统计特殊整数
数位DP模板题，首先给出数位DP的常用模板(附code 1)。
code1
int dfs(int pos,bool is_limit,bool is_num,...){
if(pos == m){
return is_num ? 1:0;
}
if (!is_limit && is_num && ..dp..) return ..dp..;
int res=0;
if(!is_num)
res = f(pos+1,false, false);
//设置上限值。
int up = is_limit? ve[pos]:9;
for(int i = is_num ? 0:1;i<=up;i++){
if(...){
res+=f(pos+1,(i==up)&&is_limit,true,...);
}
}
if (!is_limit && is_num) ..dp.. = res;
return res;
}
数位DP介绍： 数位DP其实就是在暴力枚举的基础上加了记忆化数组。其通过枚举数字每个数位上的值来枚举1~n的值。结合代码来解释一下各参数的意义，pos表示的是当前枚举到第pos位，is_limit表示的是pos之前的每个数位是否都达到了最大值，比如说n = 4567，若pos=2,第0位为4，第1位为5，那么第pos=2位的值最大不能超过6，如果第0位的值小于4或第1位的值小于5，那么第pos=2处的值最大可以取到9。is_num是用来控制前导0的，若n=4567,如果不控制前导0，33就会被表示位0033，而00可能会对结果有影响，控制前导0后，就不会出现0033这种情况。如果不加记忆化数组，那么这种方法就是一种暴力搜索。 记忆化数组为什么可行呢？这个问题通过例题来解释。
例题1、统计特殊整数（本次竞赛第4题，Leetcode 2376）
方法1 数位DP
class Solution {
public:
vector<int >ve;
int dp[10][1<<10];
// pos表示第pos位，num表示ve大小，mask表示当前填了哪些数（用二进制表示，is_limit表示pos之前的位置上的数是否都是
// 上限值，is_num表示pos位之前是否有数）
int f(int pos,int num,int mask,bool is_limit,bool is_num){
if(pos == num){
return is_num ? 1:0;
}
if (!is_limit && dp[pos][mask] >= 0) return dp[pos][mask];
int res=0;
// 第一种情况，pos位之前的全部位0，且pos位选择填0
if(!is_num)
res = f(pos+1,num,mask,false, false);
// 第二种情况，pos位之前全位0，pos位从1开始填到up（或者pos位之前不全为0，pos位从0开始填）
int up = is_limit? ve[pos]:9;
for(int i = is_num ? 0:1;i<=up;i++){
if(((mask>>i)&1)==0){
res+=f(pos+1,num,mask|(1<<i),(i==up)&&is_limit,true);
}
}
if (!is_limit) dp[pos][mask] = res;
return res;
}
int countSpecialNumbers(int n) {
int m = n;
while(m){
ve.push_back(m%10);
m = m/10;
}
memset(dp,-1,sizeof dp);
reverse(ve.begin(),ve.end());
int num = ve.size();
return f(0,num,0,true,false);
}
};
方法2 思维
class Solution {
public:
// 首先判断是几位数,然后计算出位数对应的特殊整数的数目
int sum_cal(int n){
if(n==1) return 9;
int ans=1;
int pos=9;
for(int i = 9;n>1;n--,i--){
ans*=i;
}
return ans*9;
}
// 从start开始，往后乘n-1次
int cal_(int n,int start){
int ans=1;
for(int i = start;n>0;i--,n--){
ans = ans * i;
}
return ans;
}
int countSpecialNumbers(int n) {
int m=n;
int num=0;
vector<int>ve;
while(m){
num++;
ve.push_back(m%10);
m/=10;
}
// return cal_(1,9);
// return num;
if(num==1) return n;
int ans=0;
for(int i=1;i<num;i++){
ans+=sum_cal(i);
}
// return ans;
bool mask[10];
memset(mask,0,sizeof(mask));
for(int i = num-1;i>0;i--){
if(i==num-1)
ans+=(ve[i]-1)*cal_(i,10-num+i);
else {
int cnt = 0;
for(int j=i+1;j<num;j++){
if(ve[j]<ve[i]){
cnt++;
}
}
ans+=(ve[i]-cnt)*cal_(i,10-num+i);
if (mask[ve[i]]) return ans;
}
mask[ve[i]] = 1;
}
bool judge = 0;
for(int i = 0;i<=ve[0];i++){
if(!mask[i]) ans++;
}
return ans;
}
};
例题2、数字 1 的个数（Leetcode 233）
计算小于等于n的非负整数中数字1出现的个数。 数位dp，定义dp[i][j]表示当考虑到第i位时，i之前一共有 j 个1的数字的个数。 code:
class Solution {
public:
int dp[20][20];
int dfs(int pos,string s,int mask,bool is_limit,bool is_num,int count){
if(pos==s.size()){
return count;
}
if (!is_limit && is_num && dp[pos][count]!=-1) return dp[pos][count];
int res = 0;
if(!is_num){
res = dfs(pos+1,s,mask,false,false,count);
}
int up = is_limit? s[pos]-0:9;
for(int i = is_num ? 0:1;i<=up;i++){
if(i==1)
res+=dfs(pos+1,s,mask|(1<<i),is_limit&&(i==up),true,count+1);
else res+=dfs(pos+1,s,mask|(1<<i),is_limit&&(i==up),true,count);
}
if (!is_limit && is_num) dp[pos][count] = res;
return res;
}
int countDigitOne(int n) {
string s = to_string(n);
memset(dp,-1,sizeof(dp));
return dfs(0,s,0,true,false,0);
}
};
例题3、不含连续1的非负整数（Leetcode 600）
给定一个正整数 n ，返回范围在 [0, n] 都非负整数中，其二进制表示不包含 连续的 1 的个数。 数位DP，将n用二进制进行表示，二进制中数位上限最大为1。定义dp[i][j]表示为考虑到第i位时，前一位为j时的数字满足条件的数字个数。注：这里j的取值只可能是0和1。 code:
class Solution {
public:
int findIntegers(int n) {
vector<int >ve;
int tmp = n;
while(tmp){
ve.push_back(tmp%2);
tmp/=2;
}
reverse(ve.begin(),ve.end());
int m = ve.size();
int dp[m][2];
memset(dp,-1,sizeof dp);
function<int (int,int,bool)> dfs = [&](int pos,int end,bool is_limit) ->int {
if(pos==m){
return 1;
}
if(!is_limit&&dp[pos][end]!=-1) return dp[pos][end];
int res = 0;
int up = is_limit? ve[pos]:1;
for(int i = 0;i<=up;i++){
char x = 0+i;
if(end == 0){
res+=dfs(pos+1,i,is_limit&&(i==up));
}
else{
if(i==1) continue;
res+=dfs(pos+1,i,is_limit&&(i==up));
}
}
if(!is_limit) dp[pos][end] = res;
return res;
};
return dfs(0,0,true);
}
};
例题4、最大为 N 的数字组合（Leetcode 902）
数位DP模板题，定义dp[i]为考虑到第i位解的个数，按照条件，每一位选择的数应该是存在于digits中。
class Solution {
public:
int dp[10];
int atMostNGivenDigitSet(vector<string>& digits, int n) {
map<string,bool>mp;
for(int i=0;i<=9;i++){
auto j = to_string(i);
mp[j]=0;
}
for(auto t:digits){
mp[t]=1;
}
auto s = to_string (n);
int m = s.length();
memset(dp,-1,sizeof dp);
function<int (int ,bool ,bool,string)> dfs = [&](int pos,bool is_limit,bool is_num,string now)-> int {
if(pos==m){
return is_num;
}
if(!is_limit&&is_num&&dp[pos]!=-1) return dp[pos];
int res = 0;
if(!is_num){
res+=dfs(pos+1,false,false,now);
}
for(int i = 0,up = is_limit? s[pos]-0:9; i<=up;i++){
auto j = to_string(i);
if(mp[j]){
res+=dfs(pos+1,is_limit&&(i==up),true,now+j);
}
}
if(!is_limit&&is_num) dp[pos] = res;
return res;
};
return dfs(0,true,false,"");
}
};
总结：数位DP题目的形式往往是求区间[L，R]中满足某个条件的数字的个数，该类题应该清楚的是dp记忆化数组的表示方法，限制条件用代码应该怎么表达，然后就可以套模板了。
这篇关于Leetcode第306场周赛（附数位DP总结）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-22怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享
- 2024-11-22ansible 的archive 参数是什么意思？-icode9专业技术文章分享
- 2024-11-22ansible 中怎么只用archive 排除某个目录？-icode9专业技术文章分享
- 2024-11-22exclude_path参数是什么作用？-icode9专业技术文章分享
- 2024-11-22微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口？-icode9专业技术文章分享
- 2024-11-22uniapp 实现聊天消息会话的列表功能怎么实现？-icode9专业技术文章分享
- 2024-11-22在Mac系统上将图片中的文字提取出来有哪些方法？-icode9专业技术文章分享
- 2024-11-22excel 表格中怎么固定一行显示不滚动？-icode9专业技术文章分享
- 2024-11-22怎么将 -rwxr-xr-x 修改为 drwxr-xr-x？-icode9专业技术文章分享
- 2024-11-22在Excel中怎么将小数向上取整到最接近的整数？-icode9专业技术文章分享
