博主另外一个地址
5654. 盒子中小球的最大数量
题意:
问[l,r]区间中出现ok(x)最多的是
ok(x)定义为各位数字之和
思路
模拟即可
代码
class Solution {
public:
int ok(int x) {
int ans=0;
while(x) {
ans+=x%10;
x/=10;
}
return ans;
}
int countBalls(int lowLimit, int highLimit) {
map<int,int>mp;
for(int i=lowLimit;i<=highLimit;i++) {
int x=ok(i);
mp[x]++;
}
int mx=0;
for(auto item:mp) {
mx=max(mx,item.second);
}
return mx;
}
};
5665. 从相邻元素对还原数组
题意
给定长度为n的二维数组,第二维包含两个数[ai,bi]即ai与bi紧邻,让我们构造出一个一维数组,按照之前给定的相邻方式,保证构造出来的数组中每个数均不同,题目有解
思路
简单离散化对ai和bi之间建立一条边,即可直接dfs搜索出符合题意的路径
代码
class Solution {
public:
int h[400005];
int ne[400005];
int e[400005];
map<int,int>du;
map<int,int>vis;
vector<int>ans;
int n,idx;
void add(int x,int y){
e[idx]=y;
ne[idx]=h[x];
h[x]=idx++;
}
void dfs(int x,int cnt) {
if(cnt>n) {
return ;
}
for(int i=h[x];~i;i=ne[i]) {
int j=e[i];
if(!vis[j]) {
vis[j]=1;
if(j>=100000) ans.push_back(j-200004);
else ans.push_back(j);
dfs(j,cnt+1);
// ans.pop_back();
}
}
}
vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
int len=adjacentPairs.size();
n=len;
memset(h,-1,sizeof h);
for(int i=0;i<len;i++) {
int x=adjacentPairs[i][0];
int y=adjacentPairs[i][1];
if(x<0) x+=200004;
if(y<0) y+=200004;
du[x]++;
du[y]++;
add(x,y);
add(y,x);
}
for(auto item:du) {
int y=item.second;
if(y==1) {
//cout<<item.first;
if(item.first>100000) ans.push_back(item.first-200004);
else ans.push_back(item.first);
vis[item.first]=1;
dfs(item.first,1);
break;
}
}
for(int i=0;i<ans.size();i++) {
if(ans[i]<-100000) ans[i]=100000;
}
reverse(ans.begin(),ans.end());
return ans;
}
};
5667. 你能在你最喜欢的那天吃到你最喜欢的糖果吗?
思路
贪心注意数据范围为longlong
处理一个前缀和数组
ft //第ft类型的糖果
fd//第fd天
dc//每天最多吃dc颗糖果
如果要在第fd天吃到第ft类型的糖果需要满足下述条件:
- (fd+1)*dc>sum[ft-1] 因为fd从第0开始算起,所以要满足在fd+1天每天都吃最多的,其糖果数大于前ft-1个类型的糖果的总和
- fd<sum[ft] 即假设前fd天只吃一个糖果 要保证其值小于sum[ft]前ft个糖果总数
代码
class Solution {
public:
long long int sum[100005];
vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
int lencand=candiesCount.size();
for(int i=0;i<lencand;i++) {
if(i) sum[i]=sum[i-1]+candiesCount[i];
else sum[i]=candiesCount[i];
}
vector<bool>ans;
for(int i=0;i<queries.size();i++) {
long long int ft=queries[i][0];//第ft类型的糖果
long long int fd=queries[i][1];//第fd天
long long int dc=queries[i][2];//每天最多吃dc颗糖果
//cout<<fd*dc<<" "<<sum[ft-1]<<'\n';
if(ft) {
//cout<<(fd+1)*dc<<" "<<sum[ft-1]<<" "<<sum[ft]<<" "<<fd<<'\n';
if((fd+1)*dc>sum[ft-1]&&fd<sum[ft]) ans.push_back(true);
else ans.push_back(false);
}
else {
if((fd+1)<=sum[ft]) ans.push_back(true);
else ans.push_back(false);
}
}
return ans;
}
};
5666. 回文串分割 IV
给你一个字符串 s ,如果可以将它分割成三个 非空 回文子字符串,那么返回 true ,否则返回 false 。
当一个字符串正着读和反着读是一模一样的,就称其为 回文字符串 。
思路
处理一个f[l][r]数组,表示区间[l,r]能否形成一个回文字符串然后枚举两个分割点
即可 i,j使得f[l][i]、f[i+1][j]、f[j+1][r]均可组成一个回文字符串
对于f[l][r],
- 若l==r则f[l][r]=true
- 若r==l+1则f[l][r]=s[l]==s[r]
- 若r>l+1则f[l][r]=s[l]==s[r]&&f[l+1][r-1]
为了保证f[l+1][r-1]状态要在f[l][r]状态前计算出来 因此l可以采用从大到小进行枚举
代码
class Solution {
public:
bool f[2002][2002];
bool checkPartitioning(string s) {
int n=s.length();
for(int l=n-1;l>=0;l--) {
for(int r=l;r<n;r++) {
if(l==r)f[l][r]=true;
else if(r==l+1) f[l][r]=(s[l]==s[r]);
else f[l][r]=s[l]==s[r]&&f[l+1][r-1];
}
}
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
if(f[0][i]&&f[i+1][j]&&f[j+1][n-1]) return true;
}
}
return false;
}
};