A.暴力枚举左右端点即可
class Solution {
public:
int alternatingSubarray(vector<int>& nums) {
int res=0;
int n=nums.size();
for(int i=0;i<n;i++)
{
int last=nums[i]+1;
int x=-1;int cnt=1;
for(int j=i+1;j<n;j++){
if(nums[j]==last){
cnt++;
res=max(res,cnt);
}
else{
break;
}
last=last+x*1;
x=-x;
}
}
if(res==1||res==0) res=-1;
return res;
}
};
B.直接map统计当前位置有没有东西即可,
class Solution {
public:
vector<int> relocateMarbles(vector<int>& nums, vector<int>& f, vector<int>& t) {
unordered_map<int,int> mp;
int n=nums.size();
for(auto x:nums) mp[x]++;
for(int i=0;i<f.size();i++)
{
int x=f[i],y=t[i];
if(x==y) continue;
mp[y]+=mp[x];mp[x]=0;
}
vector<int> res;
for(auto [k,v]:mp) if(v>0) res.push_back(k);
sort(res.begin(),res.end());
return res;
}
};
C.暴力dp 检测字符串是不是五的二进制即可
class Solution {
public:
int minimumBeautifulSubstrings(string s) {
int n=s.size();
vector<int> f(n+10,0x3f3f3f3f);
s="?"+s;
f[0]=0;
function<bool(int,int)> check=[&](int x,int y)
{
long long res=0;
if(s[x]=='0') return false;
for(int i=x;i<=y;i++) res=res*2+(s[i]-'0');
if(res==0) return false;
while(res%5==0) res/=5;
if(res!=1) return false;
return true;
};
D.枚举每个黑色点的贡献即可,当前黑色点的贡献
只对左上 上 左 当前点有贡献
注意因为要求是22所以,x=n-1 || y==m-1不算
如果题目不是22可以用二维差分优化
typedef pair<int,int> PII;
class Solution {
public:
int dx[9]={-1,-1,0,0},dy[9]={-1,0,-1,0};
vector<long long> countBlackBlocks(int n, int m, vector<vector<int>>& c) {
map<PII,int> mp;
for(int i=0;i<c.size();i++)
{
int x=c[i][0],y=c[i][1];
for(int j=0;j<4;j++)
{
int tx=x+dx[j],ty=y+dy[j];
if(tx<0||ty<0||tx>=n-1||ty>=m-1) continue;
mp[{tx,ty}]++;
}
}
vector<long long> res(5,0);
long long s=1ll*(n-1)*(m-1);
res[0]=s-(int)(mp.size());
for(auto&[k,v]:mp)
{
res[v]++;
}
return res;
}
};