第 267 场周赛题解

Q1 2073. 买票需要的时间 (opens new window)

设k位置有T个票要买，当前位置之前的，都要拿走T次或拿完，之后的要拿T次。

class Solution2073 {
    fun timeRequiredToBuy(tickets: IntArray, k: Int): Int {
        val max = tickets[k]
        var ans = 0
        for (i in tickets.indices) {
            ans += if (i <= k) {
                minOf(max, tickets[i])
            } else {
                minOf(max - 1, tickets[i])
            }
        }
        return ans
    }
}

Q2 2074. 反转偶数长度组的节点 (opens new window)

链表不方便，就都先转成数组再做。

class Solution2074 {
    fun reverseEvenLengthGroups(head: ListNode?): ListNode? {
        val ans = ArrayList<Int>()
        val arr = head.toIntArray().toArrayList()
        var i = 0
        var l = 1
        while (i in arr.indices) {
            val add = arr.subList(i, minOf(arr.size, i + l))
            if (add.size % 2 == 0)
                ans.addAll(add.reversed())
            else ans.addAll(add)
            i += l
            l++
        }
        return ans.toIntArray().toListNode()
    }
}

Q3 2075. 解码斜向换位密码 (opens new window)

讨厌的题目类型，无聊的模拟，浪费时间，差评。

class Solution2075 {
    fun decodeCiphertext(encodedText: String, rows: Int): String {
        val cols = encodedText.length / rows
        val sb = StringBuilder()
        var i = 0
        var j = 0
        var preJ = -1
        while (j in 0 until cols) {
            if (i == 0) preJ = j
            sb.append(encodedText[j + i * cols])
            i++
            j++
            if (i !in 0 until rows) {
                i = 0
                j = preJ + 1
            }
        }
        return sb.toString().trimEnd()
    }
}

Q4 2076. 处理含限制条件的好友请求 (opens new window)

一眼就能看出是该用并查集，只是需要一个回退逻辑（或union前提前判断2个组的隶属）。

class Solution2076 {
    fun friendRequests(n: Int, restrictions: Array<IntArray>, requests: Array<IntArray>): BooleanArray {
        val ufs = UFS(n)
        return requests.map {
            ufs.union(it[0], it[1])
            restrictions.all {
                (ufs.find(it[0]) != ufs.find(it[1]))
            }.also {
                if (!it) {
                    // 回退至上一状态
                    ufs.reset()
                }
            }
        }.toBooleanArray()
    }
}