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