第 253 场周赛题解

Q1 1961. 检查字符串是否为数组前缀 (opens new window)

简单题，数据量小，不考虑时间复杂度，怎么快怎么来吧。

class Solution5838 {
    fun isPrefixString(s: String, words: Array<String>): Boolean {
        return (1..words.size).any {
            words.take(it).joinToString("") == s
        }
    }
}

Q2 1962. 移除石子使总数最小 (opens new window)

贪心就好，优先级队列一直存着当前的石头数。

class Solution5839 {
    fun minStoneSum(piles: IntArray, k: Int): Int {
        val pq = PriorityQueue<Int>(compareBy { -it })
        piles.forEach {
            pq.offer(it)
        }
        repeat(k) {
            val item = pq.poll()
            pq.offer((item + 1) / 2)
        }
        return pq.sum()
    }
}

Q3 1963. 使字符串平衡的最小交换次数 (opens new window)

设置计数$a$为当前有左括号的数量，当遇到右括号时，若$a == 0$则需要进行一次交换。注意，这次交换也会增加$a$的计数，最后计算交换的次数即可。

class Solution5840 {
    fun minSwaps(s: String): Int {
        var a = 0
        var ans = 0
        s.forEach {
            if (it == ']') {
                if (a == 0) {
                    a++
                    ans++
                }
                else if (a != 0) a--
            } else {
                a++
            }
        }
        return ans
    }
}

Q4 1964. 找出到每个位置为止最长的有效障碍赛跑路线 (opens new window)

就是普通的求最长非递减子序列长度，利用二分法维护当前链表即可。

class Solution5841 {
    // 最长非递增子序列
    fun longestObstacleCourseAtEachPosition(obstacles: IntArray): IntArray {
        val ans = ArrayList<Int>()
        val cur = ArrayList<Int>()
        obstacles.forEach {
            // 若要严格递增，这里>改为>=
            val index = cur.biFirstIndexOf { c -> c > it }
            ans.add(
                if (index == -1) {
                    cur.add(it)
                    cur.size
                } else {
                    cur[index] = it
                    index + 1
                }
            )
        }
        return ans.toIntArray()
    }
}

/**
 * 二分查找，找到第一个满足条件的Index
 * 若整个列表都没有满足的，返回-1
 * */
fun <T> ArrayList<T>.biFirstIndexOf(func: (T) -> Boolean): Int {
    if (this.isEmpty()) return -1
    var left = 0
    var right = this.lastIndex
    while (left + 1 < right) {
        val mid = (left + right).ushr(1)
        when {
            func(this[mid]) -> right = mid
            else -> left = mid
        }
    }
    return when {
        func(this[left]) -> left
        func(this[right]) -> right
        else -> -1
    }
}