力扣第 344 场周赛题解

题目链接：https://leetcode.cn/contest/weekly-contest-344/

# T1. 找出不同元素数目差数组

hash 计数

	class Solution {
	public int[] distinctDifferenceArray(int[] nums) {
	// 记录每个数出现的次数
	int[] s = new int[51];
	// 记录后缀中不同元素的个数
	int scnt = 0;
	for (int num : nums) {
	++s[num];
	if (s[num] == 1) ++scnt;
	}

	int[] p = new int[51];
	// 记录前缀中不同元素的个数
	int pcnt = 0;
	int n = nums.length;
	for (int i = 0; i < n; ++i) {
	int k = nums[i];
	--s[k];
	++p[k];
	if (s[k] == 0) --scnt;
	if (p[k] == 1) ++pcnt;
	nums[i] = pcnt - scnt;
	}

	return nums;
	}
	}

两个哈希表：

	class FrequencyTracker {
	// number -> cnt
	Map<Integer, Integer> cntMap;
	// frequent -> different number's count
	Map<Integer, Integer> freMap;
	public FrequencyTracker() {
	cntMap = new HashMap<>();
	freMap = new HashMap<>();
	}
	public void add(int number) {
	int cnt = cntMap.getOrDefault(number, 0);
	if (cnt > 0) {
	// 该数还有 cnt 个，因此个数为 cnt 的要减一
	freMap.put(cnt, freMap.getOrDefault(cnt, 0) - 1);
	}
	++cnt;
	cntMap.put(number, cnt);
	// 出现次数为 cnt+1 的数的个数 +1
	freMap.put(cnt, freMap.getOrDefault(cnt, 0) + 1);
	}
	public void deleteOne(int number) {
	int cnt = cntMap.getOrDefault(number, 0);
	if (cnt > 0) {
	// 出现次数为 cnt 的数的个数 -1
	freMap.put(cnt, freMap.getOrDefault(cnt, 0) - 1);
	--cnt;
	cntMap.put(number, cnt);
	// 次数为 0 就不要存了
	if (cnt > 0) freMap.put(cnt, freMap.getOrDefault(cnt, 0) + 1);
	}
	}
	public boolean hasFrequency(int frequency) {
	return freMap.getOrDefault(frequency, 0) > 0;
	}
	}

	/**
	* 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);
	*/

着色的格子只与相邻的格子的颜色相同与否，才会对答案有影响

技巧：可以先减去原有颜色对答案的影响，再计算重新着色对答案的影响

	class Solution {
	public int[] colorTheArray(int n, int[][] queries) {
	int[] c = new int[n];
	int len = queries.length;
	int[] ret = new int[len];
	int cnt = 0;

	for (int i = 0; i < len; ++i) {
	int k = queries[i][0];
	if (c[k] > 0) {
	// 原来有着色，判断左右相邻的连个格子，
	// 如果颜色相同，则减一
	if (k > 0 && c[k - 1] == c[k]) --cnt;
	if (k < n - 1 && c[k] == c[k + 1]) --cnt;
	}
	// 重新着色
	c[k] = queries[i][1];
	// 如果与相邻的格子相同，则加一
	if (k > 0 && c[k - 1] == c[k]) ++cnt;
	if (k < n - 1 && c[k] == c[k + 1]) ++cnt;

	ret[i] = cnt;
	}

	return ret;
	}
	}

贪心

	class Solution {
	public int minIncrements(int n, int[] cost) {
	int ret = 0;
	for (int p = n / 2; p > 0; --p) {
	// 为了使两个子节点的值相等，只需把较小的值加到较大者
	ret += Math.abs(cost[2 * p - 1] - cost[2 * p]);
	// 把最大的加到父亲节点
	cost[p - 1] += Math.max(cost[2 * p - 1], cost[2 * p]);
	}

	return ret;
	}
	}