LeetCode周赛#224

传送门

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

思路

签到题，半分钟直接来。

代码

class Solution {
public:
    int countGoodRectangles(vector<vector<int>>& rectangles) {
        int ans = 0;
        int maxLen = -1;
        
        for(auto el : rectangles) {
            maxLen = max(maxLen, min(el[0], el[1]));
        }
        
        for(auto el : rectangles) {
            if(min(el[0], el[1]) == maxLen) {
                ans++;
            }
        }
        
        return ans;
    }
};

T2 同积元组

思路

很显然，对于一个四元组(a,b,c,d)，它能产生八种答案，题目很贴心的帮我们把nums做了升序排序(题干没说，自己悟的)，所以我们的计算仅针对标准(a<b<c<d)情况下的四元组。

根据题意，若存在(a,b,c,d)，使得a*b=c*d，答案计数就++。不难看出，这里的四元组其实是由两个同积的二元组(a,b)、(c,d)组成的。那么我们只需要统计所有同积的二元组，它们两两匹配所产生的二元组个数就是该乘积贡献的答案数。按这个思路计算所有乘积的贡献和就是最终答案。根据上一段的思路，最终答案要*8。

代码

class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        unordered_map<int, int> record;
        const int n = nums.size();
        int ans = 0;

        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                record[nums[i] * nums[j]]++;
            }
        }

        for(auto el : record) {
            ans += (el.second * (el.second - 1)) / 2;
        }

        return ans * 8;
    }
};

T3 重新排列后的最大子矩阵

思路

这种题首先肯定是不能模拟的。

用matirx[i][j]表示到(i,j)位置为止这一列最大的连续长度，然后sort一遍从高向低计算面积维护一个最大值就行了。

代码

class Solution {
public:
    static bool cmp(int x, int y) {
        return x > y;
    }

    int largestSubmatrix(vector<vector<int>>& matrix) {
        int ans = 0;
        int h = matrix.size();
        int w = matrix[0].size();

        for (int i = 1; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (matrix[i][j]) {
                    matrix[i][j] += matrix[i-1][j];
                }
            }
        }

        for (int i = 0; i < h; i++) {
            sort(matrix[i].begin(), matrix[i].end(), cmp);
            for (int j = 0; j < w; j++) {
                ans = max(ans, (j + 1) * matrix[i][j]);
            }
        }

        return ans;
    }
};