讨论/题目交流/🏆 第 162 场力扣周赛/
🏆 第 162 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 奇数值单元格的数目
4 分 - 重构 2 行二进制矩阵
5 分 - 统计封闭岛屿的数目
6 分 - 得分最高的单词集合

展开讨论

第一题:

看着数据量暴力模拟统计即可,其实也可以,直接统计一下每个行每个列分别加了多少次,对于每个格子,就可以通过对应的行和列直接计算出值

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

第二题

这个题理解题意后就不难了。2值,要么就是0要么就是1,如果某一列加起来等于0,那么这一列两个数都是0,如果某一列加起来等于2,那么这一列两个数都是1。
把和为0和2的列先填了,把upper和lower减去相应的1,剩下的upper和lower相加必须等于和为1的列,第一行填upper个1,第二行填lower个1即可

class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        vector<vector<int>> ret(2, vector<int>(colsum.size(), 0));
        int cal = 0;
        for (int i = 0;i < colsum.size();i++) {
            if (colsum[i] == 0) {
                ret[0][i] = ret[1][i] = 0;
            } else if (colsum[i] == 1) {
                cal++;
            } else {
                ret[0][i] = ret[1][i] = 1;
                upper--;
                lower--;
            }
        }
        if (upper < 0 || lower < 0 || upper + lower != cal) {
            return {};
        } else {
            for (int i = 0;i < colsum.size();i++) {
                if (colsum[i] == 1) {
                    if (upper > 0) {
                        ret[0][i] = 1;
                        ret[1][i] = 0;
                        upper--;
                    } else {
                        ret[0][i] = 0;
                        ret[1][i] = 1;
                        lower--;
                    }
                }
            }
            return ret;
        }
    }
};

第三题:

跟leetcode-130相似。找陆地的题大家应该做得挺多了,循环找到一个陆地,从这个陆地开始把相邻能到达的陆地一起连起来算作一片陆地,访问到的陆地置为已访问。直到把所有的陆地都访问过,就可以得到总共多少封闭岛屿了。

这个题还有一个条件,如果岛屿靠近矩阵边缘,就不算封闭岛屿。这个也容易处理,只需要把矩阵边缘的陆地先访问,把能到达矩阵边缘的陆地全部置为已访问,再进行封闭岛屿的统计

class Solution {
public:
    void run(vector<vector<int>>& grid, int x, int y) {
        int n = grid.size();
        int m = grid[0].size();
        
        queue<vector<int>> Q;
        Q.push({x, y});
        grid[x][y] = 1;
        
        int vx[] = {0,0,1,-1};
        int vy[] = {1,-1,0,0};
        
        while (!Q.empty()) {
            vector<int> res = Q.front();
            Q.pop();
            
            for (int i = 0;i < 4;i++) {
                vector<int> next = {res[0] + vx[i], res[1] + vy[i]};
                if (next[0] >= 0 && next[0] < n && next[1] >= 0 && next[1] < m && grid[next[0]][next[1]] == 0) {
                    grid[next[0]][next[1]] = 1;
                    Q.push(next);
                }
            }
        }
    }
    int closedIsland(vector<vector<int>>& grid) {
        
        int n = grid.size();
        int m = grid[0].size();
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (i == 0 || j == 0 || i == n - 1 || j == m - 1) {
                    if (grid[i][j] == 0) {
                        run(grid, i, j);
                    }
                }
            }
        }
        int ret = 0;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < m;j++) {
                if (grid[i][j] == 0) {
                    ret++;
                    run(grid, i, j);
                }
            }
        }
        return ret;
    }
};

第四题:

跟上一周一样,纯枚举,words的数量才15,枚举words子集总共2^15种情况,对于每个子集,统计一下这个子集每个字母用了多少次,是不是letters的子集,如果是,计算得分

class Solution {
public:
    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;
    }
    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;
    }
};
10
展开全部 22 讨论