第 272 场周赛题解

Q1 2108. 找出数组中的第一个回文字符串 (opens new window)

签到。

class SolutionA {
    fun firstPalindrome(words: Array<String>): String {
        return words.firstOrNull { it == it.reversed() } ?: ""
    }
}

Q2 2109. 向字符串添加空格 (opens new window)

继续签到。（这以往也就是简单题）

class SolutionB {
    fun addSpaces(s: String, spaces: IntArray): String {
        val sb = StringBuilder(s)
        var offset = 0
        spaces.forEach {
            sb.insert(it + offset, ' ')
            offset++
        }
        return sb.toString()
    }
}

Q3 2110. 股票平滑下跌阶段的数目 (opens new window)

仍然签到。每次增加以当前为结尾的子数组数目。

class SolutionC {
    fun getDescentPeriods(prices: IntArray): Long {
        var ans = 0L
        var cur = 1L
        for (i in prices.indices) {
            if (i != 0 && prices[i] == prices[i - 1] - 1) {
                cur++
            } else {
                cur = 1L
            }
            ans += cur
        }
        return ans
    }
}

Q4 2111. 使数组 K 递增的最少操作次数 (opens new window)

最长非递减子序列。增加是否严格递增的变量，扩展方法快速支持（这里等号少写一个，WA了一次...）。

class SolutionD {
    fun kIncreasing(arr: IntArray, k: Int): Int {
        val l = Array<ArrayList<Int>>(k) { ArrayList<Int>() }
        for (i in arr.indices) {
            l[i % k].add(arr[i])
        }
        var ans = 0
        for (i in 0 until k) {
            ans += l[i].size - l[i].toIntArray().lis(false)
        }
        return ans
    }
}

/**
 * 单调递增子序列长度
 *
 * @param strict 是否严格递增 true 严格递增 false 可以相等
 * */
fun IntArray.lis(strict: Boolean = true): Int {
    var len = 1
    val n: Int = this.size
    if (n == 0) {
        return 0
    }
    val d = IntArray(n + 1)
    d[len] = this[0]
    for (i in 1 until n) {
        if (this[i] > d[len] || (!strict && this[i] == d[len])) {
            d[++len] = this[i]
        } else {
            var l = 1
            var r = len
            var pos = 0
            while (l <= r) {
                val mid = l + r shr 1
                if (d[mid] < this[i] || (!strict && d[mid] == this[i])) {
                    pos = mid
                    l = mid + 1
                } else {
                    r = mid - 1
                }
            }
            d[pos + 1] = this[i]
        }
    }
    return len
}