周赛小结：leetcode第323场周赛

先放排名，确实还是很菜。。

第一题：

6257. 删除每行中的最大值

就是找出每一行的最大值，然后在每次找出的每一次挑选出的每一行的最大值中的最大值

由于数据量级太小，这题怎么做都行，我就每次排序翻转找最大值（图省事），没什么好说的，直接放代码，当然还有很多可以优化的空间：

c++
class Solution {
public:
    
    int deleteGreatestValue(vector<vector<int>>& g) {
        int ans = 0;
        int m = g[0].size();
        int n = g.size();
        for(int i = 0; i < m; i ++){
            int maxVal = 0;
            for(int i = 0; i < n; i ++){
                sort(g[i].begin(), g[i].end());
                reverse(g[i].begin(), g[i].end());
                maxVal = max(maxVal, g[i][0]);
                g[i][0] = 0;
            }
            ans += maxVal;
        }
        return ans;
    }
};

第二题：

6258. 数组中最长的方波

• 题目难度Medium

其实就是一个排序加哈希表，注意如果不想考虑开方的问题的话，可以倒着遍历

做的时候其实一下就想到了，但是中间觉得并查集也可以做，就耽误了一些时间。

做的时候有一些整数溢出情况没考虑到，下次要注意

c++
class Solution {
public:
    const int N = 1000010;
    
    int longestSquareStreak(vector<int>& nums) {
        int p[N], s[N];
        memset(p, 0, sizeof p);
        sort(nums.begin(), nums.end());
        reverse(nums.begin(), nums.end());
        int h[N];
        memset(h, 0, sizeof h);
        int ans = 0;
        
        for(int i : nums){
            h[i] = 1;
            if(i <= 1000){   // 做的时候就是这个地方没考虑，i * i 爆int了，换成longlong也不行。。wa了两次，干脆直接判断
                int t = i * i;
                if(t < N && h[t]){
                    h[i] += h[t];
                }
            } 
            ans = max(ans, h[i]);
        }
        if(ans == 1) return -1;
        else return ans;
    }
};

如果从小到大枚举的话不会出现爆int的问题，但是开方的话我个人觉得有些问题(开方函数不会写 😂)

第三题：

6259. 设计内存分配器

• 题目难度Medium

这个题真是写了改，改了写，浪费了不少精力和时间，最后的版本完成的过程实际上才四分钟。。。

由于数据量比较小，所以可以直接枚举遍历

下边是ac代码：

c++
const int N = 1010;

class Allocator {
public:

    int p[N], h[N];
    int n;
    
    Allocator(int m) {
        n = m;
        h[0] = 0;
        memset(p, 0, sizeof p);
    }
    
    int allocate(int size, int mID) {
        int idx = 0;
        memset(h, 0, sizeof h);
        for(int i = 1; i <= n; i ++){
            if(!p[i]){
                h[i] = h[i - 1] + 1;
            }
            if(h[i] == size){
                idx = i - size + 1;
                break;
            }
        }
        if(!idx) return -1;
        for(int i = 0; i < size; i ++)
            p[i + idx] = mID;
        return idx - 1;
    }
    
    int free(int mID) {
        int cnt = 0;
        for(int i = 1; i <= n; i ++)
            if(p[i] == mID){
                cnt ++;
                p[i] = 0;
            }
        return cnt;
    }
};

/**
 * Your Allocator object will be instantiated and called as such:
 * Allocator* obj = new Allocator(n);
 * int param_1 = obj->allocate(size,mID);
 * int param_2 = obj->free(mID);
 */

y总说mallocLab可以用平衡树维护，以后要试试。。

第四题：

6260. 矩阵查询可获得的最大分数

• 题目难度Hard

这个题没做出来。。

联通块问题，用并查集做结果出现了重复计数的问题，没有时间进行修改了，说明对并查集的经典模型还是不熟悉，下去重复背 😭

这题采用的是离线 + 并查集的做法

首先有几个问题要解决：

1. 什么是离线？
2. 为什么要进行离线？

总结：

• 手速太慢
• 思路不够活跃，缺乏新题训练
• 基础知识还不够，很多题型名词甚至没见过（离线等）

总的来说还是有所进步，加油~ 🥳