344 LeetCode周赛

找出不同元素数目差数组

• 哈希表

  先从后往前统计后缀中每个下标出现的次数，再从前往后统计每个数出现的次数。

• 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++ &#123;
          set[nums[i]] = true
          ans[i] = len(set) - suf[i+1]
      &#125;
  
      return ans
  &#125;

频率跟踪器

• 哈希表

  分别使用两个哈希表统计每个数出现的频率和每个频率的次数。

• 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
  }

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

• 模拟

  分类讨论，每此修改只有两种情况：

  1. 修改前前后相等，修改后造成前后不相等
  2. 修改前前后不相等， 修改后造成前后相等

• 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 &#123;
              count--
          &#125;
  
          // 改动后相等
          if j > 0 && nums[j] != nums[j-1] && nums[j-1] == c &#123;
              count++
          &#125; 
          if j < n-1 && nums[j] != nums[j+1] && nums[j+1] == c &#123;
              count++
          &#125;
          ans[i] = count
          nums[j] = c
      &#125;
      return ans
  &#125;

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

• 贪心

  从下往上修改，当两个兄弟节点的路径值不等时，此时最小代价就是将其中小的值，改为大的值。此时代价就是两者绝对值。在向上时，将此时的节点值的和向上传递。此后的修改就是相同的修改方法

• 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 &#123;
              l, r = r, l
          &#125;
  
          ans += (l - r)
          cost[i-1] += l
      &#125;
      return ans
  &#125;