周赛162

题目 && 分析

第一题

给你一个 n 行 m 列的矩阵，最开始的时候，每个单元格中的值都是 0。
另有一个索引数组 indices，indices[i] = [ri, ci] 中的 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。
你需要将每对 [ri, ci] 指定的行和列上的所有单元格的值加 1。
请你在执行完所有 indices 指定的增量操作后，返回矩阵中 「奇数值单元格」 的数目。

分析1

可能存在数学的解法，不过当时想了几分钟没啥头绪，就暴力了。
按照题目的意思构建一个 m*n 的矩阵
然后进行矩阵的填充
最后统计奇数的个数

第二题

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

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

你需要利用 upper，lower 和 colsum 来重构这个矩阵，并以二维整数数组的形式返回它。
如果有多个不同的答案，那么任意一个都可以通过本题。
如果不存在符合要求的答案，就请返回一个空的二维数组。

分析2

S1: 判断是否存在符合要求的答案: - upper 和 lower 的和必须等于 colsum 的和 - colsum 的 size 减去 colsum 中 0 的个数，这个值必须同时大于 upper 和 lower 的任意一个
S2: 初始化 2 行 size 列的矩阵，该矩阵初始化为全零矩阵
S3: - 当 colsum[i]==2 时，结果矩阵的两列必然全为 1 - 当 colsum[i]==1 时，先填充 0 行，同时 upper–，直至 upper 等于 0 时，开始填充第 1 行
S4: 返回结果矩阵

第三题

有一个二维矩阵 grid ，每个位置要么是陆地（记号为 0 ）要么是水域（记号为 1 ）。
我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。
如果一座岛屿 完全 由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 「封闭岛屿」。
请返回封闭岛屿的数目。

传送门

分析3

标准的深搜题，类比 No.200

本题关键的一个隐藏条件:
如果岛屿靠近矩阵边缘，就不算封闭岛屿

两种处理办法: - 在回溯矩阵前，将所有边缘陆地变为海洋 - 在回溯矩阵时，如果遇到边缘，记录下来，不添加到结果中

在实际的操作中，两种解法的思路是一样的，只是处理条件的顺序不一样而已，取舍看个人

第四题

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

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

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

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

分析4

枚举。
枚举 words 子集总共 2^15 种情况，对于每个子集，统计一下这个子集每个字母用了多少次，是不是 letters 的子集，如果是，计算得分

代码

// Q1：

class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        vector<vector<int> > vec = vector(n,vector(m,0));

        for(auto i:indices){
            for(int j = 0;j < m; j++)
                vec[i[0]][j]++;
            for(int j = 0;j < n; ++j)
                vec[j][i[1]]++;
        }

        int count = 0;
        for(auto i:vec)
            for(auto j:i)
                if(j%2 == 1)
                    count++;

        return count;

    }
};


// Q2:

class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        int sum_res = 0,count2 = 0,count0 = 0;
        for(auto i:colsum){
            sum_res+=i;
            if(i == 2) count2++;
            if(i == 0) count0++;
        }

        if(sum_res!=(upper+lower) || (((colsum.size()-count0)<upper && (colsum.size()-count0)>lower) || ((colsum.size()-count0)>upper && (colsum.size()-count0)<lower)) )
            return {};

        vector<vector<int>> res(2,vector(colsum.size(),0));

        upper -= count2;
        lower -= count2;

        for(int i = 0 ; i< colsum.size() ; ++i){
            if(colsum[i] == 2){
                res[0][i] = 1;
                res[1][i] = 1;
            }else if(colsum[i] == 1){
                if(upper){
                    res[0][i] = 1;
                    upper--;
                }else{
                    res[1][i] = 1;
                }
            }else{
                continue;
            }
        }

        return res;

    }
};



// Q3:

class Solution {
public:
    int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}},m,n;
    vector<vector<bool>> visited;
    bool flag;

    int closedIsland(vector<vector<int>>& grid) {
        m=grid.size();
        if(m==0){
            return 0;
        }
        n=grid[0].size();

        int res = 0;
        visited=vector<vector<bool>>(m,vector<bool>(n,false));

        for(int i=1;i<m-1;i++){
            for (int j=1;j<n-1;j++){
                if(grid[i][j]==0 && !visited[i][j]){
                    flag = false;
                    res++;
                    recursion(grid,i,j);
                    if(flag)
                        res--;
                }
            }
        }

        return res;
    }

    void recursion(vector<vector<int>>& grid,int startx,int starty){

        visited[startx][starty]=true;

        for(int i=0;i<4;i++){
            int newx=startx+d[i][0];
            int newy=starty+d[i][1];
            if(!judge(newx,newy)) flag = true;
            if(judge(newx,newy) && grid[newx][newy]==0 && !visited[newx][newy]){
                recursion(grid,newx,newy);
            }
        }

        return;
    }

    bool judge(int x,int y){
        return x>=0 && y>=0 && x<m && y<n;
    }
};


//Q4:

class Solution {
public:
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        vector<int> stat(26, 0);
        for (char& c: letters) {
            stat[c - 'a']++;
        }

        int ret = 0;
        for (int i = 1;i < (1 << words.size());i++) {
            vector<int> g = group(words, i);
            int temp = 0;
            for (int j = 0;j < 26;j++) {
                if (g[j] > stat[j]) {
                    temp = -1;
                    break;
                } else {
                    temp += g[j] * score[j];
                }
            }
            if (temp != -1) {
                ret = max(ret, temp);
            }
        }
        return ret;
    }


    vector<int> group(vector<string>& words, int bit) {
        vector<int> ret(26, 0);
        for (int i = 0;i < words.size();i++) {
            if (bit & (1 << i)) {
                for (int j = 0;j < words[i].size();j++) {
                    ret[words[i][j] - 'a']++;
                }
            }
        }
        return ret;
    }
};

后记

也许吧(⊙o⊙)…