第84场周赛
832. 翻转图像
题解：根据描述，我们按照描述一步一步来就行。
vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {
for(int i=0;i<A.size();++i){
for(int j=0;j<A[i].size();++j){
A[i][j] =(!A[i][j]);
}
reverse(A[i].begin(),A[i].end());
}
return A;
}833. 字符串中的查找与替换
题解：根据描述，有如下想法，对于测试点1，只要找到首个匹配字符位置，末尾字符匹配位置，使用replace函数替换即可。在下轮替换的时候，开始找的位置应为由于插入而带来的字符串长度改变的偏置。
根据这一想法，可以通过前8个测试点。后面的替换位置并不是有序的，因此我们需要把替换位置sort一下。重写一下输入的数据结构。
struct tmp{
int index;
string source;
string target;
};
static bool cmp(struct tmp a,struct tmp b){
return a.index<b.index;
}
string findReplaceString(string &S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
vector<struct tmp>v(indexes.size());
for(int i=0;i<indexes.size();++i){
v[i].index = indexes[i];
v[i].source = sources[i];
v[i].target = targets[i];
}
sort(v.begin(),v.end(),cmp);
int bisa=0;
for(int i=0;i<indexes.size();++i){
int k=0,j,start=0;
if(i=0)j = v[i].index;
else j = v[i].index+bisa;
start=j;
for(;j<S.length();++j){
if(S[j]!=v[i].source[k])
break;
else k++;
}
if(k==v[i].source.length()){
S.replace(S.begin()+start,S.begin()+start+v[i].source.length(),v[i].target);
//每次替换带来了偏置
bisa += v[i].target.length()-v[i].source.length();
}
}
return S;
}835. 图像重叠
题解：根据描述，数据量在0-30范围内，使用蛮力算法即可。枚举A中出现的1，对于B中出现的1，有相同偏置的位置在记录数组中加一。比如
index A | 0 | 1 | 2 | index B | 0 | 1 | 2 |
|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
2 | 0 | 1 | 0 | 2 | 0 | 0 | 1 |
对于矩阵A(0,0)处的1，B中所有的1(分别位于[(1,1)(1,2),(2,2)]处)，相对于A(0,0)处的偏置分别为[(1,1)(1,2),(2,2)] 下标相减即可
对于矩阵A(0,1)处的1，B中所有的1(分别位于[(1,1)(1,2),(2,2)]处)，相对于A(0,0)处的偏置分别为[(1,0),(1,1),(2,1)]
对于矩阵A(1,1)处的1，B中所有的1(分别位于[(1,1)(1,2),(2,2)]处)，相对于A(0,0)处的偏置分别为[(0,0),(0,1),(1,1)]
对于矩阵A(2,1)处的1，B中所有的1(分别位于[(1,1)(1,2),(2,2)]处)，相对于A(0,0)处的偏置分别为[(-1,0),(-1,1),(0,2)]
统计偏置数组[(1,1)(1,2),(2,2)]，[(1,0)(1,1),(2,1)]，[(0,0),(0,1),(1,1)]，[(-1,0),(-1,1),(0,2)]，可发现(1,1)出现最多，是为3次。
int largestOverlap(vector<vector<int>>& A, vector<vector<int>>& B) {
int N = A.size();
int count[2*N][2*N];
memset(count,0,sizeof(count));
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
if (A[i][j] == 1)
for (int i2 = 0; i2 < N; ++i2)
for (int j2 = 0; j2 < N; ++j2)
if (B[i2][j2] == 1)
count[i-i2 +N][j-j2 +N] += 1;
int ret = 0;
for(int i=0;i<2*N;++i){
for(int j=0;j<2*N;++j){
ret = max(ret,count[i][j]);
}
}
return ret;
}834. 树中距离之和
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-04-132，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
