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

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

image.png

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

第一题,数学计算,先算行变换,再算列变换,时间复杂度O(n)即可

class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        vector<bool> vn(n, false);
        vector<bool> vm(m, false);
        for (int idx_n = 0; idx_n < indices.size(); idx_n++) {
            vn[indices[idx_n][0]] = !vn[indices[idx_n][0]];
        }
        for (int idx_m = 0; idx_m < indices.size(); idx_m++) {
            vm[indices[idx_m][1]] = !vm[indices[idx_m][1]];
            //cout << indices[idx_m][1] << " " << vm[indices[idx_m][1]] << endl;
        }
        int xn = 0, xm = 0;
        for (int idx_n = 0; idx_n < n; idx_n++) {
            if (vn[idx_n]) {
                xn ++;
            }
        }
        for (int idx_m = 0; idx_m < m; idx_m++) {
            if (vm[idx_m]) {
                xm ++;
            }
        }
        //cout << xn << " " << xm;
        return xn*m+xm*n-2*xn*xm;
    }
};

第2题,先把2行都是{1,1}的填上,然后再把{1,0}组合的填上,时间复杂度O(n)

class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        vector<vector<int>> res_new;
        vector<vector<int>> res(2, vector<int>(colsum.size()));
        for (int idx = 0; idx < colsum.size(); idx++) {
            if (colsum[idx] == 2) {
                res[0][idx] = 1;
                res[1][idx] = 1;
                upper--;
                lower--;
            }
        }
        if ((upper>=0) && (lower>=0)) {
            for (int idx = 0; idx < colsum.size(); idx++) {
                if (colsum[idx] == 1) {
                    if (upper > 0) {
                        res[0][idx] = 1;
                        upper--;
                    }
                    else {
                        if (lower > 0) {
                            res[1][idx] = 1;
                            lower--;
                        }
                        else {
                            return res_new;
                        }
                    }
                }
            }
        }
        if ((upper==0) &&(lower==0)) {
            return res;
        }
        return res_new;
    }
};

第3题,我用的并查集,用DFS/BFS也可以,优化一下应该可以更快一些
class Solution {
public:
int closedIsland(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size(), cnt = 0, islandnum = 0;

    for (int idx_n = 0; idx_n < n; idx_n++) {
        for (int idx_m = 0; idx_m < m; idx_m++) {
            if (grid[idx_n][idx_m] == 1) {
                grid[idx_n][idx_m] = -1;
            }
            else {
                grid[idx_n][idx_m] = cnt;
                cnt++;
            }
        }
    }
    /*
    for (int idx_n = 0; idx_n < n; idx_n++) {
        for (int idx_m = 0; idx_m < m; idx_m++) {
            cout << grid[idx_n][idx_m] << ", ";
        }
        cout<<endl;
    }
    cout<<endl;
    */
    bool flag = true;
    while (flag) {
        flag = false;
        for (int idx_n = 0; idx_n < n; idx_n++) {
            for (int idx_m = 0 ; idx_m < m; idx_m++) {
                if (grid[idx_n][idx_m] >= 0) {
                    if (idx_n-1 >= 0) {
                        if ((grid[idx_n-1][idx_m]>=0) && (grid[idx_n-1][idx_m]<grid[idx_n][idx_m])) {
                            grid[idx_n][idx_m] = grid[idx_n-1][idx_m];
                            flag = true;
                        }
                    }
                    if (idx_n+1 < n) {
                        if ((grid[idx_n+1][idx_m]>=0) && (grid[idx_n+1][idx_m]<grid[idx_n][idx_m])) {
                            grid[idx_n][idx_m] = grid[idx_n+1][idx_m];
                            flag = true;
                        }
                    }
                    if (idx_m-1 >= 0) {
                        if ((grid[idx_n][idx_m-1]>=0) && (grid[idx_n][idx_m-1]<grid[idx_n][idx_m])) {
                            grid[idx_n][idx_m] = grid[idx_n][idx_m-1];
                            flag = true;
                        }
                    }
                    if (idx_m+1 < m) {
                        if ((grid[idx_n][idx_m+1]>=0) && (grid[idx_n][idx_m+1]<grid[idx_n][idx_m])) {
                            grid[idx_n][idx_m] = grid[idx_n][idx_m+1];
                            flag = true;
                        }
                    }
                }
            }
        }
    }
    /*
    for (int idx_n = 0; idx_n < n; idx_n++) {
        for (int idx_m = 0; idx_m < m; idx_m++) {
            cout << grid[idx_n][idx_m] << ", ";
        }
        cout<<endl;
    }
    cout<<endl;
    */
    
    if (cnt > 0) {
        vector<bool> islandflag(cnt, false);
        for (int idx_n = 0; idx_n < n; idx_n++) {
            for (int idx_m = 0; idx_m < m; idx_m++) {
                if (grid[idx_n][idx_m] >= 0)
                {
                    islandflag[grid[idx_n][idx_m]] = true;
                }
            }
        }
        for (int islandidx = 0; islandidx < cnt; islandidx++) {
            if (islandflag[islandidx]) {
                flag = true;
                for (int idx_n = 0; idx_n < n; idx_n++) {
                    for (int idx_m = 0; idx_m < m; idx_m++) {
                        if (grid[idx_n][idx_m] == islandidx) {
                            if ((idx_n==0) || (idx_n==n-1) || (idx_m==0) ||(idx_m==m-1)) {
                                flag = false;
                            }
                        }
                    }
                }
                if (flag) {
                    islandnum ++;
                }
            }
        }
    }
    
    return islandnum;
}

};

第4题,想到的是用递归做回溯,前面时间花的有点多,但不知道回溯会不会超时

展开全部 22 讨论