On the shoulders of giants.

weekly-contest-162

奇数值单元格的数目

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

另有一个索引数组 indicesindices[i] = [ri, ci] 中的 rici 分别表示指定的行和列(从 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:

输入: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
题解

直接模拟即可,最后统计数量。

时间复杂度:\(O(nm)\)

class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        vector<vector<int> > num(n);
        int count = 0;
        
        for(int i = 0; i < n; i++) num[i].resize(m);
        for(auto index : indices)
        {
            for(int i = 0; i < m; i++) num[index[0]][i]++;
            for(int i = 0; i < n; i++) num[i][index[1]]++;
        }
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(num[i][j] % 2) count++;
            }
        }
        
        return count;
    }
};

重构 2 行二进制矩阵

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

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

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

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

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

示例 1:

输入: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:

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

示例 3:

输入: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
题解

colsum[i] 只有三种情况:012,分别考虑。

colsum[i] = 2 时,明显上下两行第 i 列都有一个 1

colsum[i] = 1 时,如果能放第一行则放,否则放第二行;

colsum[i] = 0 时,不需要处理。

如果 upper + lower != colsum ,明显无解。

在处理过程中,如果已处理第一行总和为 UpSum,出现 upper < Upsum 那么无解,第二行一样。

时间复杂度:\(O(n)\)

class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        int n = colsum.size(), sum[2] = {0, 0}, cnt = 0;
        vector<vector<int> > ret(2);
        vector<vector<int> > zero;
        
        for(int i = 0; i < 2; i++) ret[i].resize(n);

        for(int i = 0; i < n; i++) 
        {
            cnt += colsum[i];
            if(colsum[i] == 2) 
            {
                ret[0][i] = ret[1][i] = 1;
                sum[0]++, sum[1]++;
            }
        }
        if(upper < sum[0] || lower < sum[1] || upper + lower != cnt) return zero;
        
        for(int i = 0; i < n; i++)
        {
            if(colsum[i] != 1) continue;
            if(sum[0] < upper) ret[0][i]++, sum[0]++;
            else if(sum[1] < lower) ret[1][i]++, sum[1]++;
            else return zero;
        }
        
        return ret;
    }
};

统计封闭岛屿的数目

有一个二维矩阵 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:

输入: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
题解

如果陆地连通块可以到达边界,那么它就不是封闭的。

直接搜索每个陆地连通块,看是否能接触地图边界。

时间复杂度:\(O(nm)\)

class Solution {
    
    const int dt[2][4] = {{0, 1, 0, -1}, {1, 0, -1, 0}};
    
public:
    int n, m, count;
    vector<vector<int> > flag;
    
    bool check(int x, int y) {
        return x == 0 || x == n - 1 || y == 0 || y == m - 1;
    }
    
    void bfs(vector<vector<int>>& grid, int sx, int sy) {
        queue<pair<int, int> > q;
        q.push(make_pair(sx, sy));
        flag[sx][sy] = 1;
        int kase = 0;
        if(check(sx, sy)) kase = 1;
        while(!q.empty())
        {
            auto h = q.front(); q.pop();
            for(int i = 0; i < 4; i++)
            {
                int x = h.first + dt[0][i];
                int y = h.second + dt[1][i];
                if(0 <= x && x < n && 0 <= y && y < m) 
                {
                    if(grid[x][y] || flag[x][y]) continue;
                    q.push(make_pair(x, y));
                    flag[x][y] = 1;
                    if(check(x, y)) kase = 1;
                }
            }
        }
        if(kase == 0) count++;
    }
    
    int closedIsland(vector<vector<int>>& grid) {
        count = 0, n = grid.size(), m = grid[0].size();
        
        flag.resize(n);
        for(int i = 0; i < n; i++) flag[i].resize(m);
        
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(!grid[i][j] && !flag[i][j]) bfs(grid, i, j);
            }
        }
        
        return count;
    }
};

得分最高的单词集合

你将会得到一份单词表 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] 只包含小写的英文字母。
题解

n 比较小,直接枚举每个单词是否选取,如果合法则更新答案,否则枚举下一种情况。

时间复杂度:\(O(mn2^n)\) ,m 为字符种类个数。

class Solution {
public:
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        int ret = 0, n = words.size(), sub[26];
        vector<int> num(score.size());
        vector<vector<int> > sum(n);
        vector<int> wordScore(n);
        
        for(int i = 0; i < n; i++) sum[i].resize(26);
        for(int i = 0; i < n; i++)
        {
            for(int c = 0; c < 26; c++)
            {
                for(int j = 0; j < words[i].size(); j++)
                {
                    if(words[i][j] - 'a' == c) 
                    {
                        sum[i][c]++;
                        wordScore[i] += score[c];
                    }
                }
            }
        }
        for(auto a : letters) num[a - 'a']++;
        for(int vis = 1; vis < (1 << n); vis++)
        {
            int ans = 0, flag = 1;
            memset(sub, 0, sizeof(sub));
            for(int i = 0; i < n && flag; i++)
            {
                if(((vis >> i) & 1))
                {
                    for(int j = 0; j < 26 && flag; j++)
                    {
                        if(num[j] - sub[j] < sum[i][j]) flag = 0;
                    }
                    if(!flag) break;
                    for(int j = 0; j < 26; j++) sub[j] += sum[i][j];
                    ans += wordScore[i];
                }
                if(flag) ret = max(ret, ans);
            }
        }
        
        return ret;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注