一、本周周赛总结

• T1 模拟。
• T2 计数。
• T3 模拟。
• T4 dfs。
  

6416. 找出不同元素数目差数组

6416. 找出不同元素数目差数组

1. 题目描述

2. 思路分析

• 数据量小，按题意模拟即可。

3. 代码实现

class Solution:def distinctDifferenceArray(self, a: List[int]) -> List[int]:ans = []n = len(a)for i in range(n):ans.append(len(set(a[:i + 1])) - len(set(a[i + 1:])))return ans

6417. 频率跟踪器

6417. 频率跟踪器

1. 题目描述

2. 思路分析

• 额外用一个计数器，计数频率即可。

3. 代码实现

class FrequencyTracker:def __init__(self):self.cnt = Counter()self.f = Counter()def add(self, a: int) -> None:x = self.cnt[a]if x > 0:self.f[x] -= 1                        self.cnt[a] += 1        self.f[self.cnt[a]] += 1def deleteOne(self, a: int) -> None:if self.cnt[a] > 0:            self.f[self.cnt[a]] -= 1            self.cnt[a] -= 1self.f[self.cnt[a]] += 1def hasFrequency(self, fr: int) -> bool:return self.f[fr] > 0

6418. 有相同颜色的相邻元素数目

6418. 有相同颜色的相邻元素数目

1. 题目描述

2. 思路分析

• 直接模拟，看看每次修改的变化量是多少。
• 为了方便编码，把a前后都加个0。把ans初始化成0。
• 每次修改，判断和相邻元素的相同性，调整当前值。
  • 若修改的颜色不变，则值不变直接返回。
  • 若修改前的数和相邻相同，则值需要减小1。(注意0不算)
  • 若修改后和相邻数相同，则值增加1。

3. 代码实现

class Solution:def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:a = [0]*(n+2) ans = [0]for i,c in queries:i += 1x = ans[-1]if a[i] == c:ans.append(x)continue if a[i] == a[i-1] != 0:x -= 1 if a[i] == a[i+1] != 0:x -= 1if c == a[i-1]:x +=1 if c == a[i+1]:x += 1ans.append(x)a[i] = c return ans[1:]            

6419. 使二叉树所有路径值相等的最小代价

6419. 使二叉树所有路径值相等的最小代价

1. 题目描述

2. 思路分析

• 由于只能增加，因此只能修改更小的那条路径。
• dfs归的过程中，发现左右两边最大路径不同的话，把小的那边的节点增加。
• 由于是完全二叉树，不用建图，直接计算左右孩子下标即可。

3. 代码实现

class Solution:def minIncrements(self, n: int, cost: List[int]) -> int:ans = 0 def dfs(u):if u>n:return 0 nonlocal ans l = dfs(u*2)r = dfs(u*2+1)if l > r:l,r= r,lans += r - l return r + cost[u-1]dfs(1)return ans                  

参考链接