LeetCode Contest 344

6416. Find the Distinct Difference Array

给你一个下标从 0 开始的数组 nums ，数组长度为 n 。

nums 的 不同元素数目差 数组可以用一个长度为 n 的数组 diff 表示，其中 diff[i] 等于前缀 nums[0, ..., i] 中不同元素的数目 减去 后缀 nums[i + 1, ..., n - 1] 中不同元素的数目。

返回 nums 的 不同元素数目差 数组。

注意 nums[i, ..., j] 表示 nums 的一个从下标 i 开始到下标 j 结束的子数组（包含下标 i 和 j 对应元素）。特别需要说明的是，如果 i > j ，则 nums[i, ..., j] 表示一个空子数组。

测试样例：

输入：nums = [1,2,3,4,5]

输出：[-3,-1,1,3,5]

解释：

• 对于 i = 0，前缀中有 1 个不同的元素，而在后缀中有 4 个不同的元素。因此，diff[0] = 1 - 4 = -3 。
• 对于 i = 1，前缀中有 2 个不同的元素，而在后缀中有 3 个不同的元素。因此，diff[1] = 2 - 3 = -1 。
• 对于 i = 2，前缀中有 3 个不同的元素，而在后缀中有 2 个不同的元素。因此，diff[2] = 3 - 2 = 1 。
• 对于 i = 3，前缀中有 4 个不同的元素，而在后缀中有 1 个不同的元素。因此，diff[3] = 4 - 1 = 3 。
• 对于 i = 4，前缀中有 5 个不同的元素，而在后缀中有 0 个不同的元素。因此，diff[4] = 5 - 0 = 5 。

解答：提示有：1 <= n == nums.length <= 50。这个范围实在是太小了，直接暴力计算distinct值就行了。

class Solution {
    public int[] distinctDifferenceArray(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        for (int i = 0; i < len; ++i) {
            HashSet<Integer> left = new HashSet<>(), right = new HashSet<>();
            for (int j = 0; j < len; ++j) {
                if (j <= i) {
                    left.add(nums[j]);
                } else {
                    right.add(nums[j]);
                }
            }
            res[i] = left.size() - right.size();
        }
        return res;
    }
}

6417. Frequency Tracker

请你设计并实现一个能够对其中的值进行跟踪的数据结构，并支持对频率相关查询进行应答。

实现 FrequencyTracker 类：

• FrequencyTracker()：使用一个空数组初始化 FrequencyTracker 对象。
• void add(int number)：添加一个 number 到数据结构中。
• void deleteOne(int number)：从数据结构中删除一个 number 。数据结构 可能不包含 number ，在这种情况下不删除任何内容。
• bool hasFrequency(int frequency): 如果数据结构中存在出现 frequency 次的数字，则返回 true，否则返回 false。

测试样例：

输入：["FrequencyTracker", "add", "add", "hasFrequency"]
[[], [3], [3], [2]]

输出：[null, null, null, true]

解释：

• FrequencyTracker frequencyTracker = new FrequencyTracker();
• frequencyTracker.add(3); // 数据结构现在包含 [3]
• frequencyTracker.add(3); // 数据结构现在包含 [3, 3]
• frequencyTracker.hasFrequency(2); // 返回 true ，因为 3 出现 2 次

解答：本质上就是2个map。一个记录数字出现的次数，另一个记录次数出现的次数。

class FrequencyTracker {
    private HashMap<Integer, Integer> numberCount, freqCount;

    public FrequencyTracker() {
        numberCount = new HashMap<>();
        freqCount = new HashMap<>();
    }

    public void add(int number) {
        if (numberCount.containsKey(number)) {
            removeKey(freqCount, numberCount.get(number));
        }
        int tmp = numberCount.getOrDefault(number, 0) + 1;
        numberCount.put(number, tmp);
        freqCount.put(tmp, freqCount.getOrDefault(tmp, 0) + 1);
    }

    public void deleteOne(int number) {
        if (numberCount.containsKey(number)) {
            int o = removeKey(numberCount, number);
            removeKey(freqCount, o);
            if (o != 1) {
                numberCount.put(number, o - 1);
                freqCount.put(o - 1, freqCount.getOrDefault(o - 1, 0) + 1);
            }
        }
    }

    public boolean hasFrequency(int frequency) {
        return freqCount.containsKey(frequency);
    }

    private int removeKey(HashMap<Integer, Integer> map, int key) {
        int tmp = map.get(key);
        if (tmp == 1) {
            map.remove(key);
        } else {
            map.put(key, tmp - 1);
        }
        return tmp;
    }
}

/**
 * Your FrequencyTracker object will be instantiated and called as such:
 * FrequencyTracker obj = new FrequencyTracker();
 * obj.add(number);
 * obj.deleteOne(number);
 * boolean param_3 = obj.hasFrequency(frequency);
 */

6418. Number of Adjacent Elements With the Same Color

给你一个下标从 0 开始、长度为 n 的数组 nums 。一开始，所有元素都是 未染色 （值为 0 ）的。

给你一个二维整数数组 queries ，其中 queries[i] = [indexi, colori] 。

对于每个操作，你需要将数组 nums 中下标为 indexi 的格子染色为 colori 。

请你返回一个长度与 queries 相等的数组 answer ，其中 answer[i]是前 i 个操作 之后 ，相邻元素颜色相同的数目。

更正式的，answer[i] 是执行完前 i 个操作后，0 <= j < n - 1 的下标 j 中，满足 nums[j] == nums[j + 1] 且 nums[j] != 0 的数目。

测试样例

输入：n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]

输出：[0,1,1,0,2]

解释：

一开始数组 nums = [0,0,0,0] ，0 表示数组中还没染色的元素。

• 第 1 个操作后，nums = [2,0,0,0] 。相邻元素颜色相同的数目为 0 。
• 第 2 个操作后，nums = [2,2,0,0] 。相邻元素颜色相同的数目为 1 。
• 第 3 个操作后，nums = [2,2,0,1] 。相邻元素颜色相同的数目为 1 。
• 第 4 个操作后，nums = [2,1,0,1] 。相邻元素颜色相同的数目为 0 。
• 第 5 个操作后，nums = [2,1,1,1] 。相邻元素颜色相同的数目为 2 。

解答：这道题目就是记录一下query发生前后，query位置所发生的相邻颜色变化情况。

class Solution {
    public int[] colorTheArray(int n, int[][] queries) {
        int[] mem = new int[n];
        int[] res = new int[queries.length];
        int count = 0;
        for (int i = 0; i < queries.length; ++i) {
            int p = queries[i][0];
            if (p - 1 >= 0 && mem[p] != 0 && mem[p] == mem[p - 1]) {
                count -= 1;
            }
            if (p + 1 < n && mem[p] != 0 && mem[p] == mem[p + 1]) {
                count -= 1;
            }
            mem[p] = queries[i][1];

            if (p - 1 >= 0 && mem[p] != 0 && mem[p] == mem[p - 1]) {
                count += 1;
            }
            if (p + 1 < n && mem[p] != 0 && mem[p] == mem[p + 1]) {
                count += 1;
            }
            res[i] = count;
        }
        return res;
    }
}

6419. Make Costs of Paths Equal in a Binary Tree

给你一个整数 n 表示一棵 满二叉树 里面节点的数目，节点编号从 1 到 n 。根节点编号为 1 ，树中每个非叶子节点 i 都有两个孩子，分别是左孩子 2 i 和右孩子 2 i + 1 。

树中每个节点都有一个值，用下标从 0 开始、长度为 n 的整数数组 cost 表示，其中 cost[i] 是第 i + 1 个节点的值。每次操作，你可以将树中 任意 节点的值 增加 1 。你可以执行操作 任意 次。

你的目标是让根到每一个 叶子结点 的路径值相等。请你返回 最少 需要执行增加操作多少次。

注意：

• 满二叉树 指的是一棵树，它满足树中除了叶子节点外每个节点都恰好有 2 个节点，且所有叶子节点距离根节点距离相同。
• 路径值 指的是路径上所有节点的值之和。

测试样例

输入：n = 7, cost = [1,5,2,2,3,3,1]

输出：6

解释：

我们执行以下的增加操作：

• 将节点 4 的值增加一次。
• 将节点 3 的值增加三次。
• 将节点 7 的值增加两次。

从根到叶子的每一条路径值都为 9 。总共增加次数为 1 + 3 + 2 = 6 。这是最小的答案。

解答：因为每一条从根到每一个 叶子结点 的路径值相等。每一个节点到它的叶节点路径和都必须相同。

路径越高的位置修改数字所产生的代价也会越小。DFS计算路径最大值就可以了。

class Solution {
    public int minIncrements(int n, int[] cost) {
        int[] res = {0};
        helper(cost, 1, res);
        return res[0];
    }

    private int helper(int[] cost, int pos, int[] res) {
        if (pos - 1 >= cost.length) return 0;
        int left = helper(cost, pos * 2, res), right = helper(cost, pos * 2 + 1, res);
        if (left != right) {
            res[0] += Math.abs(left - right);
        }
        return Math.max(left, right) + cost[pos - 1];
    }
}

着实究极手速场了。这周还Wrong Answer了一次，心痛。