第 239 场周赛题解
2025/8/31大约 3 分钟
第 239 场周赛题解
Q1 1848. 到目标元素的最小距离
普通暴力。
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. 将字符串拆分为递减的连续值
$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. 邻位交换的最小次数
本题的最终状态其实是求$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. 包含每个查询的最小区间
利用线段树模板!先将区间按照长度排序,然后依次更新线段树的值。最后查询一遍即可,注意线段树的$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
}
}