Weekly Contest 162

[lihe]

第一次参加Leetcode周赛，做出来两题，感觉排名前十的都是神仙。

5255. Cells with Odd Values in a Matrix

Easy

Given n and m which are the dimensions of a matrix initialized by zeros and given an array indices where indices[i] = [ri, ci]. For each pair of [ri, ci] you have to increment all cells in row ri and column ci by 1.

Return the number of cells with odd values in the matrix after applying the increment to all indices.

Example 1:

Input: n = 2, m = 3, indices = [[0,1],[1,1]]
Output: 6
Explanation: Initial matrix = [[0,0,0],[0,0,0]].
After applying first increment it becomes [[1,2,1],[0,1,0]].
The final matrix will be [[1,3,1],[1,3,1]] which contains 6 odd numbers.

Example 2:

Input: n = 2, m = 2, indices = [[1,1],[0,0]]
Output: 0
Explanation: Final matrix = [[2,2],[2,2]]. There is no odd number in the final matrix.

Constraints:

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

class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        if(indices.size() == 0)
            return 0;
        vector<vector<int>> girl(n, vector<int>(m, 0));
        for(int i = 0; i < indices.size(); i++){
            int row = indices[i][0];
            int col = indices[i][1];
            for(int j = 0; j < m; j++){
                girl[row][j]++;
            }
            for(int j = 0; j < n; j++){
                girl[j][col]++;
            }
        }
        int result = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(girl[i][j] % 2){
                    result++;
                }
            }
        }
        return result;
    }
};

5256. Reconstruct a 2-Row Binary Matrix

Medium

Given the following details of a matrix with n columns and 2 rows :

• The matrix is a binary matrix, which means each element in the matrix can be 0 or 1.
• The sum of elements of the 0-th(upper) row is given as upper.
• The sum of elements of the 1-st(lower) row is given as lower.
• The sum of elements in the i-th column(0-indexed) is colsum[i], where colsum is given as an integer array with length n.

Your task is to reconstruct the matrix with upper, lower and colsum.

Return it as a 2-D integer array.

If there are more than one valid solution, any of them will be accepted.

If no valid solution exists, return an empty 2-D array.

Example 1:

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]
Explanation: [[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.

Example 2:

Input: upper = 2, lower = 3, colsum = [2,2,1,1]
Output: []

Example 3:

Input: upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
Output: [[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

Constraints:

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

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

5257. Number of Closed Islands

Medium

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Example 1:

Input: 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]]
Output: 2
Explanation: 
Islands in gray are closed because they are completely surrounded by water (group of 1s).

Example 2:

Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1

Example 3:

Input: 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]]
Output: 2

Constraints:

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

class Solution{
public:
    void dfs(std::vector<std::vector<int>> &grid, int i, int j, int &val){
        if(i < 0 || i == grid.size()|| j < 0 || j == grid[0].size()){  // 边界条件
            val = 0;
            return;
        }
        if(grid[i][j] == 1)
            return;
        grid[i][j] = 1;  // 标记已访问过的方块
        dfs(grid, i + 1, j, val);
        dfs(grid, i - 1, j, val);
        dfs(grid, i, j - 1, val);
        dfs(grid, i, j + 1, val);
    }

    int closedIsland(std::vector<std::vector<int>> &grid){
        int result = 0;
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[i].size(); j++){
                if(grid[i][j] == 0){
                    int val = 1;
                    dfs(grid, i, j, val);
                    result += val;
                }
            }
        }
        return result;
    }
};

5258. Maximum Score Words Formed by Letters

Hard

Given a list of words, list of single letters (might be repeating) and score of every character.

Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times).

It is not necessary to use all characters in letters and each letter can only be used once. Score of letters 'a', 'b', 'c', ... ,'z' is given by score[0], score[1], ... , score[25] respectively.

Example 1:

Input: 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]
Output: 23
Explanation:
Score  a=1, c=9, d=5, g=3, o=2
Given letters, we can form the words "dad" (5+1+5) and "good" (3+2+2+5) with a score of 23.
Words "dad" and "dog" only get a score of 21.

Example 2:

Input: 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]
Output: 27
Explanation:
Score  a=4, b=4, c=4, x=5, z=10
Given letters, we can form the words "ax" (4+5), "bx" (4+5) and "cx" (4+5) with a score of 27.
Word "xxxz" only get a score of 25.

Example 3:

Input: 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]
Output: 0
Explanation:
Letter "e" can only be used once.

Constraints:

• 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] contains only lower case English letters.

class Solution{
public:
    vector<int> group(vector<string> &words, int bit){
        vector<int> g(26, 0);
        for(int i = 0; i < words.size(); i++){
            if(bit & (1 << i)){
                for(auto c : words[i]){
                    g[c - 'a']++;
                }
            }
        }
        return g;
    }

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

        int result = 0;
        for(int i = 0; i < (1 << words.size()); i++){
            auto g = group(words, i);
            int temp = 0;
            for(int j = 0; j < 26; j++){
                if(l[j] < g[j]){
                    temp = 0;
                    break;
                }
                else{
                    temp += g[j] * score[j];
                }
            }
            result = max(result, temp);
        }
        return result;
    }
};