第 265 场周赛题解

Q1 2057. 值相等的最小索引 (opens new window)

纯签到。

class Solution2057 {
    fun smallestEqual(nums: IntArray): Int {
        for (i in nums.indices) {
            if (i % 10 == nums[i])
                return i
        }
        return -1
    }
}

Q2 2058. 找出临界点之间的最小和最大距离 (opens new window)

链表写着难受，就直接先转成ArrayList，之后就是简单操作了。把极值点塞到一个list中，最大值就是头尾差，最小值就是相邻两个点差的最小值。注意如果极值点少于2个，直接给-1即可。

class Solution2058 {
    fun nodesBetweenCriticalPoints(head: ListNode?): IntArray {
        val arr = head.toIntArray()
        val l = arrayListOf<Int>()
        for (i in arr.indices) {
            if (i == 0 || i == arr.lastIndex) continue
            if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
                l.add(i)
            } else if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {
                l.add(i)
            }
        }
        if (l.size < 2) return intArrayOf(-1, -1)
        var min = arr.size
        val max = l.last() - l.first()
        for (i in l.indices) {
            if (i == 0) continue
            min = minOf(min, l[i] - l[i - 1])
        }
        return intArrayOf(min, max)
    }
}

Q3 2059. 转化数字的最小运算数 (opens new window)

直接BFS模拟，比Q2要简单。遇到过的数字可以不用再计算，且超过1..1000范围的也不用再处理。

class Solution2059 {
    fun minimumOperations(nums: IntArray, start: Int, goal: Int): Int {
        val queue: Queue<Int> = LinkedList<Int>()
        queue.add(start)
        var step = 0
        val seen = HashSet<Int>()
        while (queue.isNotEmpty()) {
            val size = queue.size
            step++
            for (k in 0 until size) {
                val item = queue.poll()
                if (item == goal) return step
                if (item in seen) continue
                if (item !in seen) seen.add(item)
                if (item !in 0..1000) continue
                nums.forEach {
                    queue.offer(item + it)
                    queue.offer(item - it)
                    queue.offer(item xor it)
                }
            }
        }
        return -1
    }
}

Q4 2060. 同源字符串检测 (opens new window)

比较难的题目，但是冷静下来并不是现有知识储备做不出来的题目。两个字符串从左向右比较即可。DFS进行搜索，关键变量是两个字符串比较到的index及当前两个字符串仍剩余的通配符数量。

之后按照比较逻辑进行深度搜索即可。

1. 双方都有通配符，互相消耗至一方为0为止
2. 若有一方是数字，将数字转换为通配符（转换1~3位）
3. 若双方都没有数字，减少有通配符一方的通配符，若都没有通配符，则进行比较是否相等

class Solution2060 {
    fun possiblyEquals(s1: String, s2: String): Boolean {
        val seen = HashSet<String>()

        var ans = false

        fun dfs(i: Int, j: Int, rest1: Int, rest2: Int) {
            if (ans) return
            val key = "$i,$j,$rest1,$rest2"
            if (key in seen) return
            seen.add(key)

            // 刚好匹配完成
            if (i == s1.length && j == s2.length && rest1 == 0 && rest2 == 0) {
                ans = true
                return
            }

            // 有一方有剩余没用完，则互相消耗掉
            if (rest1 != 0 && rest2 != 0) {
                val min = minOf(rest1, rest2)
                dfs(i, j, rest1 - min, rest2 - min)
                return
            }

            // 无可消耗，需要字符匹对进行判断
            if (rest1 == 0 && rest2 == 0 && i in s1.indices && s1[i] in 'a'..'z' && j in s2.indices && s2[j] in 'a'..'z') {
                if (s1[i] == s2[j]) {
                    dfs(i + 1, j + 1, 0, 0)
                } else return
            } else if (rest1 > 0 && j in s2.indices && s2[j] in 'a'..'z') {
                return dfs(i, j + 1, rest1 - 1, 0)
            } else if (rest2 > 0 && i in s1.indices && s1[i] in 'a'..'z') {
                return dfs(i + 1, j, 0, rest2 - 1)
            } else if (j in s2.indices && s2[j] in '1'..'9') {
                var rest = 0
                for (k in 0 until 3) {
                    if (j + k in s2.indices && s2[j + k].isDigit()) {
                        rest = rest * 10 + (s2[j + k] - '0')
                        dfs(i, j + k + 1, rest1, rest2 + rest)
                    } else break
                }
                return
            } else if (i in s1.indices && s1[i] in '1'..'9') {
                var rest = 0
                for (k in 0 until 3) {
                    if (i + k in s1.indices && s1[i + k].isDigit()) {
                        rest = rest * 10 + (s1[i + k] - '0')
                        dfs(i + k + 1, j, rest1 + rest, rest2)
                    } else break
                }
                return
            } else {
                return
            }
        }

        dfs(0, 0, 0, 0)
        return ans
    }
}