找出不同元素數目差數組#
-
哈希表先從後往前統計後綴中每個下標出現的次數，再從前往後統計每個數出現的次數。
-
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 }