225周赛好题分享

这周的周赛是在国际服打的,因为起床就11点了,打国服会掉rating,A了两题,第二题挺有意思,第三题就一个裸的二维前缀和。

1737. 满足三条件之一需改变的最少字符数

这个题刚开始就想着贪心来做了,想在每个字符串中找最大,最小,但是因为两个字符串是可以同时变的,具有后效性,所以不能贪心,但是数据范围不大,可以进行枚举,但是如何来枚举呢,我们可以枚举这个分界点,分别统计在这个分界点之上的和之下的,最后统计将所有的字母变成某一个相同的字母需要的次数,所以只有暴力枚举就好,这个题的思路还是蛮好的。

class Solution {
public:
int minCharacters(string a, string b) {
int ans = a.size()+b.size();
for(char w = 'a'; w <= 'z'; w++) {
if(w >'a') {
int contar1 = 0;
for(char ai: a) contar1 += (ai >= w);
for(char bi: b) contar1 += (bi < w);
ans = min(ans, contar1);
int contar2 = 0;
for(char ai: a) contar2 += (ai < w);
for(char bi: b) contar2 += (bi >= w);
ans = min(ans, contar2);
}
int contar3 = 0;
for(char ai: a) contar3 += (ai != w);
for(char bi: b) contar3 += (bi != w);
ans = min(ans, contar3);

}
return ans;
}
};

1738. 找出第 K 大的异或坐标值

这题没啥好说的裸二维前缀和,然后sort,求top k。注意异或的前缀和求的方式。

const int M = 1000+5;
int dp[M][M];
class Solution {
public:
int kthLargestValue(vector<vector<int>>& matrix, int k) {
memset(dp,0,sizeof(dp));
vector<int> res;
int n= matrix.size();
int m = matrix[0].size();
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
dp[i][j] = (dp[i-1][j] ^ dp[i-1][j-1]) ^ (dp[i][j-1] ^ dp[i-1][j-1]) ^ dp[i-1][j-1] ^ matrix[i-1][j-1];
res.push_back(dp[i][j]);
}
}
sort(res.rbegin(),res.rend());
return res[k-1];
}
};

1739. 放置盒子

典型的找规律题。看不太懂,得题解。

题解