Weekly Contest 162

Posted on | In , | |
Words count in article: 587 | Reading time ≈ 3

1252. Cells with Odd Values in a Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        int rem[n][m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++)
                rem[i][j] = 0;
        }
        for(auto& i: indices){
            for(int j=0; j<m; j++) rem[i[0]][j]++;
            for(int j=0; j<n; j++) rem[j][i[1]]++;
        }
        int c = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(rem[i][j] % 2 == 1){
                    c++;
                }
            }
        }
        return c;
    }
};

1253. Reconstruct a 2-Row Binary Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        vector<vector<int>> temp(2);
        for(int i=0; i<2; i++) temp[i].resize(colsum.size());
        for(int i=0; i<colsum.size(); i++){
            if(colsum[i] == 2){
                if(upper == 0 || lower == 0)
                {
                    vector<vector<int>> ret;
                    return ret;
                }
                temp[0][i] = 1;
                temp[1][i] = 1;
                upper--;
                lower--;
            }
        }
        for(int i=0; i<colsum.size(); i++){
            if(colsum[i] == 1){
                if(upper>0){
                    upper--;
                    temp[0][i] = 1;
                }
                else if(lower>0){
                    lower--;
                    temp[1][i] = 1;
                }
                else
                {
                    vector<vector<int>> ret;
                    return ret;
                }
            }
        }
        if(upper == 0 && lower == 0)
            return temp;
        else{
            vector<vector<int>> ret;
            return ret;
        }
    }
};

1254. Number of Closed Islands

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int fill(vector<vector<int>> & g, int i, int j){
        if(i<0 || j<0 || i>=g.size() || j>=g[i].size() || g[i][j] )
            return 0;
        return (g[i][j] = 1) + fill(g, i+1, j) + fill(g, i, j+1) + fill(g, i-1, j) + fill(g, i, j-1);
    }
    int closedIsland(vector<vector<int>>& g, int res = 0) {
        for(int i=0; i<g.size(); i++){
            for(int j=0; j<g[i].size(); j++){
                if(i * j == 0 || i == g.size()-1 || j == g[i].size()-1)
                    fill(g, i, j);
            }
        }
        for(int i=0; i<g.size(); i++){
            for(int j=0; j<g[i].size(); j++){
                res += fill(g, i, j)>0;
            }
        }
        return res;
    }
};

1255. Maximum Score Words Formed by Letters

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int dfs(vector<string> &ws, vector<int> &cnt, vector<int> &score, int i){
        if(i >= ws.size()) return 0;
        auto skipGain = dfs(ws, cnt, score, i+1), gain = 0, formed = 1;
        vector<int> cnt1(begin(cnt), end(cnt));
        for(auto ch: ws[i]){
            if(--cnt1[ch-'a'] < 0) formed = 0;
            gain += score[ch-'a'];
        }
        return max(skipGain, formed ? gain+dfs(ws, cnt1, score, i+1) : 0);
    }
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        vector<int> cnt(26);
        for(auto ch: letters) ++cnt[ch-'a'];
        return dfs(words, cnt, score, 0);
    }
};
Donate? comment?