A.
class Solution {
public:
string removeTrailingZeros(string num) {
while(num.size()&&num.back()=='0') num.pop_back();
return num;
}
};
B.
class Solution {
public:
vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& g) {
vector<vector<int>> res=g;
int n=g.size(),m=g[0].size();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
{
int x=i-1,y=j-1;
unordered_set<int> st;
while(x>=0&&y>=0){
st.insert(g[x][y]);
x--,y--;
}
int a=st.size();st.clear();
x=i+1,y=j+1;
while(x<n&&y<m){
st.insert(g[x][y]);
x++,y++;
}
int b=st.size();
res[i][j]=abs(b-a);
}
}
return res;
}
};
C.
考虑全变成1或者全变成0的情况
枚举中间为分割点肯定是最优的
如果当前字符不是目标字符串,只能翻转,如果和前一个字母相同且都不是目标字符直接,同时扩展
否则,只能老实翻转当前0-i的区间,且为了不改变0-i-1的区间,所以要同时翻转0-i-1的区间
class Solution {
public:
long long minimumCost(string s) {
int n=s.size();
function<long long(char)> calc=[&](char c)->long long{
long long res=0;
int l=n/2-1;
for(int i=0;i<=l;i++){
if(s[i]!=c)
{
if(i>0&&s[i]==s[i-1]||i==0) res++;
else res+=i+i+1;
}
}
for(int i=n-1;i>l;i--){
if(s[i]!=c){
if(i<n-1&&s[i]==s[i+1]||i==n-1) res++;
else res+=n-1-i+n-i;
}
}
return res;
};
return min(calc('0'),calc('1'));
}
};
D.首先这是个拓扑图
只能从值小的转移到值大的
所以可DP
然后排个序直接转移,暴力会tle
然后观察可得对于i,j的状态只会直接从第i行的最大值和j列的最大值转移过来
所以维护即可类似于单调栈思想,只不过这个单调栈是一直递增的
typedef pair<int,int> pii;
class Solution {
public:
struct node{
int w,x,y;
};
int maxIncreasingCells(vector<vector<int>>& mat) {
int n=mat.size(),m=mat[0].size();
vector<node> a;
map<int,vector<pii>> mp;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
mp[mat[i][j]].push_back({i,j});
}
int res=0;
vector<vector<int>> row(n+1);vector<vector<int>> col(m+1);
for(auto&[k,a]:mp)
{
vector<int> mx;
for(auto&[i,j]:a)
{
int now=1;
if(row[i].size())
now=max(now,row[i][0]+1);
if(col[j].size())
now=max(now,col[j][0]+1);
mx.push_back(now);
res=max(res,now);
}
for(int k=0;k<a.size();k++)
{
auto&[x,y]=a[k];
while(row[x].size()&&row[x].back()<=mx[k])
row[x].pop_back();
row[x].push_back(mx[k]);
while(col[y].size()&&col[y].back()<=mx[k])
col[y].pop_back();
col[y].push_back(mx[k]);
}
}
return res;
}
};