LeetCode Contest 323

2500. Delete Greatest Value in Each Row

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

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

从每一行删除值最大的元素。如果存在多个这样的值，删除其中任何一个。
将删除元素中的最大值与答案相加。
注意 每执行一次操作，矩阵中列的数据就会减 1 。

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

测试样例：
输入：grid = [[1,2,4],[3,3,1]]
输出：8

解释：上图展示在每一步中需要移除的值。

• 在第一步操作中，从第一行删除 4 ，从第二行删除 3（注意，有两个单元格中的值为 3 ，我们以>> 删除任一）。在答案上加 4 。
• 在第二步操作中，从第一行删除 2 ，从第二行删除 3 。在答案上加 3 。
• 在第三步操作中，从第一行删除 1 ，从第二行删除 1 。在答案上加 1 。
  最终，答案 = 4 + 3 + 1 = 8 。

解答: 操作顺序是每一行删除值最大的元素，所以可以想到对每一行进行排序。第二步是删除元素中最大的值，并于答案相加，则可以对每一列求最大值。

class Solution {
    public int deleteGreatestValue(int[][] grid) {
        for (int i = 0; i < grid.length; ++i) {
            Arrays.sort(grid[i]);
        }
        int res = 0;
        for (int i = grid[0].length - 1; i >= 0; --i) {
            int add = 0;
            for (int j = 0; j < grid.length; ++j) {
                add = Math.max(add, grid[j][i]);
            }
            res += add;
        }
        return res;
    }
}

2501. Longest Square Streak in an Array

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

• 子序列的长度至少为 2 ，并且
• 将子序列从小到大排序 之后 ，除第一个元素外，每个元素都是前一个元素的 平方 。

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

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

测试样例：
输入：nums = [4,3,6,16,8,2]
输出：3

解释：选出子序列 [4,16,2] 。排序后，得到 [2,4,16] 。

• 4 = 2 * 2.
• 16 = 4 * 4.
  因此，[4,16,2] 是一个方波.
  可以证明长度为 4 的子序列都不是方波。

解答： 这道题目主要考点是计算最长子序列。首先我们需要把所有出现的数字放在一个HashMap中。HashMap可以提高，判断当前元素的平方元素是否出现。

随后可以简单把HashMap对应的value，记录当前数字为开头，所能到达的最长长度。使用带记忆的DFS完成计算。

class Solution {
    public int longestSquareStreak(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i : nums) {
            map.put(i, -1);
        }
        int res = 0;
        for (int i : nums) {
            res = Math.max(res, find(map, i));
        }
        return res <= 1 ? -1 : res;
    }

    private int find(HashMap<Integer, Integer> map, long input) {
        if (input >= Integer.MAX_VALUE) {
            return 0;
        }
        int n = (int) input;
        if (!map.containsKey(n)) {
            return 0;
        } else if (map.get(n) == -1) {
            map.put(n, find(map, input * input) + 1);
        }
        return map.get(n);
    }
}

2502. Design Memory Allocator

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

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

1. 分配 一块大小为 size 的连续空闲内存单元并赋 id mID 。
2. 释放 给定 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 对应的所有内存单元。返回释放的内存单元数目。

测试样例：
输入: ["Allocator", "allocate", "allocate", "allocate", "free", "allocate", > "allocate", "allocate", "free", "allocate", "free"]
[[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], > [7]]

输出: [null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]

解答： 这道题目有个很大的提示，1 <= n, size, mID <= 1000，最多调用1000次函数。所以可以很简单的利用for循环完成计算。比较好的做法可以借鉴： 利用区间合并方法

class Allocator {
    private int[] mem;

    public Allocator(int n) {
        mem = new int[n];
    }

    public int allocate(int size, int mID) {
        int st = 0, ed = 0;
        boolean isSuccess = false;
        while (ed < mem.length) {
            if (mem[ed] != 0) {
                st = ed + 1;
            } else if (ed - st + 1 == size) {
                for (int i = st; i <= ed; ++i) {
                    mem[i] = mID;
                }
                return st;
            }
            ++ed;
        }
        return isSuccess ? st : -1;
    }

    public int free(int mID) {
        int c = 0;
        for (int i = 0; i < mem.length; ++i) {
            if (mem[i] == mID) {
                ++c;
                mem[i] = 0;
            }
        }
        return c;
    }
}

2503. Maximum Number of Points From Grid Queries

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

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

• 如果 queries[i] 严格 大于你当前所处位置单元格，如果该单元格是第一次访问，则获得 1 分，> 并且你可以移动到所有 4 个方向（上、下、左、右）上任一 相邻 单元格。
• 否则，你不能获得任何分，并且结束这一过程。
  在过程结束后，answer[i] 是你可以获得的最大分数。注意，对于每个查询，你可以访问同一个单元> 格 多次 。

返回结果数组 answer 。

测试样例：
输入：grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]

输出：[5,8,1]

解释：上图展示了每个查询中访问并获得分数的单元格。

解答：这道题目测试范围比较大。如果每次query都进行BFS搜索会导致TLE。所以比较好的处理方法是利用表中已经存在的数字，将其拍平存在一个TreeMap中（方便之后的搜索）。然后利用一次BFS，计算TreeMap中的每个数可以达到的位置。最后使用前缀和，计算对应数字可以覆盖的范围。

对于每次query，我们可以简单的查找它在TreeMap中能够覆盖的元素，然后通过前缀和的列表查表就能完成得出结果。

class Solution {
    private static final int[] moves = {1,0,-1,0,1};

    public int[] maxPoints(int[][] grid, int[] queries) {
        TreeMap<Integer, Integer> map = sortNum(grid);
        int[] tree = buildTree(grid, map);

        int[] res = new int[queries.length];
        for (int i = 0; i < res.length; ++i) {
            Map.Entry<Integer, Integer> entry = map.lowerEntry(queries[i]);
            if (entry != null) {
                res[i] = tree[entry.getValue()];
            }
        }
        return res;
    }

    private TreeMap<Integer, Integer> sortNum(int[][] grid) {
        Set<Integer> set = new HashSet<>();
        List<Integer> cand = new ArrayList<>();
        for (int[] row : grid) {
            for (int n : row) {
                if (!set.contains(n)) {
                    set.add(n);
                    cand.add(n);
                }
            }
        }
        Collections.sort(cand);
        TreeMap<Integer, Integer> res = new TreeMap<>();
        for (int i = 0; i < cand.size(); ++i) {
            res.put(cand.get(i), i);
        }
        return res;
    }

    private int[] buildTree(int[][] grid, TreeMap<Integer, Integer> map) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        boolean[][] isAdd = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0}); dp[0][0] = grid[0][0];
        isAdd[0][0] = true;

        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            if (tmp == null) {
                queue.add(null);
            } else {
                isAdd[tmp[0]][tmp[1]] = false;
                for (int i = 0; i < 4; ++i) {
                    int xt = tmp[0] + moves[i], yt = tmp[1] + moves[i + 1];
                    if (xt >= 0 && xt < m && yt >= 0 && yt < n
                            && (dp[xt][yt] == 0 || dp[xt][yt] > Math.max(grid[xt][yt], dp[tmp[0]][tmp[1]]))) {
                        dp[xt][yt] = Math.max(grid[xt][yt], dp[tmp[0]][tmp[1]]);
                        if (!isAdd[xt][yt]) {
                            isAdd[xt][yt] = true;
                            queue.add(new int[]{xt, yt});
                        }
                    }
                }
            }
        }

        int[] tree = new int[map.size()];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                tree[map.get(dp[i][j])] += 1;
            }
        }
        int sum = 0;
        for (int i = 0; i < tree.length; ++i) {
            sum += tree[i];
            tree[i] = sum;
        }
        return tree;
    }
}