LeetCode Contest 357

6925. Faulty Keyboard

你的笔记本键盘存在故障，每当你在上面输入字符 'i' 时，它会反转你所写的字符串。而输入其他字符则可以正常工作。

给你一个下标从 0 开始的字符串 s ，请你用故障键盘依次输入每个字符。

返回最终笔记本屏幕上输出的字符串。

测试样例：

输入：s = "string"

输出："rtsng"

解释：

• 输入第 1 个字符后，屏幕上的文本是："s" 。
• 输入第 2 个字符后，屏幕上的文本是："st" 。
• 输入第 3 个字符后，屏幕上的文本是："str" 。
• 因为第 4 个字符是 'i' ，屏幕上的文本被反转，变成 "rts" 。
• 输入第 5 个字符后，屏幕上的文本是："rtsn" 。
• 输入第 6 个字符后，屏幕上的文本是： "rtsng" 。

因此，返回 "rtsng" 。

解答：按照题意暴力计算。

class Solution {
    public String finalString(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == 'i') {
                sb.reverse();
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

6953. Check if it is Possible to Split Array

给你一个长度为 n 的数组 nums 和一个整数 m 。请你判断能否执行一系列操作，将数组拆分成 n 个 非空 数组。

在每一步操作中，你可以选择一个 长度至少为 2 的现有数组（之前步骤的结果） 并将其拆分成 2 个子数组，而得到的 每个 子数组，至少 需要满足以下条件之一：

• 子数组的长度为 1 ，或者
• 子数组元素之和 大于或等于 m 。

如果你可以将给定数组拆分成 n 个满足要求的数组，返回 true ；否则，返回 false 。

注意：子数组是数组中的一个连续非空元素序列。

测试样例：

输入：nums = [2, 2, 1], m = 4

输出：true

解释：

• 第 1 步，将数组 nums 拆分成 [2, 2] 和 [1] 。
• 第 2 步，将数组 [2, 2] 拆分成 [2] 和 [2] 。

因此，答案为 true 。

解答：这道题目有点脑筋急转弯，如果数组中有连续2个数字之和大于m，就一定可以完成分裂。但是需要注意一个条件：子数组的长度为 1。所以nums.size <= 2的时候也一定可以分裂。WA麻了。

class Solution {
    public boolean canSplitArray(List<Integer> nums, int m) {
        if (nums.size() <= 2) {
            return true;
        }
        int pre = Integer.MIN_VALUE;
        for (int n : nums) {
            if (n + pre >= m) {
                return true;
            }
            pre = n;
        }
        return false;
    }
}

6951. Find the Safest Path in a Grid

给你一个下标从 0 开始、大小为 n x n 的二维矩阵 grid ，其中 (r, c) 表示：

• 如果 grid[r][c] = 1 ，则表示一个存在小偷的单元格
• 如果 grid[r][c] = 0 ，则表示一个空单元格

你最开始位于单元格 (0, 0) 。在一步移动中，你可以移动到矩阵中的任一相邻单元格，包括存在小偷的单元格。

矩阵中路径的 安全系数 定义为：从路径中任一单元格到矩阵中任一小偷所在单元格的 最小 曼哈顿距离。

返回所有通向单元格 (n - 1, n - 1) 的路径中的 最大安全系数 。

单元格 (r, c) 的某个 相邻 单元格，是指在矩阵中存在的 (r, c + 1)、(r, c - 1)、(r + 1, c) 和 (r - 1, c) 之一。

两个单元格 (a, b) 和 (x, y) 之间的 曼哈顿距离 等于 | a - x | + | b - y | ，其中 |val| 表示 val 的绝对值。

测试样例

输入：grid = [[1,0,0],[0,0,0],[0,0,1]]

输出：0

解释：
从 (0, 0) 到 (n - 1, n - 1) 的每条路径都经过存在小偷的单元格 (0, 0) 和 (n - 1, n - 1) 。

解答：其实感觉这道题目就不好做了。。。这道题目需要逆向思维。我们可以分析一下每个点到最近的小偷曼哈顿距离，并且做出一个列表。然后我们距离由远及近，利用并查集查看起始和结束点是不是可达。

class Solution {
    class DSU{
        int[] parent;

        public DSU(int N) {
            parent = new int[N];
            for (int i = 0; i < N; ++i) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }

        public void union(int x, int y) {
            parent[find(x)] = find(y);
        }
    }

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

    public int maximumSafenessFactor(List<List<Integer>> grid) {
        int[][] matrix = turnArrayList(grid);
        int n = matrix.length;
        if (matrix.length == 1 && matrix[0].length == 1 && matrix[0][0] == 1) {
            return 0;
        }
        LinkedList<int[]> list = new LinkedList<>();
        List<int[]> last = new ArrayList<>();
        boolean[][] isMatched = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 1) {
                    list.addFirst(new int[]{i, j});
                    last.add(new int[]{i, j});
                    isMatched[i][j] = true;
                }
            }
        }

        int maxDis = 0;
        while (!last.isEmpty()) {
            ++maxDis;
            list.addFirst(null);
            List<int[]> nextLast = new ArrayList<>();
            for (int[] l : last) {
                for (int i = 0; i < 4; ++i) {
                    int xt = l[0] + moves[i], yt = l[1] + moves[i + 1];
                    if (xt >= 0 && xt < n && yt >= 0 && yt < n && !isMatched[xt][yt]) {
                        isMatched[xt][yt] = true;
                        list.addFirst(new int[]{xt, yt});
                        nextLast.add(new int[]{xt, yt});
                    }
                }
            }
            last = nextLast;
        }

        DSU uf = new DSU(n * n);
        Iterator<int[]> it = list.iterator();
        isMatched = new boolean[n][n];

        for (int i = maxDis; i >= 0; --i) {
            while (it.hasNext()) {
                int[] tmp = it.next();
                if (tmp == null) {
                    break;
                } else {
                    isMatched[tmp[0]][tmp[1]] = true;
                    for (int mv = 0; mv < 4; ++mv) {
                        int xt = tmp[0] + moves[mv], yt = tmp[1] + moves[mv + 1];
                        if (xt >= 0 && xt < n && yt >= 0 && yt < n && isMatched[xt][yt]) {
                            uf.union(xt * n + yt, tmp[0] * n + tmp[1]);
                        }
                    }
                }
            }
            if (uf.find(0) == uf.find((n - 1) * n + n - 1)) {
                return i;
            }
        }
        return 0;
    }

    private int[][] turnArrayList(List<List<Integer>> grid) {
        int n = grid.size(), offset = 0;
        int[][] res = new int[n][n];
        for (List<Integer> m : grid) {
            int to = 0;
            for (Integer num : m) {
                res[offset][to++] = num;
            }
            ++offset;
        }
        return res;
    }
}

6932. Maximum Elegance of a K-Length Subsequence

给你一个长度为 n 的二维整数数组 items 和一个整数 k 。

items[i] = [profiti, categoryi]，其中 profiti 和 categoryi 分别表示第 i 个项目的利润和类别。

现定义 items 的 子序列 的 优雅度 可以用 total_profit + distinct_categories2 计算，其中 total_profit 是子序列中所有项目的利润总和，distinct_categories 是所选子序列所含的所有类别中不同类别的数量。

你的任务是从 items 所有长度为 k 的子序列中，找出 最大优雅度 。

用整数形式表示并返回 items 中所有长度恰好为 k 的子序列的最大优雅度。

注意：数组的子序列是经由原数组删除一些元素（可能不删除）而产生的新数组，且删除不改变其余元素相对顺序。

测试样例

输入：items = [[3,2],[5,1],[10,1]], k = 2

输出：17

解释：在这个例子中，我们需要选出长度为 2 的子序列。其中一种方案是 items[0] = [3,2] 和 items[2] = [10,1] 。子序列的总利润为 3 + 10 = 13 ，子序列包含 2 种不同类别 [2,1] 。因此，优雅度为 13 + 22 = 17 ，可以证明 17 是可以获得的最大优雅度。

解答：我们首先利用排序，将profit从大到小遍历，然后开始遍历整个数组。需要注意的地方是，如果加入的数字已经达到k个，那么就需要尽量增加新的数字可能（已经按照profit排序，所以此时profit一定是最优的）。

class Solution {
    private HashMap<Integer, PriorityQueue<Integer>> queue;
    private TreeMap<Integer, HashMap<Integer, Integer>> scoreSort;

    public long findMaximumElegance(int[][] items, int k) {
        Arrays.sort(items, (a, b) -> (b[0] - a[0]));

        queue = new HashMap<>();
        scoreSort = new TreeMap<>();

        long res = 0, profitSum = 0;
        for (int[] item : items) {
            int cat = item[1], pro = item[0];
            if (k > 0) {
                profitSum += pro;
                addQueue(cat, pro);
                addScoreWithCondition(cat, pro);
                --k;
            } else if (!queue.containsKey(cat) && !scoreSort.isEmpty()) {
                int lower = scoreSort.firstKey(), group = getRandomGroup(lower);
                removeScore(group, queue.get(group).poll());
                if (queue.get(group).size() == 1) {
                    removeScore(group, queue.get(group).peek());
                }
                addQueue(cat, pro);
                addScoreWithCondition(cat, pro);
                profitSum -= lower;
                profitSum += pro;
            }

            long distinct = queue.size();
            res = Math.max(res, distinct * distinct + profitSum);
        }
        return res;
    }

    private void addQueue(int category, int profit) {
        if (!queue.containsKey(category)) {
            queue.put(category, new PriorityQueue<>());
        }
        queue.get(category).add(profit);
    }

    private void addScoreWithCondition(int group, int score) {
        if (queue.get(group).size() == 2) {
            for (int s : queue.get(group)) {
                addScore(group, s);
            }
        } else if (queue.get(group).size() > 2) {
            addScore(group, score);
        }
    }

    private void addScore(int group, int score) {
        if (!scoreSort.containsKey(score)) {
            scoreSort.put(score, new HashMap<>());
        }
        HashMap<Integer, Integer> map = scoreSort.get(score);
        map.put(group, map.getOrDefault(group, 0) + 1);
    }

    private int getRandomGroup(int group) {
        for (int n : scoreSort.get(group).keySet()) {
            return n;
        }
        return -1;
    }

    private void removeScore(int group, int score) {
        HashMap<Integer, Integer> tmp = scoreSort.get(score);
        int old = tmp.get(group);
        if (old == 1) {
            tmp.remove(group);
        } else {
            tmp.put(group, old - 1);
        }
        if (tmp.isEmpty()) {
            scoreSort.remove(score);
        }
    }
}