第 244 场周赛题解

Q1 1886. 判断矩阵经轮转后是否一致 (opens new window)

主要是旋转和比较的方法，刚好可以补充一波矩阵相关操作的工具类。

矩阵值完全相同也可以用工具类比较~

class Solution1886 {
    fun findRotation(mat: Array<IntArray>, target: Array<IntArray>): Boolean {
        val matrix = mat.toMatrix()
        for (c in 0 until 4) {
            matrix.rotate()
            if (matrix == target.toMatrix()) {
                return true
            }
        }
        return false
    }
}

// n行 m列 矩阵
class Matrix(val n: Int, val m: Int, val matrix: Array<IntArray>) {

    override fun toString(): String {
        return matrix.joinToString { it.joinToString() }
    }

    override fun equals(other: Any?): Boolean {
        if (other !is Matrix) return false
        return this.toString() == other.toString()
    }

    override fun hashCode(): Int {
        var result = n
        result = 31 * result + m
        result = 31 * result + matrix.contentDeepHashCode()
        return result
    }
}

// 向右旋转90°
fun Matrix.rotate() {
    if (n != m) {
        println("Rotate Error")
    }
    for (i in 0 until (n + 1) / 2) {
        for (j in 0 until n / 2) {
            val temp = matrix[n - 1 - j][i]
            matrix[n - 1 - j][i] = matrix[n - 1 - i][n - j - 1]
            matrix[n - 1 - i][n - j - 1] = matrix[j][n - 1 - i]
            matrix[j][n - 1 - i] = matrix[i][j]
            matrix[i][j] = temp
        }
    }
}

fun Array<IntArray>.toMatrix(): Matrix {
    val n = this.size
    val m = this[0].size
    return Matrix(n, m, this)
}

Q2 1887. 使数组元素相等的减少操作次数 (opens new window)

最开始没看懂题意... 后来才发现就是变成次大，那每个数字变化的次数就是作为$Set$集合中该数字大小的次序。

也可以直接逆序排序后，单次遍历判断值是否有变小，若有变小则之前所有已遍历数据都要增加$1$次操作。

class Solution1887 {
    fun reductionOperations(nums: IntArray): Int {
        val set = HashSet<Int>()
        nums.forEach {
            set.add(it)
        }
        val map = HashMap<Int, Int>()
        set.sorted().mapIndexed { index, i -> map[i] = index }
        return nums.sumBy { map[it]!! }
    }
}

Q3 1888. 使二进制字符串字符交替的最少反转次数 (opens new window)

滑动窗口，将字符串头删除塞到尾部，就相当于字符串乘以$2$，然后取中间长度为$n$的部分。然后问题转化为求窗口中的部分尽量多的满足交替字符串的次数即可。

$a0、a1、b0、b1$分别记为奇数位、偶数位为$0$或$1$的总次数，最小值即$minOf(n - a0 - b1, n - a1 - b0)$。

class Solution1888 {
    fun minFlips(s: String): Int {
        val n = s.length
        val t = s + s
        var a0 = 0
        var a1 = 0
        var b0 = 0
        var b1 = 0
        var ans = Int.MAX_VALUE
        for (i in t.indices) {
            if (t[i] == '0') if (i % 2 == 0) a0++ else b0++
            else if (i % 2 == 0) a1++ else b1++

            if (i >= n) {
                if (t[i - n] == '0') if ((i - n) % 2 == 0) a0-- else b0--
                else if ((i - n) % 2 == 0) a1-- else b1--
            }
            ans = minOf(ans, minOf(n - a0 - b1, n - a1 - b0))
        }
        return ans
    }
}

Q4 1889. 装包裹的最小浪费空间 (opens new window)

二分查找，箱子的总数范围小于$10^5$，则可以以箱子作为循环主体，每个箱子可以增加多少空间。要注意$Int * Int$的数据范围，要提前变为$Long$类型，不然会越界... 因为这个怒吃两发$WA$...

class Solution1889 {
    fun minWastedSpace(packages: IntArray, boxes: Array<IntArray>): Int {
        val mod = 1000000007L
        packages.sort()
        val sum = packages.map { it.toLong() }.sum()
        var ans = Long.MAX_VALUE
        for (i in boxes.indices) {
            val it = boxes[i].sorted()
            if (it.last() < packages.last()) {
                continue
            }
            var preIndex = 0
            var tmp = 0L
            it.forEach {
                val index = packages.biLastIndexOf { item -> item <= it }
                tmp += (index - preIndex + 1) * it.toLong()
                preIndex = index + 1
                if (preIndex == packages.size) return@forEach
            }
            ans = minOf(ans, tmp - sum)
        }
        return if (ans == Long.MAX_VALUE) -1 else (ans % mod).toInt()
    }
}

fun IntArray.biLastIndexOf(func: (Int) -> Boolean): Int {
    var left = 0
    var right = this.lastIndex
    while (left + 1 < right) {
        val mid = (left + right).ushr(1)
        when {
            func(this[mid]) -> left = mid
            else -> right = mid
        }
    }
    return when {
        func(this[right]) -> right
        func(this[left]) -> left
        else -> -1
    }
}