第 279 场周赛题解 (opens new window)

Q1 2164. 对奇偶下标分别排序 (opens new window)

模拟，还有就是总数可能是奇数，还要多判断一个... 这里还吃个WA。

class SolutionA {
    fun sortEvenOdd(nums: IntArray): IntArray {
        val a = ArrayList<Int>()
        val b = ArrayList<Int>()
        for (i in nums.indices) {
            if (i % 2 == 0) {
                a.add(nums[i])
            } else {
                b.add(nums[i])
            }
        }
        a.sort()
        b.sortDescending()
        val ans = ArrayList<Int>()
        for (i in b.indices) {
            ans.add(a[i])
            ans.add(b[i])
        }
        if (a.size > b.size) {
            ans.add(a.last())
        }
        return ans.toIntArray()
    }
}

Q2 2165. 重排数字的最小值 (opens new window)

模拟，负数就直接数字从大到小排，正数先塞一个非0最小，然后塞完0，余下的从小到大排。

class SolutionB {
    fun smallestNumber(num: Long): Long {
        if (num == 0L) return num
        val set = ArrayList<Int>()
        val str = num.toString()
        if (num < 0) {
            for (i in str.indices) {
                if (i == 0) continue
                set.add(str[i] - '0')
            }
            return -set.sortedDescending().joinToString("").toLong()
        }
        if (num > 0) {
            for (i in str.indices) {
                set.add(str[i] - '0')
            }
            set.sort()
            val c0 = set.count { it == 0 }
            val ans = set.sorted().joinToString("").trimStart('0')
            val arr = ArrayList<Char>()
            arr.addAll(ans.toCharArray().toList())
            repeat(c0) {
                arr.add(1, '0')
            }
            return arr.joinToString("").toLong()
        }
        return 0L
    }
}

Q3 2166. 设计位集 (opens new window)

核心就是$flip$操作并不真正修改每一位的值，而是记录变量。由于给出提示toString操作不会很多，所以可以每次遍历完整数组。

class Bitset(val size: Int) {

    val b = BooleanArray(size) { false }
    var flip = false
    var sum = 0

    fun fix(idx: Int) {
        if (!(flip xor b[idx])) {
            b[idx] = !b[idx]
            sum++
        }
    }

    fun unfix(idx: Int) {
        if (flip xor b[idx]) {
            b[idx] = !b[idx]
            sum--
        }
    }

    fun flip() {
        flip = !flip
        sum = size - sum
    }

    fun all(): Boolean {
        return sum == size
    }

    fun one(): Boolean {
        return sum > 0
    }

    fun count(): Int {
        return sum
    }

    override fun toString(): String {
        val sb = StringBuilder()
        for (i in 0 until size) {
            sb.append(if (b[i] xor flip) '1' else '0')
        }
        return sb.toString()
    }

}

Q4 2167. 移除所有载有违禁货物车厢所需的最少时间 (opens new window)

少了边界条件，全部都用2单位时间来拆，结果一直WA在倒数第二个Case，自己看代码看不出来... 闹心。

从右向左遍历，把每一位归右侧扔 or 单独拆的最小值计算出来，再与归左侧扔计算和的最小值即可。

class SolutionD {
    fun minimumTime(s: String): Int {
        val n = s.length
        val dp = IntArray(n + 1)
        dp[n] = 0
        for (i in s.indices.reversed()) {
            dp[i] = minOf(n - i, if (s[i] == '1') dp[i + 1] + 2 else dp[i + 1])
        }
        var ans = Int.MAX_VALUE
        for (i in 0 until n) {
            ans = minOf(ans, i + dp[i])
        }
        return ans
    }
}