Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

3346. Maximum Frequency of an Element After Performing Operations I
3347. Maximum Frequency of an Element After Performing Operations II

兩題差不多，放在一起講

思路:

先記錄nums中每個數字出現的次數

找出nums矩陣裡的最大值maxnum

接著從0~maxnum每個數都去找距離這個數[-k,k]以內的值在nums出現的次數

基本上類似prefixsum

從0 -> maxnum跑一次、maxnum -> 0再跑一次

最後找出0~maxnum中是哪個值在[-k,k]這個範圍內在nums出現最多次

就是答案了



golang code :

func maxFrequency(nums []int, k int, numOperations int) int {
        max_num := slices.Max(nums)
        count, adjacent := make([]int, max_num+1), make([]int, max_num+1)
        for _, val := range nums {
                count[val]++
        }
        adj := 0
        for i := 0; i <= max_num; i++ {
                if i-k-1 > -1 {
                        adj -= count[i-k-1]
                }
                adjacent[i] = adj
                adj += count[i]
        }
        ans, adj := 0, 0
        for i := max_num; i > -1; i-- {
                if i+k+1 <= max_num {
                        adj -= count[i+k+1]
                }
                adjacent[i] += adj
                adj += count[i]
                ans = max(ans, count[i]+min(numOperations, adjacent[i]))
        }
        return ans
}



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.160.205 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1732799638.A.13E.html
→ JIWP: 笑了 hard那個不行 會超出時間
推 sustainer123: 寶 救我 有沒有DP秘訣 我最近一直刷DP
→ sustainer123: 但感覺完全沒進步==
→ JIWP: 你刷dp幹嘛
推 sustainer123: 我感覺我DP跟Graph最廢 想說補強一下
→ sustainer123: 結果刷DP感覺完全沒進步 GG