第 262 场周赛题解

Q1 2032. 至少在两个数组中出现的值 (opens new window)

通过${intersect}$求交集。

class Solution5894 {
    fun twoOutOfThree(nums1: IntArray, nums2: IntArray, nums3: IntArray): List<Int> {
        val ans = hashSetOf<Int>()
        ans.addAll(nums1.intersect(nums2.toList()))
        ans.addAll(nums2.intersect(nums3.toList()))
        ans.addAll(nums1.intersect(nums3.toList()))
        return ans.toList()
    }
}

Q2 2033. 获取单值网格的最小操作数 (opens new window)

需要了解到使用中位数作为目标值。

class Solution5895 {
    fun minOperations(grid: Array<IntArray>, x: Int): Int {
        val n = grid.size
        val m = grid[0].size
        val l = arrayListOf<Int>()
        for (i in grid.indices) {
            l.addAll(grid[i].toList())
        }

        val mid = l.sorted()[m * n / 2]
        var ans = 0
        for (i in grid.indices) {
            for (j in grid[0].indices) {
                val diff = abs(grid[i][j] - mid)
                if (diff % x != 0) return -1
                ans += diff / x
            }
        }
        return ans
    }
}

Q3 2034. 股票价格波动 (opens new window)

硬模拟，这题没意思。

class StockPrice() {

    val tm = TreeMap<Int, Int>()

    val pqMax = PriorityQueue<Int>(compareBy { -it })
    val pqMin = PriorityQueue<Int>(compareBy { it })

    fun update(timestamp: Int, price: Int) {
        if (timestamp in tm.keys) {
            pqMax.remove(tm[timestamp])
            pqMin.remove(tm[timestamp])
        }
        tm[timestamp] = price
        pqMax.offer(price)
        pqMin.offer(price)
    }

    fun current(): Int {
        return tm.lastEntry().value
    }

    fun maximum(): Int {
        return pqMax.peek()
    }

    fun minimum(): Int {
        return pqMin.peek()
    }

}

Q4 2035. 将数组分成两个数组并最小化数组和的差 (opens new window)

数据范围是$30$，如果直接暴力是$2^{30}$会超时。先用折半法处理两部分数据，再组合起来。

左侧处理数据填充到$0..n$的n+1的长度的数组，分别代表选择了几个index。右侧同理，然后左右选择总和为n的，通过TreeSet查找最接近$sum$的。

class Solution5897 {
    // 折半法
    // size为30的，先左15 右15拆
    fun minimumDifference(nums: IntArray): Int {
        val n = nums.size / 2

        fun helper(arr: Array<TreeSet<Int>>, offset: Int) {
            for (mask in 0 until (1 shl n)) {
                var cur = 0
                var count = 0
                // 该状态下的总和及总count
                for (i in 0 until n) {
                    if (mask and (1 shl i) != 0) {
                        count++
                        cur += nums[i + offset]
                    }
                }
                arr[count].add(cur)
            }
        }

        val leftArr = Array<TreeSet<Int>>(n + 1) { TreeSet() }
        val rightArr = Array<TreeSet<Int>>(n + 1) { TreeSet() }

        helper(leftArr, 0)
        helper(rightArr, n)

        var ans = Int.MAX_VALUE
        val sum = nums.sum()
        for (i in leftArr.indices) {
            leftArr[i].forEach { left ->
                val j = n - i
                rightArr[j].ceiling(sum / 2 - left)?.let { right ->
                    ans = minOf(ans, abs((left + right) * 2 - sum))
                }
                rightArr[j].floor(sum / 2 - left)?.let { right ->
                    ans = minOf(ans, abs((left + right) * 2 - sum))
                }
            }
        }

        return ans
    }
}