第 239 场周赛题解

Q1 1848. 到目标元素的最小距离 (opens new window)

普通暴力。

class Solution1848 {
    fun getMinDistance(nums: IntArray, target: Int, start: Int): Int {
        var min = Int.MAX_VALUE
        for (i in nums.indices) {
            if (nums[i] == target) {
                min = minOf(min, abs(i - start))
            }
        }
        return min
    }
}

Q2 1849. 将字符串拆分为递减的连续值 (opens new window)

$DFS$向下查找，长度小于$20$且至少要拆分为两个数值，因此使用$Long$足够表示。这里可以注意活用$toLongOrNull()$方法，可以方便的将不符合$Long$的数据排除，否则可能有$RunTimeError$。

class Solution5747 {
    fun splitString(s: String): Boolean {
        fun dfs(left: Int, cur: Long): Boolean {
            if (left >= s.length) return true
            var ans = false
            for (i in left + 1..s.length) {
                val next = s.substring(left, i).toLongOrNull()
                if (next == cur - 1) {
                    ans = ans or dfs(i, next)
                }
            }
            return ans
        }
        for (i in 1 until s.length) {
            val cur = s.substring(0, i).toLongOrNull() ?: continue
            if (dfs(i, cur)) return true
        }
        return false
    }
}

Q3 1850. 邻位交换的最小次数 (opens new window)

本题的最终状态其实是求$k$次$nextPermutation$的结果，主要还需要判断两个字符串需要交换多少次下标。交换的过程可以使用冒泡排序，查找交换次数的时间复杂度为$O(n^2)$。

class Solution1850 {
    fun getMinSwaps(num: String, k: Int): Int {
        val n = num.map { it - '0' }.toIntArray()
        for (i in 0 until k) {
            nextPermutation(n)
        }
        val start = num.map { it - '0' }.toIntArray()
        var ans = 0
        for (i in n.indices) {
            for (j in i until n.size) {
                if (start[i] == n[j]) {
                    ans += j - i
                    for (t in j - 1 downTo i) {
                        val tmp = n[t]
                        n[t] = n[t + 1]
                        n[t + 1] = tmp
                    }
                    break
                }
            }
        }
        return ans
    }

    fun nextPermutation(nums: IntArray) {
        for (i in nums.size - 2 downTo 0) {
            for (j in nums.size - 1 downTo i + 1) {
                if (nums[j] > nums[i]) {
                    val temp = nums[i]
                    nums[i] = nums[j]
                    nums[j] = temp
                    nums.sort(i + 1, nums.size)
                    return
                }
            }
        }
        nums.reverse()
    }
}

Q4 1851. 包含每个查询的最小区间 (opens new window)

利用线段树模板！先将区间按照长度排序，然后依次更新线段树的值。最后查询一遍即可，注意线段树的$merge$过程是要取最小值。

class Solution1851 {
    fun minInterval(intervals: Array<IntArray>, queries: IntArray): IntArray {
        val seg = SegmentTree<Int>(start = 0, end = Int.MAX_VALUE / 2, value = Int.MAX_VALUE / 2) { a, b -> minOf(a, b) }
        intervals.sortByDescending { it[1] - it[0] }
        intervals.forEach {
            seg.update(seg, it[0], it[1], it[1] - it[0] + 1)
        }
        val ans = arrayListOf<Int>()
        queries.forEach {
            seg.query(seg, it, it).also {
                if (it >= Int.MAX_VALUE / 2) ans.add(-1)
                else ans.add(it)
            }
        }
        return ans.toIntArray()
    }
}

class SegmentTree<T>(val start: Int = 0,
                     val end: Int = 0,
                     var value: T? = null,
                     private var lazy: T? = null,
                     val merge: (a: T, b: T) -> T) {

    var left: SegmentTree<T>? = null
    var right: SegmentTree<T>? = null
    val mid: Int
        get() {
            return start + (end - start) / 2
        }

    fun build(arr: Array<T>): SegmentTree<T>? {
        return buildHelper(0, arr.lastIndex, arr)
    }

    private fun buildHelper(left: Int, right: Int, arr: Array<T>): SegmentTree<T>? {
        if (left > right) return null
        val root = SegmentTree(left, right, arr[left], null, merge)
        if (left == right) return root
        val mid = (left + right) / 2
        root.left = buildHelper(left, mid, arr)
        root.right = buildHelper(mid + 1, right, arr)
        root.value = safeMerge(root.left?.value, root.right?.value)
        return root
    }

    private fun build(left: Int, right: Int, default: T?): SegmentTree<T>? {
        if (left > right) return null
        return SegmentTree(left, right, default, null, merge)
    }

    fun update(root: SegmentTree<T>, l: Int, r: Int, v: T) {
        if (l <= root.start && r >= root.end) {
            root.value = v
            root.lazy = safeMerge(root.lazy, v)
            return
        }
        // 动态开点线段树
        if (root.left == null || root.right == null) {
            val mid = root.mid
            if (root.left == null)
                root.left = build(root.start, mid, root.value)
            if (root.right == null)
                root.right = build(mid + 1, root.end, root.value)
        }
        pushDown(root)
        val mid = root.mid
        if (l <= mid) {
            update(root.left!!, l, r, v)
        }
        if (r > mid) {
            update(root.right!!, l, r, v)
        }
        root.value = merge(root.left!!.value!!, root.right!!.value!!)
    }

    private fun pushDown(root: SegmentTree<T>) {
        if (root.lazy == null) return
        root.left?.lazy = safeMerge(root.left?.lazy, root.lazy)
        root.right?.lazy = safeMerge(root.right?.lazy, root.lazy)
        root.left?.value = safeMerge(root.left?.value, root.lazy)
        root.right?.value = safeMerge(root.right?.value, root.lazy)
        root.lazy = null
    }

    fun update(root: SegmentTree<T>, index: Int, value: T) {
        if (root.start == index && root.end == index) {
            root.value = value
            return
        }
        // 动态开点线段树
        if (root.left == null || root.right == null) {
            val mid = root.mid
            if (root.left == null)
                root.left = build(root.start, mid, root.value)
            if (root.right == null)
                root.right = build(mid + 1, root.end, root.value)
        }
        val mid = root.mid
        if (index <= mid) {
            update(root.left!!, index, value)
            root.value = safeMerge(root.left!!.value, root.right!!.value)
        } else {
            update(root.right!!, index, value)
            root.value = safeMerge(root.left!!.value, root.right!!.value)
        }
    }

    fun query(root: SegmentTree<T>, left: Int, right: Int): T {
        if (left <= root.start && right >= root.end) {
            return root.value!!
        }
        // 动态开点线段树
        if (root.left == null || root.right == null) {
            val mid = root.mid
            if (root.left == null)
                root.left = build(root.start, mid, root.value)
            if (root.right == null)
                root.right = build(mid + 1, root.end, root.value)
        }
        pushDown(root)
        val mid = root.mid
        var ans: T? = null
        if (mid >= left) {
            ans = safeMerge(ans, query(root.left!!, left, right))
        }
        if (mid + 1 <= right) {
            ans = safeMerge(ans, query(root.right!!, left, right))
        }
        return ans!!
    }

    private fun safeMerge(a: T?, b: T?): T? {
        return when {
            a == null -> b
            b == null -> a
            else -> merge(a, b)
        }
    }

    // 注意lazy的更新策略
    private fun lazyMerge(a: T?, b: T?): T? {
        return b
    }
}