力扣162周赛

思路：
第一题是个水题，直接模拟一下，然后遍历一下就行了。

class Solution {
public:int oddCells(int n, int m, vector<vector<int>>& indices) {int a[50][50]={0};for(int i=0;i<indices.size();i++){int x=indices[i][0];int y=indices[i][1];for(int i=0;i<m;i++){a[x][i]+=1;}for(int i=0;i<n;i++){a[i][y]+=1;}}int count=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(a[i][j]%2==1)count++;}}return count;}
};

思路：
分类讨论+贪心

当colsum=2，当且仅当第0行和第1行都是1，upper–，lower–
当colsum=0，当且仅当第0行和第1行都是0
当colsum=1，贪心两行中和较大的那个，这样能够让他们更快靠近答案。

class Solution {
public:vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {vector<vector<int>>ans;int len=colsum.size();for(int i=0;i<2;i++){vector<int>temp;for(int j=0;j<len;j++)temp.push_back(0);ans.push_back(temp);}for(int i=0;i<len;i++){if(colsum[i]==0){ans[0][i]=ans[1][i]=0;}else if(colsum[i]==2){ans[0][i]=ans[1][i]=1;--upper;--lower;}else {if(upper>lower){//贪心--upper;ans[0][i]=1;}else{--lower;ans[1][i]=1;}}if(upper<0||lower<0)return{};}if(upper==0&&lower==0)return ans;else return {};}
};

思路：
只要和最外层的0相连的岛屿绝对不是答案，因为不满足上下左右是1，所以我们可以先最最上面和最下面一行最左边和最右边（这些0相连的0绝对不是封闭岛屿）用bfs将他们修改成1，然后再遍历这个矩阵，找到为1的格子bfs将与他相连的联通块全部染色成1，遍历结束后就是答案。

class Solution {
public:int x,y;Solution(){}Solution(int a,int b){x=a;y=b;}void bfs(int x,int y,int row,int col,vector<vector<int> >& grid){int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};queue<Solution>st;st.push(Solution(x,y));while(!st.empty()){Solution now=st.front();st.pop();for(int i=0;i<4;i++){int fx=dir[i][0]+now.x;int fy=dir[i][1]+now.y;if(fx<0||fy<0||fx>=row||fy>=col)continue;if(grid[fx][fy]==0){st.push(Solution(fx,fy));grid[fx][fy]=1;}}}}int closedIsland(vector<vector<int>>& grid) {int ans=0;int row=grid.size();int col=grid[0].size();for(int i=0;i<row;i++){for(int j=0;j<col;j++){if((grid[i][j]==0)&&(i==0||i==row-1||j==0||j==col-1))bfs(i,j,grid.size(),grid[i].size(),grid);}}for(int i=0;i<grid.size();i++){for(int j=0;j<grid[i].size();j++){if(grid[i][j]==0&&i!=grid.size()-1&&i!=0&&j!=0&&j!=grid[i].size()-1){bfs(i,j,grid.size(),grid[i].size(),grid);ans++;}}}return ans;}
};

思路：
二进制枚举words全部子集，在满足letters个数的情况下统计最大值

class Solution {
public:int ans=0;int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {int cnt[26]={0};int app[26]={0};int w=words.size(),m=letters.size();for(int i=0;i<m;i++){//统计字典中出现个字母的个数++cnt[letters[i]-'a'];}for(int s=0;s<(1<<w);s++){//枚举字符串words所有子集memset(app,0,sizeof(app));for(int i=0;i<w;i++){if((s>>i)&1){for(auto c:words[i])++app[c-'a'];//子集中字母出现的个数}}bool flag=true;int sum=0;for(int i=0;i<26&&flag;i++){//更新答案if(app[i]>cnt[i])flag=false;sum+=score[i]*app[i];}if(flag&&sum>ans)ans=sum;}return ans;}
};

本次竞赛排名，2，4是赛后根据别人的思路写的，总之还蛮有意思的

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！