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记忆化数组的表示方法,限制条件用代码应该怎么表达,然后就可以套模板了。
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/291364.html