第 221 场周赛题解

Q1 1704. 判断字符串的两半是否相似 (opens new window)

直接暴力。

class Solution5637 {
    fun halvesAreAlike(s: String): Boolean {
        val arr = arrayOf('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U')
        return s.substring(0, s.length / 2).count {
            it in arr
        } == s.substring(s.length / 2, s.length).count {
            it in arr
        }
    }
}

Q2 1705. 吃苹果的最大数目 (opens new window)

按题意理解，贪心每次都吃最快要过期的苹果即可，可以通过优先级队列维护按过期时间排序的苹果。

class Solution1705 {
    fun eatenApples(apples: IntArray, days: IntArray): Int {
        val pq = PriorityQueue<IntArray>(compareBy { it[0] })
        var ans = 0
        var i = 0
        while (i in apples.indices || pq.isNotEmpty()) {
            while (pq.isNotEmpty() && pq.peek()[0] <= i) {
                pq.poll()
            }
            if (i in apples.indices && apples[i] != 0) {
                pq.offer(intArrayOf(i + days[i], apples[i]))
            }
            if (pq.isNotEmpty()) {
                val item = pq.peek()
                if (item[1] > 1) {
                    item[1]--
                } else {
                    pq.poll()
                }
                ans++
            }
            i++
        }
        return ans
    }
}

Q3 1706. 球会落何处 (opens new window)

数据范围$1 <= m, n <= 100$比较小，直接模拟即可。

经过一个格子，小球被卡住或向下一层落去。向下落一定是左下或右下，根据几种不同情况算出$DP$数组，标识每个格子对小球的影响：

• 0：小球被卡在当前格子
• 1：小球向右下落
• -1：小球向左下落

之后直接遍历最顶层的球即可，时间复杂度为$O(n^3)$。也可以增加$memo$算出每个格子的最终结果，将时间复杂度降为$O(n^2)$。

class Solution5210 {
    fun findBall(grid: Array<IntArray>): IntArray {
        val n = grid.size
        val m = grid[0].size
        val dp = Array<IntArray>(n) { IntArray(m) }
        for (i in 0 until n)
            for (j in 0 until m)
                dp[i][j] = when {
                    grid[i][j] == 1 -> if (j + 1 < m && grid[i][j + 1] == 1) 1 else 0
                    else -> if (j > 0 && grid[i][j - 1] == -1) -1 else 0
                }
        val ans = arrayListOf<Int>()
        fun dfs(i: Int, j: Int) {
            if (i == n) {
                ans.add(j)
                return
            }
            if (dp[i][j] == 0) {
                ans.add(-1)
                return
            }
            dfs(i + 1, j + dp[i][j])
        }
        for (i in 0 until m) {
            dfs(0, i)
        }
        return ans.toIntArray()
    }
}

Q4 1707. 与数组中元素的最大异或值 (opens new window)

离线算法+Trie字典树。

首先，由于有最大值$m_i$的限制，因此需要不断的扩充可比较范围。先将$queries$按照$m_i$排序，同时$nums$数组也从小到大排序，逐渐的增加可比较的内容。

其次，对于$xor$运算的比较，如果将两两的值都求出来，则需要$O(n^2)$的时间复杂度。这里可以利用字典树Trie，将现有的数字按Bit位插入Trie，获取最大值可以在线性时间内查询到。

class Solution1707 {
    fun maximizeXor(nums: IntArray, queries: Array<IntArray>): IntArray {
        val q = queries.sortedBy { it[1] }
        nums.sort()
        var i = 0
        var j = 0
        var cur = q[i]
        val map = HashMap<String, Int>()
        val root = Trie<Int>()
        while (j in q.indices) {
            while (i in nums.indices && nums[i] <= cur[1]) {
                root.insertInt(nums[i])
                i++
            }
            map[cur.joinToString()] = root.maxXor(cur[0])
            j++
            if (j !in q.indices) break
            cur = q[j]
        }
        return queries.map {
            map.getOrDefault(it.joinToString(), -1)
        }.toIntArray()
    }
}

class Trie<T> {
    class TrieNode<T>(val init: T? = null) {
        val value: T? = init
        val children: ArrayList<TrieNode<T>> = arrayListOf()
    }

    val root = TrieNode<T>()

    /**
     * insert value
     * */
    fun insert(value: Array<T>) {
        fun dfs(node: TrieNode<T>, depth: Int) {
            if (depth !in value.indices) return
            if (!node.children.map { it.value }.contains(value[depth])) {
                node.children.add(TrieNode<T>(value[depth]))
            }
            val next = node.children.first { it.value == value[depth] }
            dfs(next, depth + 1)
        }
        dfs(root, 0)
    }
}

fun Trie<Int>.insertInt(key: Int) {
    var temp = this.root
    for (i in 31 downTo 0) {
        val curBit = (key and (1 shl i)).let { if (it > 0) 1 else 0 }
        val item = temp.children.firstOrNull { it.value == curBit }
        if (item == null)
            temp.children.add(Trie.TrieNode(curBit))
        temp = temp.children.first { it.value == curBit }
    }
}

/**
 * https://www.geeksforgeeks.org/maximum-possible-xor-every-element-array-another-array/
 * */
fun Trie<Int>.maxXor(key: Int): Int {
    if (root.children.isEmpty()) return -1
    var temp = root
    var cur = 0
    for (i in 31 downTo 0) {
        cur *= 2
        val curBit = (key and (1 shl i)).let { if (it > 0) 1 else 0 }
        temp = if (temp.children.firstOrNull { it.value == 1 - curBit } != null)
            temp.children.first { it.value == 1 - curBit }
        else
            temp.children.first { it.value == curBit }
        cur += curBit xor temp.value!!
    }
    return cur
}