異なる要素数の差配列を見つける#
-
ハッシュテーブルまず後ろから前に各インデックスの出現回数をカウントし、次に前から後ろに各数の出現回数をカウントします。
-
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 }
頻度トラッカー#
-
ハッシュテーブルそれぞれの数の出現頻度と各頻度の回数をカウントするために、2 つのハッシュテーブルを使用します。
-
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 }
同じ色の隣接要素の数#
-
シミュレーション分類して議論し、各変更には 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 { 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 }
二分木のすべてのパスの値を等しくするための最小コスト#
-
貪欲法下から上に修正し、2 つの兄弟ノードのパスの値が等しくない場合、この時の最小コストは小さい値を大きい値に変更することです。この時のコストは両者の絶対値です。上に向かうとき、この時のノード値の合計を上に伝達します。その後の修正は同じ修正方法になります。
-
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 }