第 255 场周赛题解
2025/8/31大约 2 分钟
第 255 场周赛题解
Q1 1979. 找出数组的最大公约数
直接求就完了!
class Solution5850 {
fun findGCD(nums: IntArray): Int {
nums.sort()
return gcd(nums.max()!!, nums.min()!!)
}
}
/**
* GCD 最大公约数
* */
tailrec fun gcd(a: Int, b: Int): Int {
return if (b == 0) a else gcd(b, a % b)
}
Q2 1980. 找出不同的二进制字符串
直接遍历,筛出不在集合内的。
class Solution5851 {
fun findDifferentBinaryString(nums: Array<String>): String {
val n = nums[0].length
val set = nums.map {
var cur = 0
var step = 1
for (i in it.indices.reversed()) {
cur += (it[i] - '0') * step
step *= 2
}
cur
}
// set.joinToString().print()
for (i in 0 until (1 shl n)) {
if (i !in set) return i.toString(2).padStart(n, '0')
}
return ""
}
}
Q3 1981. 最小化目标值与所选元素的差
大于target的只需要一个最小值,因此每次可以把过多的数据从$Set$中$Remove$掉。其他的都交给$TreeSet$就好了,符合逻辑。
class Solution5852 {
fun minimizeTheDifference(mat: Array<IntArray>, target: Int): Int {
var set = TreeSet<Int>()
for (i in mat.indices) {
val nxtSet = TreeSet<Int>()
for (j in mat[0].indices) {
var large = Int.MAX_VALUE / 2
if (i == 0) {
nxtSet.add(mat[i][j])
} else {
set.forEach { s ->
val nxt = s + mat[i][j]
if (nxt > target) {
if (nxt < large) {
nxtSet.remove(large)
nxtSet.add(nxt)
large = nxt
}
} else {
nxtSet.add(nxt)
}
}
}
}
set = nxtSet
}
// set.print()
return minOf(
(set.ceiling(target) ?: Int.MAX_VALUE / 4) - target,
target - (set.floor(target) ?: Int.MIN_VALUE / 4)
)
}
}
Q4 1982. 从子集的和还原数组
有意思的题目,排序后,最大值和次大值得差$d$(非负值差),一定能保证$d$或$-d$在原数组中(可以通过反证法证明)。
- 若$d$是由两个更小的正数组合起来的,那么原次大值则不符合逻辑。
- 若$d$是有一个更大的正数与一个负数组合起来的,那么这个负数也会让原次大值不符合逻辑。
因此,可以$BackTrack$遍历使用$d$或$-d$来填充数组,看是否能构造出来。
每次构造,可以将原数组拆分成两部分$a$和$b$,并且对于所有的$b_{i} - a_{i} == d$,这样,根据我们选择的是$d$就将$a$数组进行下一轮迭代,选择的是$-d$就使用$b$数组进行下一轮迭代。直至迭代出一个结果位置。
该题主要是第一步不容易想到,之后的回溯其实就比较简单了。
class Solution5853 {
fun recoverArray(n: Int, sums: IntArray): IntArray {
sums.sort()
fun checkDiff(diff: Int, arr: ArrayList<Int>, pos: Boolean): ArrayList<Int> {
if (pos && diff !in arr) return arrayListOf()
if (!pos && -diff !in arr) return arrayListOf()
var l = 0
var r = 0
val s = arrayListOf<Int>()
val t = arrayListOf<Int>()
val used = BooleanArray(arr.size)
while (l in arr.indices) {
if (used[l]) {
l++
continue
}
s.add(arr[l])
used[l] = true
while (used[r] || arr[r] != arr[l] + diff) {
r++
if (r !in arr.indices) return arrayListOf<Int>()
}
t.add(arr[r])
used[r] = true
l++
}
return if (pos) s else t
}
val ans = ArrayList<Int>()
val tmp = ArrayList<Int>()
fun dfs(cur: ArrayList<Int>) {
if (cur.isEmpty() || ans.isNotEmpty()) return
if (tmp.size == n) {
ans.addAll(tmp)
return
}
val d = cur[cur.lastIndex] - cur[cur.lastIndex - 1]
tmp.add(d)
dfs(checkDiff(d, cur, true))
tmp.remove(d)
tmp.add(-d)
dfs(checkDiff(d, cur, false))
tmp.remove(-d)
}
dfs(ArrayList(sums.sorted()))
return ans.toIntArray()
}
}