讨论/题目交流/🏆 第 162 场力扣周赛/
🏆 第 162 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 奇数值单元格的数目
4 分 - 重构 2 行二进制矩阵
5 分 - 统计封闭岛屿的数目
6 分 - 得分最高的单词集合

展开讨论

题1: 奇数值单元格的数目

思路1: 暴力枚举

对于每个indices[i]=[ri,ci]indices[i]=[r_i,c_i],按要求对第rir_i行加1,对第cic_i列加1,最后遍历统计奇数个数

复杂度:

时间复杂度: O(mn)O(m*n)

空间复杂度: O(mn)O(m*n)

思路2:单独统计每行每列

第一每个indices[i]=[ri,ci]indices[i]=[r_i,c_i],第rir_i行操操作了一次,第cic_i列操作了一次;

那么对于一个位置[i,j][i,j]来说,其位置的奇偶性取决于第ii行与第jj列的操作次数之和:和为奇数,则位置[i,j][i,j]处为奇数,否则为偶数

示例代码:

int oddCells(int n, int m, vector<vector<int>>& indices) {
    vector<int> t1(n,0);
    vector<int> t2(m,0);
    for(auto item:indices){
        int i = item[0];
        int j = item[1];
        t1[i]=(t1[i]+1)%2;	// 第i行操作次数加1
        t2[j]=(t2[j]+1)%2;	// 第j列操作次数加1
    }
    // 奇+奇=偶,奇+偶=奇
    int cnt1=accumulate(t1.begin(),t1.end(),0);
    int cnt2 = accumulate(t2.begin(),t2.end(),0);
    return cnt1*(m-cnt2)+(n-cnt1)*cnt2;
}

复杂度:

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

空间复杂度: O(n)O(n)

题2: 重构 2 行二进制矩阵

思路:贪心

当一行的结果确定后,另一行一定确定,那么只需确定第一行即可

colsum[i]colsum[i]为2时,第一行第个数re[0][i](第一行第i个数)第一行第个数re[0][i](第一行第i个数)肯定为1;当colsum[i]colsum[i]为0时,re[0][i]re[0][i]一定为0,对于colsum[i]colsum[i]为1时,贪心的取re[0][i]re[0][i]为1直到1总个数为upper

代码实现:

vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& col) {
    int n = col.size();
    vector<vector<int>> re(2,vector<int>(n,0));
    vector<int> t;
    int cnt=0;
    for(int i=0;i<n;i++){
        if(col[i]==2) upper--;		// 可以贪心选择1的个数
    }
    if(upper<0) return {};
    for(int i=0;i<n;i++){
        if(col[i]==2) {
            re[0][i]=1;		// col[i]=2,re[0][i]=1
        }
        else if(col[i]==1 && upper){	// 贪心取1
            re[0][i]=1;
            upper--;
        }
        re[1][i] = col[i]-re[0][i];		// re[1][i] = colsum[i]-re[0][i]
        if(re[1][i]) cnt++;		// 判断第2行的1的个数
    }
    if(cnt!=lower) return {};	// 如果第2行1的个数不为lower,则不存在
    return re;
}

复杂度:

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

空间复杂度: O(n)O(n)

题3: 统计封闭岛屿的数目

思路:BFS or DFS

BFS每个陆地(0)相连的所有陆地,如果没有遇到边界,则满足条件被水(1)包围

代码实现:

class Solution {
public:
    const vector<vector<int>> dir={{1,0},{-1,0},{0,1},{0,-1}};
    bool bfs(vector<vector<int>> &g,int i,int j){
        int m = g.size();
        int n = g[0].size();
        g[i][j]=1;
        deque<pair<int,int>> que;
        que.push_back({i,j});
        bool f = true;
        while(!que.empty()){
            int tm = que.size();
            while(tm--){
                auto p=que.front();
                int x = p.first;
                int y = p.second;
                for(int i=0;i<4;i++){
                    int dx = x+dir[i][0];
                    int dy = y+dir[i][1];
                    if(dx<0||dy<0||dx>=m||dy>=n){
                        f=false;	// 遇到边界
                        continue;
                    }
                    if(g[dx][dy]) continue;
                    g[dx][dy]=1;	// 已访问陆地
                    que.push_back({dx,dy});
                }
                que.pop_front();
            }
        }
        return f;
    }
    int closedIsland(vector<vector<int>>& g) {
        int m = g.size();
        if(m==0) return 0;
        int n = g[0].size();
        if(n==0) return 0;
        int cnt=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(g[i][j]) continue;
                if(bfs(g,i,j)) {
                    //cout<<i<<' '<<j<<endl;
                    cnt++;
                }
            }
        }
        return cnt;
    }
};

复杂度:

时间复杂度: O(n2)O(n^2)

空间复杂度: ?

题4: 得分最高的单词集合

思路:DFS

枚举单词的所有可能集合,判断可能性(是否超过了每个字母的使用次数),计算得分

代码实现:

class Solution {
public:
    void dfs(vector<string> &words,int s,int &re,vector<int>&cnts,vector<int> &scores,int &temp){
        bool f = true;
        for(int i=0;i<26;i++){
            if(cnts[i]<0){	// 超过每个字母的使用次数限制
                f=false;
                break;
            }
        }
        if(f) re=max(re,temp);	// 计算分数
        else return;
        int n=words.size();
        if(s>=n) return;
        for(int i=s;i<n;i++){
            for(auto item:words[i]){	// 更新每个字母的使用次数
                cnts[item-'a']--;
                temp+=scores[item-'a'];		// 计算分数
            }
            dfs(words,i+1,re,cnts,scores,temp);
            for(auto item:words[i]){	// 回溯
                cnts[item-'a']++;		// 回溯每个字符使用次数限制
                temp-=scores[item-'a'];		// 回溯分数
            }
        }
    }
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        vector<int> cnts(26,0);		// 每个字母的使用次数统计
        int s = 0;
        for(auto item:letters){
            cnts[item-'a']++;
        }
        int temp=0;
        int re = 0;
        dfs(words,s,re,cnts,score,temp);
        return re;
    }
};

总结:

  1. 按题意模拟即可
  2. 贪心
  3. BFS或者DFS
  4. DFS

题目不是很难,大部分是搜索问题。

展开全部 22 讨论