一小时自信AK，结果还是掉出了100名。。。

写一波题解，ACM公众号的题解就给广哥去更新了（手动滑稽）

周赛传送门

https://leetcode-cn.com/contest/weekly-contest-162

5255. 奇数值单元格的数目

题目

给你一个 n 行 m 列的矩阵，最开始的时候，每个单元格中的值都是 0。

另有一个索引数组 indices，indices[i] = [ri, ci] 中的 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。

你需要将每对 [ri, ci] 指定的行和列上的所有单元格的值加 1。

请你在执行完所有 indices 指定的增量操作后，返回矩阵中「奇数值单元格」的数目。

示例 1：

输入：n = 2, m = 3, indices = [[0,1],[1,1]]
输出：6
解释：最开始的矩阵是 [[0,0,0],[0,0,0]]。
第一次增量操作后得到 [[1,2,1],[0,1,0]]。
最后的矩阵是 [[1,3,1],[1,3,1]]，里面有 6 个奇数。

示例 2：

1
2
3

输入：n = 2, m = 2, indices = [[1,1],[0,0]]
输出：0
解释：最后的矩阵是 [[2,2],[2,2]]，里面没有奇数。

提示：

1 <= n <= 50
1 <= m <= 50
1 <= indices.length <= 100
0 <= indices[i][0] < n
0 <= indices[i][1] < m

题解

这题是一个简单的模拟题，我们只需要跟着题目的描述操作就可以

首先我们创建一个新的二维向量，然后遍历indices这个vector然后对相应地位置+1即可

最后我们遍历二维向量统计奇数个数

class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        vector<vector<int>> v=vector(n+10,vector<int>(m+10,0));
        for(auto x:indices){
            for(int i=0;i<m;i++) v[x[0]][i]++;
            for(int i=0;i<n;i++) v[i][x[1]]++;
        }
        int ans=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(v[i][j]&1) ans++;
        return ans;
    }
};

5256. 重构 2 行二进制矩阵

题目

给你一个 2 行 n 列的二进制数组：

矩阵是一个二进制矩阵，这意味着矩阵中的每个元素不是 0 就是 1。
第 0 行的元素之和为 upper。
第 1 行的元素之和为 lower。
第 i 列（从 0 开始编号）的元素之和为 colsum[i]，colsum 是一个长度为 n 的整数数组。

你需要利用 upper，lower 和 colsum 来重构这个矩阵，并以二维整数数组的形式返回它。

如果有多个不同的答案，那么任意一个都可以通过本题。

如果不存在符合要求的答案，就请返回一个空的二维数组。

示例 1：

1
2
3

输入：upper = 2, lower = 1, colsum = [1,1,1]
输出：[[1,1,0],[0,0,1]]
解释：[[1,0,1],[0,1,0]] 和 [[0,1,1],[1,0,0]] 也是正确答案。

示例 2：

1 2	输入：upper = 2, lower = 3, colsum = [2,2,1,1] 输出：[]

示例 3：

1 2	输入：upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1] 输出：[[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

提示：

1 <= colsum.length <= 10^5
0 <= upper, lower <= colsum.length
0 <= colsum[i] <= 2

题解

首先题目一开始没看仔细，然后wa了一发，压压惊之后猛然发现矩阵中的元素不是0就是1这个条件，突然醒悟QAQ

首先判断一下有没有答案，我们来思考一下，矩阵的每行的和与每列的和肯定是相等的，所以说如果colsum和upper+lower都不相等的话那我们就可以直接返回空的vector>了，然后当两个值是相同的时候就一定有答案吗？

答案是不一定的，这里举个例子

upper = 1，lower = 3，colsum = [2，2]

可以发现并没有答案，upper=1这个很致命

那么我们就发现了更深层次的问题，其实这个题就是upper和lower的分解问题（也就是upper和lower被colsum分解）

由于只有两行，但是可以有很多列，所以显而易见我们是按列从左到右去填值的（按行你可以试试，试出来算我输）

所以一共三种分解的情况（因为矩阵是二进制的矩阵）

colsum==0，代表矩阵这一列都是0，upper和lower也不会被减
colsum==2，很和谐的情况，表示upper和lower都要减一，矩阵两行也都要填1
colsum==1，upper和lower其中一个需要减一，那么肯定是两个中取大的那个减一，因为我们要尽可能的找到答案（如果upper或lower被减成负数显然没有答案）

最后判断一下upper和lower有没有变成负数，变成负数就说明没答案了

class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& col) {
        int sum=0;
        for(auto x:col) sum+=x;
        if(sum!=upper+lower) return vector<vector<int>>();
        int n=2,m=col.size();
        vector<vector<int>> v(n,vector<int>(m,0));
        for(int i=0;i<m;i++){
            if(col[i]==2){
                v[0][i]=v[1][i]=1;
                upper--,lower--;
            }
            else if(col[i]==1){
                if(upper>=lower) v[0][i]=1,upper--;
                else v[1][i]=1,lower--;
            }
        }
        if(upper<0||lower<0) return vector<vector<int>>();
        return v;
    }
};

5257. 统计封闭岛屿的数目

题目

有一个二维矩阵 grid ，每个位置要么是陆地（记号为 0 ）要么是水域（记号为 1 ）。

我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。

如果一座岛屿完全由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为「封闭岛屿」。

请返回封闭岛屿的数目。

示例 1：

输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2
解释：
灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。

示例 2：

1 2	输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]] 输出：1

示例 3：

输入：grid = [[1,1,1,1,1,1,1],
             [1,0,0,0,0,0,1],
             [1,0,1,1,1,0,1],
             [1,0,1,0,1,0,1],
             [1,0,1,1,1,0,1],
             [1,0,0,0,0,0,1],
             [1,1,1,1,1,1,1]]
输出：2

提示：

1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <=1

题解

这一题我觉得我的思路应该是很巧妙的了

首先如果不熟悉这题的建议百度四连通，刷一刷普通的四连通题

好的，我们假设你已经会四连通了，接下来看我下面的思路

这题唯一的区别就在于如果连到边界的联通块是不能被计算进答案里的，那么我们可以利用这一点进行逆向思维

我们直接跑一圈边界，主动出击把边界的连通块全部干掉

对边界上的所有0块进行dfs或bfs的四连通，但是不计算进答案

然后再对里面的块进行四联通，计算进答案里

就是这个小变化就能AC这题

class Solution {
public:
    int n,m;
    int dx[4]= {0,0,-1,1};
    int dy[4]= {-1,1,0,0};
    void dfs(vector<vector<int>>& g,int x,int y){
        g[x][y]=1;
        for(int i=0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx>=0&&nx<n&&ny>=0&&ny<m&&g[nx][ny]==0)
                dfs(g,nx,ny);
        }
    }
    int closedIsland(vector<vector<int>>& g) {
        n=g.size(),m=g[0].size();
        int ans=0;
        if(n==1||m==1) return 0;
        for(int i=0;i<m;i++){
            if(g[0][i]==0) dfs(g,0,i);
            if(g[n-1][i]==0) dfs(g,n-1,i);
        }
        for(int i=0;i<n;i++){
            if(g[i][0]==0) dfs(g,i,0);
            if(g[i][m-1]==0) dfs(g,i,m-1);
        }
        for(int i=1;i<n-1;i++)
            for(int j=1;j<m-1;j++)
                if(g[i][j]==0)
                    dfs(g,i,j),ans++;
        return ans;
    }
};

5258. 得分最高的单词集合

题目

你将会得到一份单词表 words，一个字母表 letters （可能会有重复字母），以及每个字母对应的得分情况表 score。

请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：能够由 letters 里的字母拼写出的任意属于 words 单词子集中，分数最高的单词集合的得分。

单词拼写游戏的规则概述如下：

玩家需要用字母表 letters 里的字母来拼写单词表 words 中的单词。
可以只使用字母表 letters 中的部分字母，但是每个字母最多被使用一次。
单词表 words 中每个单词只能计分（使用）一次。
根据字母得分情况表score，字母 'a', 'b', 'c', … , 'z' 对应的得分分别为 score[0], score[1], …, score[25]。
本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和。

示例 1：

输入：words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
输出：23
解释：
字母得分为  a=1, c=9, d=5, g=3, o=2
使用给定的字母表 letters，我们可以拼写单词 "dad" (5+1+5)和 "good" (3+2+2+5)，得分为 23 。
而单词 "dad" 和 "dog" 只能得到 21 分。

示例 2：

输入：words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
输出：27
解释：
字母得分为  a=4, b=4, c=4, x=5, z=10
使用给定的字母表 letters，我们可以组成单词 "ax" (4+5)， "bx" (4+5) 和 "cx" (4+5) ，总得分为 27 。
单词 "xxxz" 的得分仅为 25 。

示例 3：

输入：words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
输出：0
解释：
字母 "e" 在字母表 letters 中只出现了一次，所以无法组成单词表 words 中的单词。

提示：

1 <= words.length <= 14
1 <= words[i].length <= 15
1 <= letters.length <= 100
letters[i].length == 1
score.length == 26
0 <= score[i] <= 10
words[i] 和 letters[i] 只包含小写的英文字母。

题解

第四题找对思路就不难

首先看数据范围就感觉不对劲，怎么会这么小呢，结果果然是一题暴搜

看到15这个神奇的数字，我果断来了波二进制暴搜，然后一发AC了

首先我们对所有能用的字母进行一下哈希，统计一下每个字母出现了几次

然后我们先进行一下（无谓）的剪枝，如果words有存在根本不可能被拼出来的单词的话就直接删除这个单词

最后进行二进制的暴搜，枚举所有状态并判断可行性，如果可行就更新答案

class Solution {
public:
    int s[30],t[30],tt[30];
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        memset(s,0,sizeof s);
        vector<string> v;
        bool flag;
        for(auto x:letters) s[x-'a']++;
        for(auto str:words){
            memcpy(t,s,sizeof s);
            flag=true;
            for(auto c:str){
                t[c-'a']--;
                if(t[c-'a']<0){
                    flag=false;
                    break;
                }
            }
            if(flag) v.push_back(str);
        }
        int ans=0;
        int n=v.size();
        for(int i=0;i<(1<<n);i++){
            memcpy(t,s,sizeof s);
            flag=true;
            int sum=0;
            for(int j=0;j<n;j++){
                if(i>>j&1){
                    bool f=true;
                    for(auto c:v[j]){
                        t[c-'a']--;
                        sum+=score[c-'a'];
                        if(t[c-'a']<0){
                            flag=false;
                            f=false;
                            break;
                        }
                    }
                    if(!f) break;
                }
            }
            if(flag) ans=max(ans,sum);
        }
        return ans;
    }
};

In The End

Leetcode周赛第162场题解

周赛传送门

5255. 奇数值单元格的数目

题目

题解

5256. 重构 2 行二进制矩阵

题目

题解

5257. 统计封闭岛屿的数目

题目

题解

5258. 得分最高的单词集合

题目

题解