第 246 场周赛题解

Q1 1903. 字符串中的最大奇数 (opens new window)

找到最后一位为奇数的数字，可以直接$subString$到该位置，即所求结果。

class Solution {
    fun largestOddNumber(num: String): String {
        for (i in num.indices.reversed()) {
            if ((num[i] - '0') % 2 == 1) {
                return num.substring(0, i + 1)
            }
        }
        return ""
    }
}

Q2 1904. 你完成的完整对局数 (opens new window)

将分钟考向最近的$15$的整数倍，注意开始时间和结束时间的靠近方向不同。最后看下时间是否为负值，负数的话需要+上一整天。

class Solution1904 {
    fun numberOfRounds(startTime: String, finishTime: String): Int {
        val (sh, sm) = startTime.split(":").map { it.toInt() }
        val (fh, fm) = finishTime.split(":").map { it.toInt() }
        val s = sh * 60 + sm
        var f = fh * 60 + fm
        if (f < s) {
            f += 60 * 24
        }
        val rf = f / 15 * 15
        return maxOf(0, (rf - s)) / 15
    }
}

Q3 1905. 统计子岛屿 (opens new window)

使用$BFS$求解，注意每次岛屿2需要划出一整片岛屿一起判断，有任何一块陆地在岛屿1中是海洋，整体岛屿都不能计算到结果中。使用$DFS$超时.. 改成$BFS$才过，以后能用$BFS$都用$BFS$，不要用$DFS$。

class Solution5791 {
    fun countSubIslands(grid1: Array<IntArray>, grid2: Array<IntArray>): Int {
        // 方向
        val ori = arrayOf(
                intArrayOf(-1, 0),
                intArrayOf(0, -1),
                intArrayOf(0, 1),
                intArrayOf(1, 0)
        )

        fun bfs(i: Int, j: Int): ArrayList<IntArray> {
            val queue: Queue<IntArray> = LinkedList<IntArray>()
            queue.add(intArrayOf(i, j))
            grid2[i][j] = 2
            val ans = ArrayList<IntArray>()
            while (queue.isNotEmpty()) {
                val size = queue.size
                for (k in 0 until size) {
                    val item = queue.poll()
                    ans.add(item)
                    for (o in ori) {
                        val ni = item[0] + o[0]
                        val nj = item[1] + o[1]
                        if (ni in grid2.indices && nj in grid2[0].indices && grid2[ni][nj] == 1) {
                            grid2[ni][nj] = 2
                            queue.offer(intArrayOf(ni, nj))
                        }
                    }
                }
            }
            return ans
        }

        var ans = 0
        for (i in grid2.indices) {
            for (j in grid2[0].indices) {
                if (grid2[i][j] == 1) {
                    val land = bfs(i, j)
                    if (land.all { grid1[it[0]][it[1]] == 1 })
                        ans++
                }
            }
        }
        return ans
    }
}

Q4 1906. 查询差绝对值的最小值 (opens new window)

由于限定了数字的大小只能是$1..100$，可以以此为切入点。可以利用前缀和，计算出两个点之前的数组段包含的值。遇到这种$query$的题，我更习惯用线段树来处理，将$merge$逻辑传入即可。

线段树中的默认值是$BooleanArray$，长度$100$，默认值$false$。合并时就取$index$的或运算结果。每次$query$直接求解相应线段树内的值对应的$BooleanArray$，然后遍历它内部$true$值的最小间距即可。

class Solution1906 {
    fun minDifference(nums: IntArray, queries: Array<IntArray>): IntArray {
        val seg = SegmentTree<BooleanArray>(start = 0, end = nums.lastIndex, value = BooleanArray(101)) { a, b ->
            val ans = BooleanArray(101)
            for (i in ans.indices) {
                ans[i] = a[i] or b[i]
            }
            ans
        }
        for (i in nums.indices) {
            val arr = BooleanArray(101)
            arr[nums[i]] = true
            seg.update(seg, i, i, arr)
        }
        val ans = arrayListOf<Int>()
        queries.forEach {
            seg.query(seg, it[0], it[1]).also {
                var lst = -1
                var cur = Int.MAX_VALUE
                for (i in it.indices) {
                    if (!it[i]) continue
                    if (lst == -1) {
                        lst = i
                    } else {
                        cur = minOf(cur, i - lst)
                        lst = i
                    }
                }
                if (cur == Int.MAX_VALUE) ans.add(-1)
                else ans.add(cur)
            }
        }
        return ans.toIntArray()
    }
}