LeetCode周赛323，LeetCode官方的福利专场

关注、星标下方公众号，和你一起成长

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

今天是周一，我们照惯例来聊聊昨天的LeetCode周赛。

本次的周赛是第323场，是LeetCode官方的学习福利专场。除了前10名可以获得盲盒奖励之外，还有一些排名在幸运位置的同学可以获得LeetBook的奖励。并且，只要通过一题，就可以获得力扣的学习专属福利。属于是普天同庆大礼包了。

可能是为了照顾新入门的同学，本次赛题的质量一般，难度相对来说不算很大。

有老哥表示双周赛的时候还坐牢，没想到周赛的喜提rank1了。对于这样的菊苣，只能送上orz。

删除每行中的最大值

给你一个 m x n 大小的矩阵 grid ，由若干正整数组成。

执行下述操作，直到 grid 变为空矩阵：

从每一行删除值最大的元素。如果存在多个这样的值，删除其中任何一个。

将删除元素中的最大值与答案相加。

注意 每执行一次操作，矩阵中列的数据就会减 1 。

返回执行上述操作后的答案。

题解

题目看起来很花哨，但实际上是对每一行进行排序之后，选取每一列的最大值作为得分。最后返回得分之和即可。

class Solution {public:    int deleteGreatestValue(vector<vector>& grid) {        int n = grid.size();        for (int i = 0; i < n; i++) sort(grid[i].begin(), grid[i].end());                int ret = 0;        int m = grid[0].size();                for (int j = 0; j < m; j++) {            int tmp = 0;            for (int i = 0; i < n; i++) tmp = max(tmp, grid[i][j]);            ret += tmp;        }        return ret;    }};

数组中最长的方波

给你一个整数数组 nums 。如果 nums 的子序列满足下述条件，则认为该子序列是一个 方波 ：

子序列的长度至少为 2 ，并且

将子序列从小到大排序 之后 ，除第一个元素外，每个元素都是前一个元素的 平方 。

返回 nums 中 最长方波 的长度，如果不存在 方波 则返回 -1 。

子序列 也是一个数组，可以由另一个数组删除一些或不删除元素且不改变剩余元素的顺序得到。

题解

题目要求的是一个子序列，并且又说子序列要按照从小到大排序，那么我们可以秒想到，可以先对数组中元素进行排序，这样就可以保证从左到右取出来的子序列就是天然有序的。

其次我们要保证子序列中除了第一个元素之外的每个元素都是之前一个元素的平方，由于我们通过排序保证了我们遍历元素的顺序就是从小到大的，那么我们只需要判断当前元素的完全平方根是否存在在数组中即可。我们使用map来记录，map[x]表示以x结尾的子序列的最长方波，那么map[x] = map[sqrt(x)] + 1。这个式子写出来是不是很眼熟？

眼熟就对了，其实本质上用到了类似动态规划的思想。这里面的x和它平方根的关系，就是状态转移的关系。把握住了这一点，代码就很好写了。

class Solution {public:    int longestSquareStreak(vector& nums) {        sort(nums.begin(), nums.end());                map mp;        // 初始化，将所有元素都插入map中        for (auto x: nums) mp[x] = 1;                int ret = 1;        for (auto x: nums) {            // 计算x的平方根            int rt = int(sqrt(x));            // 要记得验算一下平方根是不是成立            if (rt * rt == x && mp.count(rt)) {                int cur = mp[rt] + 1;                mp[x] = cur;                // 更新答案                ret = max(ret, cur);            }        }        return ret > 1 ? ret : -1;    }};

设计内存分配器

给你一个整数 n ，表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。

请你设计一个具备以下功能的内存分配器：

分配 一块大小为 size 的连续空闲内存单元并赋 id mID 。

释放 给定 id mID 对应的所有内存单元。

注意：

多个块可以被分配到同一个 mID 。

你必须释放 mID 对应的所有内存单元，即便这些内存单元被分配在不同的块中。

实现 Allocator 类：

Allocator(int n) 使用一个大小为 n 的内存数组初始化 Allocator 对象。

int allocate(int size, int mID) 找出大小为 size 个连续空闲内存单元且位于 最左侧 的块，分配并赋 id mID 。返回块的第一个下标。如果不存在这样的块，返回 -1 。

int free(int mID) 释放 id mID 对应的所有内存单元。返回释放的内存单元数目。

题解

这题光看题面是比较困难的，是一个比较复杂的区间维护问题。但我们注意到本题的数据范围很小，最大只有1000。也就是说可以承受 的复杂度而不会超时，那么本题的难度一下子就降低了，纯暴力就可以搞定。

对于allocate和free方法我们都只要做到能够 时间内搞定即可。比较容易想到，我们可以使用一个数组维护每个内存单元所属的mID。

对于allocate我们要找到满足大小的连续内存的位置，这里我们可以使用一个累计变量。当满足条件时它一直累计，不满足条件时清零重新累计。这样我们就可以在 的时间内找到满足条件的位置，找到之后，我们再用一次循环去修改这个部分内存所对应的mID即可。这里虽然我们用到了两重循环，但是遍历的元素最多只有2n个，所以依然是 的复杂度。

搞定了allocate之后free就更简单了，那么在free的时候，只需要遍历一下所有的内存单元，然后释放掉对应mID的即可。一重循环搞定，复杂度 。

class Allocator {public:        vector al;    int cap;        Allocator(int n) {        al.resize(n);        cap = n;    }        int allocate(int size, int mID) {        int tmp = 0;        for (int i = 0; i < cap; i++) {            if (al[i] == 0) tmp++;            else tmp = 0;            if (tmp == size) {                for (int j = i-size+1; j <= i; j++) al[j] = mID;                return i-size+1;            }        }        return -1;    }        int free(int mID) {        int ret = 0;        for (int i = 0; i < cap; i++) {            if (al[i] == mID) {                ret++;                al[i] = 0;            }        }        return ret;    }};/** * 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); */

大家感兴趣也可以想想如果不用暴力的方法，需要用到数据结构来进行维护，难度也会上一个台阶。

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

给你一个大小为 m x n 的整数矩阵 grid 和一个大小为 k 的数组 queries 。

找出一个大小为 k 的数组 answer ，且满足对于每个整数 queres[i] ，你从矩阵 左上角 单元格开始，重复以下过程：

如果 queries[i] 严格 大于你当前所处位置单元格，如果该单元格是第一次访问，则获得 1 分，并且你可以移动到所有 4 个方向（上、下、左、右）上任一 相邻 单元格。

否则，你不能获得任何分，并且结束这一过程。

在过程结束后，answer[i] 是你可以获得的最大分数。注意，对于每个查询，你可以访问同一个单元格 多次 。

返回结果数组 answer 。

题解

如果只有一个query，很简单，我们直接从左上角遍历所有连通且小于query的格子的数量。

但本题当中有最多1e4个query，如果我们单独处理显然会超时。所以必须要合并处理，那怎么合并处理呢？

我们可以反向思考，从求每一个query对应的连通块的面积转向求能够覆盖每一个格子所需要的最小代价。之后我们只需要计算每一个query能够满足多少格子即可。query越大能够覆盖的格子也就越多，这两者是递增的，我们没必要一一统计计算。可以一次性全部统计出之后，采用二分的方法来查找。

我们一步一步来看，首先统计出从左上角开始到达每一个格子路径中每个点最大值的最小值，这个值就是覆盖该点的代价。

比如上图当中从左上角到右下角的通路有好几条，一条经过的最大值是7一条是5，显然5更小。我们可以使用spfa算法搞定，代码类似于bfs。

我们使用数组dis记录每一个点到左上角经过路径中最大格子的最小值，由于grid是二维的，所以我们需要将二维坐标转化成一维坐标。转化的方式也很简单ni = i * m + j。

求出了dis数组之后，我们可以使用一个map来将dis中的值进行合并，并计算前缀和。之后在遍历query数组，利用map进行二分查找，找到对应的前缀和即是答案，更多细节查看代码。

class Solution {public:    vector maxPoints(vector<vector>& grid, vector& queries) {        int fx[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};                int n = grid.size();        int m = grid[0].size();                // dis存储每个点到左上角路径中经过最大点的最小值        vector dis(n * m, 0x3f3f3f3f);                typedef pair pii;        queue que;        que.push(make_pair(0, 0));                dis[0] = grid[0][0];        // spfa进行松弛        while (!que.empty()) {            auto u = que.front(); que.pop();            int x = u.first, y = u.second;            int iu = x * m + y;            for (int i = 0; i < 4; i++) {                int ux = x + fx[i][0];                int uy = y + fx[i][1];                                if (ux < 0 || ux >= n || uy < 0 || uy >= m) continue;                int idx = ux * m + uy;                if (dis[idx] > max(dis[iu], grid[ux][uy])) {                    dis[idx] = max(dis[iu], grid[ux][uy]);                    que.push(make_pair(ux, uy));                }            }        }                // 存储前缀和        map cnt;                for (int i = 0; i < m * n; i++) {            cnt[dis[i]]++;        }                int tmp = 0;        // 计算前缀和        for (auto it: cnt) {            int k = it.first, v = it.second;            cnt[k] += tmp;            tmp = cnt[k];        }                vector ret;        for (auto q: queries) {            // 二分查找            auto it = cnt.lower_bound(q);            if (it == cnt.begin()) ret.push_back(0);            else {                ret.push_back((--it)->second);            }        }        return ret;    }};

我翻了一下评论区里的题解，不少大佬使用并查集进行解决。可惜他们都言简意赅，我也没能完全搞懂。有兴趣的同学也可以往这个角度思考思考。

喜欢本文的话不要忘记三连~