第 254 场周赛题解

Q1 1967. 作为子字符串出现在单词中的字符串数目 (opens new window)

没啥说的，一行搞定。

class Solution5843 {
    fun numOfStrings(patterns: Array<String>, word: String): Int {
        return patterns.count { it in word }
    }
}

Q2 1968. 构造元素不等于两相邻元素平均值的数组 (opens new window)

最大最小值交替拜访，保证中间元素严格大于或小于左右两个元素的平均值。

class Solution5832 {
    fun rearrangeArray(nums: IntArray): IntArray {
        val ans = IntArray(nums.size)
        var left = 0
        var right = nums.size - 1
        var cur = 0
        nums.sort()
        while (cur in nums.indices) {
            if (cur % 2 == 0) {
                ans[cur] = nums[left]
                left++
            } else {
                ans[cur] = nums[right]
                right--
            }
            cur++
        }
        return ans
    }
}

Q3 1969. 数组元素的最小非零乘积 (opens new window)

看示例可以看出来，最小乘机是 1个 $2^p - 1$ 乘以 $(2^p - 1)/2$ 个 $2^p - 2$，剩下的部分都是$1$。还需要注意由于幂次非常大，要注意使用$quickPower$并在计算过程中就取$mod$。

class Solution5844 {
    fun minNonZeroProduct(p: Int): Int {
        val mod = 1000000007L
        val a = (1L shl p) - 1L
        val b = a - 1L
        val c = b / 2L
        return (((a % mod) * quickPower(b % mod, c)) % mod).toInt()
    }
}

/**
 * 快速幂
 * 计算 base 的 pow 次方，并且求其 %m 后的结果
 * */
fun quickPower(base: Long, pow: Long, m: Long = 1000000007L): Long {
    var res = 1L
    var a = base
    var b = pow
    while (b > 0) {
        if (b and 1L != 0L)
            res = res * a % m
        a = a * a % m
        b = b shr 1
    }
    return res
}

Q4 1970. 你能穿过矩阵的最后一天 (opens new window)

理解题意后，题目就很简单了，比$Q3$容易理解。

直接二分看最后一天第一行到最后一行还有通路是哪一天即可，$多源BFS$+$二分$。

这里最开始$Key$使用字符串集合，导致超时。能用数组还是用数组，快速访问。

class Solution5845 {
    fun latestDayToCross(row: Int, col: Int, cells: Array<IntArray>): Int {
        val dir4 = arrayOf(
                intArrayOf(0, 1),
                intArrayOf(0, -1),
                intArrayOf(1, 0),
                intArrayOf(-1, 0)
        )

        fun check(mid: Int): Boolean {
            val block = Array<BooleanArray>(row) { BooleanArray(col) }
            for (i in 0 until mid) {
                block[cells[i][0] - 1][cells[i][1] - 1] = true
            }

            val seen = Array<BooleanArray>(row) { BooleanArray(col) }
            val queue: Queue<IntArray> = LinkedList<IntArray>()
            for (j in 0 until col) {
                if (!block[0][j]) {
                    queue.offer(intArrayOf(0, j))
                    seen[0][j] = true
                }
            }
            while (queue.isNotEmpty()) {
                val size = queue.size
                for (i in 0 until size) {
                    val item = queue.poll()
                    if (item[0] == row - 1) {
                        return true
                    }
                    dir4.forEach {
                        val next = intArrayOf(item[0] + it[0], item[1] + it[1])
                        if (next[0] in 0 until row
                                && next[1] in 0 until col
                                && !block[next[0]][next[1]]
                                && !seen[next[0]][next[1]]) {
                            queue.offer(next)
                            seen[next[0]][next[1]] = true
                        }
                    }
                }
            }
            return false
        }

        var left = 0
        var right = cells.lastIndex
        while (left + 1 < right) {
            val mid = (left + right).ushr(1)
            when {
                check(mid) -> left = mid
                else -> right = mid
            }
        }
        return if (check(right)) {
            right
        } else {
            left
        }
    }
}