leetcode周赛224

ACM算法日常

发布于 2021-01-28 14:24:57

4240

发布于 2021-01-28 14:24:57

文章被收录于专栏：ACM算法日常

难度顺序：

A\le B\le C\le D

。

代码分为头文件和Solution主体部分，头文件在文末。

A.可以形成最大正方形的矩形数目

「提示：」

1 <= rectangles.length <= 1000
rectangles[i].length == 2
1 <= li, wi <= 10^9
li != wi

「思路：」遍历一遍记录最大值和最大值的个数即可。

时间复杂度：

O(n)

class Solution {
public:
    int countGoodRectangles(vector<vector<int>>& rectangles) {
        int mx = 0,cnt = 0;
        for(int i = 0;i < rectangles.size();i++) {
            int x = rectangles[i][0],y = rectangles[i][1];
            int mi = min(x,y);
            if(mx < mi) {
                mx = mi;
                cnt = 1;
            } else if(mx == mi) {
                cnt++;
            }
        }
        return cnt;
    }
};

B. 同积元组

「提示：」

1 <= nums.length <= 1000
1 <= nums[i] <= 10^4
nums 中的所有元素互不相同

「思路：」

一开始想复杂了，想着枚举两个数然后双指针去算另外一个数，但这样复杂度就是

n^3

了。

不过我们可以一开始算出两数乘积值的出现次数，用

unordered_map

存一下。然后我们再枚举两个数的乘积，注意到所有数都不同，所以假设你枚举了

a*b

，那么对应存在的与

a*b

值相同的

c*d

的个数为

mp[a*b]-1

，因此就可以算出对应4元组个数了。

因为数字之间可以交换，所以最后结果要乘以4。

时间复杂度：

O(n^2)

class Solution {
public:
    unordered_map<int,int>mp;
    int tupleSameProduct(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0;i < n;i++) {
            for(int j = i + 1;j < n;j++) {
                mp[nums[i] * nums[j]]++;
            }
        }
        int ans = 0;
        for(int i = 0;i < n;i++) {
            for(int j = i + 1;j < n;j++) {
                int now = nums[i] * nums[j];
                int num = mp[now] - 1;
                ans += num * 4;
            }
        }
        return ans;
    }
};

C. 重新排列后的最大子矩阵

「提示：」

m == matrix.length
n == matrix[i].length
1 <= m * n <= 10^5
matrix[i][j] 要么是 0 ，要么是 1 。

「思路」

直接枚举最后所得子矩阵的在矩阵中的起始行位置，那么每一列的贡献就是在这一行向上延伸1的长度，这就成了直方图寻找最大子矩阵了，假设不能重排就是单调栈求最大子矩阵。
因为可以重排列，所以将每一列的按照贡献排个序枚举起点，结果就是这一列的高度乘以后面列的个数：

H[j] * (len - j)

。

时间复杂度：

O(n*m*log(m))

class Solution {
public:
    int largestSubmatrix(vector<vector<int>>& matrix) {
        int n = matrix.size(),m = matrix[0].size();
        vector<vector<int> >h;
        h.resize(n);
        for(int i = 0;i < n;i++) h[i].resize(m);
        int ans = 0;
        for(int i = n - 1;i >= 0;i--) {
            for(int j = 0;j < m;j++) {
                if(matrix[i][j] == 1) {
                    h[i][j] = h[min(i + 1,n - 1)][j] + 1;
                }
            }
        }
        for(int i = 0;i < n;i++) { //起始位置
            vector<int>vec;
            for(int j = 0;j < m;j++) {
                if(h[i][j] != 0) {
                    vec.push_back(h[i][j]);
                }   
            }
            sort(vec.begin(),vec.end());
            int len = vec.size();
            int tmp = 0;
            for(int j = 0;j < len;j++) {
                tmp = max(tmp,vec[j] * (len - j));
            }
            ans = max(ans,tmp);
        }
        return ans;
    }
};

D.猫和老鼠 II

「提示：」

rows == grid.length
cols = grid[i].length
1 <= rows, cols <= 8
grid[i][j] 只包含字符 'C' ，'M' ，'F' ，'.' 和 '#' 。
grid 中只包含一个 'C' ，'M' 和 'F' 。
1 <= catJump, mouseJump <= 8

「思路」用了最朴素的记忆化搜索来写。

定义，代表老鼠的位置是

(x1,x2)

，猫的位置是

(x2,y2)

，

cur=0/1

代表当前是老鼠/猫，

cnt

代表老鼠进行过的轮数。

转移的过程就是在

bfs

里面同时记录老鼠和猫的状态，然后轮换先手，也就是博弈搜索。只要有一个子状态返回

false

，那么说明这个状态可以赢；或者能走到

也能赢；猫能走到

也赢。

题目的最大轮数是1000，但实际并不会到那么大，到了一定范围结果就已经固定了（估计不会超过格子数8*8），1000会T，所以我设置成了200。

时间复杂度：

O(rows^2*cols^2*2*200)

class Solution {
public:
    vector<string>mp;
    int n,m;
    int clen,mlen;
    int dirx[5] = {0,0,0,1,-1};
    int diry[5] = {0,1,-1,0,0};
    int dp[8][8][8][8][2][201];
    bool judge(pair<int,int>mou,pair<int,int>cat,int cur,int cnt) {
        int &ans = dp[mou.first][mou.second][cat.first][cat.second][cur][cnt];
        if(cnt >= 200) { //已经进行了至少1000次操作
            ans = (cur != 0);
            return ans;
        }
        if(ans != -1) {
            return ans;
        }
        if(cur == 0) { //老鼠
            if(!judge(mou,cat,cur ^ 1,cnt + 1)) return true;
            for(int i = 1;i < 5;i++) {
                int x = mou.first,y = mou.second;
                for(int j = 1;j <= mlen;j++) {
                    int dx = x + dirx[i] * j;
                    int dy = y + diry[i] * j;
                    if(dx >= n || dy >= m || dx < 0 || dy < 0) break;
                    if(mp[dx][dy] == '#') break;
                    if(dx == cat.first && dy == cat.second) continue;
                    if(mp[dx][dy] == 'F') return ans = true;
                    if(!judge({dx,dy},cat,cur ^ 1,cnt + 1)) {
                        return ans = true;
                    }
                }
            }
        } else {
            if(!judge(mou,cat,cur ^ 1,cnt)) return true;
            for(int i = 1;i < 5;i++) {
                int x = cat.first,y = cat.second;
                for(int j = 1;j <= clen;j++) {
                    int dx = x + dirx[i] * j;
                    int dy = y + diry[i] * j;
                    if(dx >= n || dy >= m || dx < 0 || dy < 0) break;
                    if(mp[dx][dy] == '#') break;
                    if(mp[dx][dy] == 'F') return ans = true;
                    if(dx == mou.first && dy == mou.second) return ans = true;
                    if(!judge(mou,{dx,dy},cur ^ 1,cnt)) {
                        return ans = true;
                    }
                }
            }
        }
        return ans = false;
    }
    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
        memset(dp,-1,sizeof(dp));
        mp = grid;n = grid.size();m = grid[0].size();
        clen = catJump;
        mlen = mouseJump;
        pair<int,int>cat,mou;
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                if(grid[i][j] == 'C') {
                    cat = {i,j};
                }
                if(grid[i][j] == 'M') {
                    mou = {i,j};
                }
            }
        }
        return judge(mou,cat,0,0);
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-01-17，如有侵权请联系 cloudcommunity@tencent.com 删除

grid