Onehr7

Find the Distinct Difference Array#

• Hash Table

  First, count the occurrences of each index in the suffix from back to front, then count the occurrences of each number from front to back.

• Python

  Copy

  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

  Copy

  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
  }
  

Frequency Tracker#

• Hash Table

  Use two hash tables to track the frequency of each number and the count of each frequency.

• Python

  Copy

  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

  Copy

  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) {
  	// Only delete if number exists
  	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
  }
  

Number of Adjacent Elements with the Same Color#

• Simulation

  Classify and discuss, there are only two cases for each modification:

  1. The values before and after the modification are equal, and the modification causes them to be unequal.
  2. The values before and after the modification are unequal, and the modification causes them to be equal.

• Python

  Copy

  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

  Copy

  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]
  
  		// Modify the equal value
  		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--
  		}
  
  		// Modify to be equal
  		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
  }
  

Make Costs of Paths Equal in a Binary Tree#

• Greedy

  Modify from bottom to top. When the path values of two sibling nodes are not equal, the minimum cost is to change the smaller value to the larger value. The cost is the absolute difference between the two values. When moving up, pass the sum of the node values at this time. The subsequent modifications are the same.

• Python

  Copy

  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

  Copy

  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
  }