第84场周赛

用户1145562

发布于 2020-10-23 08:06:17

42000

代码可运行

文章被收录于专栏：LC刷题LC刷题

运行总次数：0

代码可运行

传送门

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	index B	1	2
0	1	1	0	0	0
1	0	1	1	1	1
2	0	1	2	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;
    }