344 LeetCode周赛
找出不同元素数目差数组
-
哈希表先从后往前统计后缀中每个下标出现的次数，再从前往后统计每个数出现的次数。
-
Python
1class Solution: 2 def distinctDifferenceArray(self, nums: List[int]) -> List[int]: 3 n = len(nums) 4 ans = [0] * n 5 6 for i, num in enumerate(nums): 7 c1 = Counter(nums[:i+1]) 8 c2 = Counter(nums[i+1:]) 9 ans[i] = len(c1) - len(c2) 10 return ans -
Golang
1func distinctDifferenceArray(nums []int) []int { 2 n := len(nums) 3 4 suf := make([]int, n+1) 5 set := make(map[int]bool) 6 7 for i := n - 1; i >= 0; i-- { 8 set[nums[i]] = true 9 suf[i] = len(set) 10 } 11 12 set = make(map[int]bool) 13 ans := make([]int, n) 14 for i := 0; i < n; i++ { 15 set[nums[i]] = true 16 ans[i] = len(set) - suf[i+1] 17 } 18 19 return ans 20}
频率跟踪器
-
哈希表分别使用两个哈希表统计每个数出现的频率和每个频率的次数。
-
Python
1class FrequencyTracker: 2 3 def __init__(self): 4 self.counter = defaultdict(int) 5 self.nums = defaultdict(int) 6 7 def add(self, number: int) -> None: 8 if self.counter[self.nums[number]] > 0: 9 self.counter[self.nums[number]] -= 1 10 11 self.nums[number] += 1 12 self.counter[self.nums[number]] += 1 13 14 def deleteOne(self, number: int) -> None: 15 if self.nums[number] != 0: 16 self.counter[self.nums[number]] -= 1 17 self.nums[number] -= 1 18 self.counter[self.nums[number]] += 1 19 20 def hasFrequency(self, frequency: int) -> bool: 21 if self.counter[frequency] > 0: 22 return True 23 return False -
Golang
1type FrequencyTracker struct { 2 nums map[int]int 3 f map[int]int 4} 5 6func Constructor() FrequencyTracker { 7 ft := FrequencyTracker{} 8 ft.nums = make(map[int]int) 9 ft.f = make(map[int]int) 10 11 return ft 12} 13 14func (this *FrequencyTracker) Add(number int) { 15 this.f[this.nums[number]]-- 16 this.nums[number]++ 17 this.f[this.nums[number]]++ 18} 19 20func (this *FrequencyTracker) DeleteOne(number int) { 21 // 只有number存在才进行删除 22 if this.nums[number] > 0 { 23 this.f[this.nums[number]]-- 24 this.nums[number]-- 25 this.f[this.nums[number]]++ 26 } 27 28} 29 30func (this *FrequencyTracker) HasFrequency(frequency int) bool { 31 return this.f[frequency] > 0 32}
有相同颜色的相邻元素数目
-
模拟分类讨论，每此修改只有两种情况：
- 修改前前后相等，修改后造成前后不相等
- 修改前前后不相等， 修改后造成前后相等
-
Python
1class Solution: 2 def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]: 3 nums = [0] * n 4 m = len(queries) 5 ans = [0] * m 6 7 pre = 0 8 for i, (idx, c) in enumerate(queries): 9 if idx > 0 and nums[idx] == nums[idx-1] and nums[idx-1] != c and nums[idx] != 0: 10 if pre > 0: 11 pre -= 1 12 if idx < n-1 and nums[idx] == nums[idx+1] and nums[idx+1] != c and nums[idx] != 0: 13 if pre > 0: 14 pre -= 1 15 16 if idx > 0 and nums[idx] != nums[idx-1] and nums[idx-1] == c: 17 pre += 1 18 19 if idx < n - 1 and nums[idx] != nums[idx + 1] and nums[idx + 1] == c: 20 pre += 1 21 nums[idx] = c 22 ans[i] = pre 23 24 return ans -
Golang
1func colorTheArray(n int, queries [][]int) []int { 2 nums := make([]int, n) 3 count := 0 4 ans := make([]int, len(queries)) 5 6 for i, q := range queries { 7 j, c := q[0], q[1] 8 9 // 改动原相等的值 10 if j > 0 && nums[j] == nums[j-1] && nums[j] != 0 && nums[j] != c && count > 0 { 11 count-- 12 } 13 if j < n-1 && nums[j] == nums[j+1] && nums[j] != 0 && nums[j] != c && count > 0 { 14 count-- 15 } 16 17 // 改动后相等 18 if j > 0 && nums[j] != nums[j-1] && nums[j-1] == c { 19 count++ 20 } 21 if j < n-1 && nums[j] != nums[j+1] && nums[j+1] == c { 22 count++ 23 } 24 ans[i] = count 25 nums[j] = c 26 } 27 return ans 28}
使二叉树所有路径值相等的最小代价
-
贪心从下往上修改，当两个兄弟节点的路径值不等时，此时最小代价就是将其中小的值，改为大的值。此时代价就是两者绝对值。在向上时，将此时的节点值的和向上传递。此后的修改就是相同的修改方法
-
Python
1class Solution: 2 def minIncrements(self, n: int, cost: List[int]) -> int: 3 ans = 0 4 5 for i in range(n//2, 0, -1): 6 ans += abs(cost[i*2-1] - cost[i*2]) 7 cost[i-1] += max(cost[i*2-1], cost[i*2]) 8 9 return ans -
Golang
1func minIncrements(n int, cost []int) int { 2 ans := 0 3 for i := n / 2; i > 0; i-- { 4 l, r := cost[i*2-1], cost[i*2] 5 if l < r { 6 l, r = r, l 7 } 8 9 ans += (l - r) 10 cost[i-1] += l 11 } 12 return ans 13}