周赛回

1. 删除每行中的最大值

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

描述比较绕，其实就是做两件事：

1. 把每行元素从大到小排序
2. 由右至左，找到每一列的最大元素并累加

最后返回累加值即可。

代码

class Solution {
public:
    int deleteGreatestValue(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), ans = 0;
        for (auto& row : grid) sort(row.begin(), row.end());
        for (int i = n - 1; i >= 0; --i) {
            int maxNum = INT_MIN;
            for (int j = 0; j < m; ++j) {
                maxNum = maxNum > grid[j][i] ? maxNum : grid[j][i];
            }
            ans += maxNum;
        }
        return ans;
    }
};

2. 数组中最长的方波

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

1. 既然子序列可以排序，那么原数组顺序其实无所谓。且符合条件的子序列显然不能有重复值，那么直接把原数组去重+排序再操作即可。用有序set就可以轻易做到。
2. 当满足条件的子序列的首元素确定，后面的元素也应当是确定的（不断平方），那么可以枚举首元素，然后二分法搜索后续元素，后续元素不存在时即达到当前首元素能构成的最大长度。
3. 已经作为一个可能子序列内的元素的元素，不再可能作为另一个子序列的首元素（否则长度一定更短），所以用一个数组visited保存各个位置元素的访问情况。

代码

class Solution {
public:
    int longestSquareStreak(vector<int>& nums) {
        set<int> s(nums.begin(), nums.end());
        nums = vector<int>(s.begin(), s.end());
        int n = nums.size(), ans = 0;
        unordered_set<int> visited;
        int i = 0, cnt = 1;
        long long cur = nums[0];
        while (i < n) {
            if (visited.count(cur) != 0) {
                cur = nums[i++];
            }
            else {
                visited.emplace(cur);
                if (binary_search(nums.begin(), nums.end(), cur * cur)) {
                    cur *= cur;
                    cnt++;
                    ans = ans > cnt ? ans : cnt;
                }
                else {
                    cur = nums[i++];
                    cnt = 1;
                }
            }
        }
        return ans == 0 ? -1 : ans;
    }
};

3. 设计内存分配器

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

如果存储每个位置的分配情况，显然很容易超时。那么，用一个两层的数组 memos ，保存内存中每一个被占用的块的首尾下标，且要按每个块的起始下标进行排序。再用一个嵌套两层数组的map ids ，保存mID与块之间的对应关系。

分配新块时，先假定可用的起始下标 start 为0，然后判断下一个已分配块的起始下标到 start 的距离是否大于等于 size 。最后计算整个内存空间末尾到 start 的距离是否足够（即要分配的块起始下标在所有已分配块之后）。将新的块插入到 memos ，然后排一次序，再将映射添加到 ids 。

清空 mID 对应的块时，要遍历其对应的每一个块，在 memos 中查找并删除，且累加长度。最后把 mID 从 ids 中删除，再返回累加的长度。

写这题时细节没处理好，否则十分钟就应该完成的。

代码

class Allocator {
private:
    map<int, vector<vector<int>>> ids;
    vector<vector<int>> memos;
    int maxSize;
public:
    Allocator(int n) {
        maxSize = n;
    }

    int allocate(int size, int mID) {
        int start = 0;
        for (auto& block : memos) {
            if (block[0] - start >= size) break;
            else start = block[1];
        }
        if (maxSize - start < size) return -1;
        else {
            vector<int> newBlock = {start, start + size};
            ids[mID].push_back(newBlock);
            memos.push_back(newBlock);
            sort(memos.begin(), memos.end(), [&](vector<int> block1, vector<int> block2){
                return block1[0] < block2[0];
            });
            return start;
        }
    }

    int free(int mID) {
        if (ids.find(mID) == ids.end()) return 0;
        int size = 0;
        for (auto& block : ids[mID]) {
            size += block[1] - block[0];
            memos.erase(find(memos.begin(), memos.end(), block));
        }
        ids.erase(mID);
        return size;
    }
};