第 226 场周赛题解

Q1 5654. 盒子中小球的最大数量 (opens new window)

直接暴力即可，Kotlin可以方便的通过sumBy直接计算和。

class Solution5654 {
    fun countBalls(lowLimit: Int, highLimit: Int): Int {
        val map = HashMap<Int, Int>()
        for (i in lowLimit..highLimit) {
            val k = i.toString().sumBy { it - '0' }
            map[k] = map.getOrDefault(k, 0) + 1
        }
        return map.values.max()!!
    }
}

Q2 5665. 从相邻元素对还原数组 (opens new window)

由于数组中的元素均不相同，因此只有数组头尾的元素仅出现一次，其余元素均会出现两次。找到头尾后，遍历查找下一个即可。

class Solution5665 {
    fun restoreArray(adjacentPairs: Array<IntArray>): IntArray {
        val map = HashMap<Int, ArrayList<Int>>()
        adjacentPairs.forEach {
            val (x, y) = it
            map.getOrPut(x, { arrayListOf() }).add(y)
            map.getOrPut(y, { arrayListOf() }).add(x)
        }
        val seen = HashSet<Int>()
        val ans = arrayListOf<Int>()
        fun dfs(i: Int) {
            ans.add(i)
            seen.add(i)
            for (v in map[i]!!) {
                if (v !in seen) {
                    dfs(v)
                }
            }
        }
        dfs(map.filter { it.value.size == 1 }.keys.first())
        return ans.toIntArray()
    }
}

Q3 5667. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？ (opens new window)

比赛过程中最恶心人的一道题！

1. 注意天数是从0开始算，因此计算乘法时需要+1
2. favoriteDay 和 dailyCap 均是10的9次方范围，直接使用Int会越界

根据前缀和，计算出糖果I的范围是[min, max]闭区间，而第day天可以吃到的糖果范围是[dayMin, dayMax]，直接判断这两个区间是否有交集即可。

这种题在比赛时WA了很多次，各种边界条件判断不准确，这时候该冷静冷静，重新梳理下思路，使用最Simple的方法去解决。

class Solution5667 {
    fun canEat(candiesCount: IntArray, queries: Array<IntArray>): BooleanArray {
        val n = candiesCount.size
        val preSum = LongArray(n + 1)
        for (i in candiesCount.indices) {
            preSum[i + 1] = preSum[i] + candiesCount[i]
        }
        val ans = ArrayList<Boolean>()
        for (q in queries) {
            val min = preSum[q[0]] + 1
            val max = preSum[q[0] + 1]
            val day = q[1]
            val cap = q[2].toLong()
            val dayMin = day + 1
            val dayMax = (day + 1) * cap
            ans.add(min <= dayMax && max >= dayMin)
        }
        return ans.toBooleanArray()
    }
}

Q4 5666. 回文串分割 IV (opens new window)

先观察数据范围，长度只有2000，因此O(n²)的时间复杂度是可以接受的。

1. 先计算出所有开头、结尾的是否是回文的二维数组isPal
2. 找到以最后一个元素为结尾的，头部的index
3. 遍历上述符合条件的index，开始查找以i为分割，能够使得(0, i) 和 (i + 1, index - 1)均为回文，则该字符串可以拆分为3个非空的回文字符串

class Solution5666 {
    fun checkPartitioning(word: String): Boolean {
        val n = word.length
        val isPal = Array(n) { BooleanArray(n) }
        for (i in 0 until n) {
            for (j in 0..i) {
                if (word[j] == word[i] && (i - j < 2 || isPal[j + 1][i - 1])) {
                    isPal[j][i] = true
                }
            }
        }
        val last = ArrayList<Int>()
        for (i in 0 until n) {
            if (isPal[i][n - 1]) last.add(i)
        }
        for (l in last) {
            for (i in 0 until l) {
                if (isPal[0][i] && isPal[i + 1][l - 1]) {
                    return true
                }
            }
        }
        return false
    }
}