Leetcode-第162场周赛

发表于 分类于 阅读次数：

1252. 奇数值单元格的数目

解法1：暴力模拟

暴力模拟，遍历将奇数找出来

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
class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        vector<vector<int>> v(n,vector<int>(m,0));
        int size=indices.size();
        for(int i=0;i<size;i++)
        {
            int x=indices[i][0],y=indices[i][1];
            for(int j=0;j<m;j++)
            {
                v[x][j]++;
            }
            for(int j=0;j<n;j++)
            {
                v[j][y]++;
            }
        }
        int res=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(v[i][j]%2)
                    res++;
            }
        }
        return res;
    }
};

1253. 重构 2 行二进制矩阵

解法1：模拟存放

1.判断upper+lower是否等于colsum总和

2.如果colsum[i]=2将结果数组对应该列都赋值为1

3.先将第一行按要求填充，剩下的填第二行

4.判断各行对应总和是否符合要求

5.返回对应结果

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
class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        int size=colsum.size();
        int temp=0;
        vector<vector<int>> res(2,vector<int>(size,0));
        int k=0;
        for(int i=0;i<size;i++)
        {
            temp+=colsum[i];
            if(colsum[i]==2)
            {
                res[0][i]=1;res[1][i]=1;
                k++;
            }
        }
        for(int i=0;i<size;i++)
        {
            if(colsum[i]==1)
            {
                if(k<upper)
                {    
                    res[0][i]=1;
                    k++;
                }
                else res[1][i]=1;
            }
        }
        vector<vector<int>> res1;
        int u=0,l=0;
        for(int i=0;i<size;i++)
        {
            u+=res[0][i];l+=res[1][i];
        }
        if(u!=upper||l!=lower)
            return res1;
        if(temp!=(upper+lower))
            return res1;
        
        else return res;
    }
};

1254. 统计封闭岛屿的数目

解法1：BFS

1.遍历不在边缘位置的0，从这一位置开始BFS。

2.BFS过程中将走过的点都标记下

3.BFS中若遇到触碰到边缘表示这个区域不是一个封闭岛屿，返回值置为0，否则为1

4.将封闭岛屿累计，得到返回值

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
    int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
    vector<vector<int>> grid_d;
    int n,m;
public:
    int closedIsland(vector<vector<int>>& grid) {
        n=grid.size(),m=grid[0].size();
        this->grid_d=grid;
        int res=0;
        vector<vector<bool>> used(n,vector<bool>(m,false));
        /*for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
                cout<<grid[i][j]<<" ";
            cout<<endl;
        }*/
        for(int i=1;i<n-1;i++)
        {
            for(int j=1;j<m-1;j++)
            {
                if(grid[i][j]!=1&&!used[i][j])
                {
                    used[i][j]=true;
                    res+=bfs(i,j,used);
                }
            }
        }
        return res;
    }
    int bfs(int i,int j,vector<vector<bool>>& used)
    {
        queue<pair<int,int>> que;
        que.push(make_pair(i,j));
        int ret=1;
        while(!que.empty())
        {
            int size=que.size();
            for(int k=0;k<size;k++)
            {
                pair<int,int> q=que.front();que.pop();
                int x=q.first,y=q.second;
               // cout<<x<<" "<<y<<endl;
                for(int d=0;d<4;d++)
                {
                    if(x+dir[d][0]>=0&&x+dir[d][0]<n&&y+dir[d][1]>=0&&y+dir[d][1]<m&&grid_d[x+dir[d][0]][y+dir[d][1]]!=1&&!used[x+dir[d][0]][y+dir[d][1]])
                    {
                        int newx=x+dir[d][0],newy=y+dir[d][1];
                        used[newx][newy]=true;
                        if((newx==0||newx==n-1||newy==0||newy==m-1)&&grid_d[newx][newy]==0)
                        {
                           ret=0;
                        }
                        que.push(make_pair(newx,newy));
                    }
                }
            }
        }
        return ret;
    }
};

1255. 得分最高的单词集合

解法1：子集&位压缩

思路：

1.由于words长度最高15，可枚举words的子集，即$2^{15}$，对于每个子集，统计一下这个子集每个字母用了多少次，是不是letters的子集，如果是计算得分，比较获得最高得分

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
44
45
46
47
class Solution {
public:
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        vector<int> let(26,0);
        for(char& c:letters)
        {
            let[c-'a']++;
        }
        int res=0;
        int n=words.size();
        for(int i=1;i<(1<<n);i++)
        {
            vector<int> g=group(words,i);
            int temp=0;
            for(int j=0;j<26;j++)
            {
                if(g[j]>let[j])
                {
                    temp=-1;
                    break;
                }
                else
                {
                    temp+=g[j]*score[j];
                }
            }
            
                res=max(res,temp);
        }
        return res;
    }
    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;
    }
};