第 255 场周赛题解

Q1 1979. 找出数组的最大公约数 (opens new window)

直接求就完了！

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. 找出不同的二进制字符串 (opens new window)

直接遍历，筛出不在集合内的。

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. 最小化目标值与所选元素的差 (opens new window)

大于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. 从子集的和还原数组 (opens new window)

有意思的题目，排序后，最大值和次大值得差$d$（非负值差），一定能保证$d$或$-d$在原数组中（可以通过反证法证明）。

1. 若$d$是由两个更小的正数组合起来的，那么原次大值则不符合逻辑。
2. 若$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()
    }
}