第 223 场周赛题解

Q1 1720. 解码异或后的数组 (opens new window)

$xor$的特性，顺序遍历即可。

class Solution1720 {
    fun decode(encoded: IntArray, first: Int): IntArray {
        val n = encoded.size
        val ans = IntArray(n + 1)
        ans[0] = first
        for (i in 1 until ans.size) {
            ans[i] = ans[i - 1] xor encoded[i - 1]
        }
        return ans
    }
}

Q2 1721. 交换链表中的节点 (opens new window)

标准做法是三指针，第一个指针每次后移，第二个指针前$k$次后移，第三个指针前$k$次不移动，之后每次都移动。直到第一个指针指向$null$时，可以证明此时第二个和第三个指针指向我们要交换的两个位置。这时用普通的链表交换即可。

class Solution1721 {
    fun swapNodes(head: ListNode?, k: Int): ListNode? {
        if (head == null) {
            return null
        }
        if (head.next == null) {
            return head
        }
        var cur: ListNode? = head
        var slow: ListNode? = head
        var fast: ListNode? = head
        var index = 1
        while (cur?.next != null) {
            if (index < k) {
                slow = slow?.next
            } else {
                fast = fast?.next
            }
            cur = cur.next
            index++
        }
        val slowValue = slow?.`val` ?: 0
        slow?.`val` = fast?.`val` ?: 0
        fast?.`val` = slowValue
        return head
    }
}

此外，该题目没有要求修改的是原链表，可以直接把整个链表改成数组，修改后再重新构建链表。

时间复杂度同样都为$O(n)$。

class Solution1721 {
    fun swapNodes(head: ListNode?, k: Int): ListNode? {
        val arr = head.toIntArray()
        val n = arr.size
        val temp = arr[k - 1]
        arr[k - 1] = arr[n - k + 1]
        arr[n - k + 1] = temp
        return arr.toListNode()
    }
}

fun ListNode?.toIntArray(): IntArray {
    if (this == null) return intArrayOf()
    var cur = this
    val ans = arrayListOf<Int>()
    while (cur != null) {
        ans.add(cur.`val`)
        cur = cur.next
    }
    return ans.toIntArray()
}

fun IntArray.toListNode(): ListNode {
    var node = ListNode(this[0])
    val head = node
    for (i in 1 until this.size) {
        val cur = ListNode(this[i])
        node.next = cur
        node = cur
    }
    return head
}

Q3 1722. 执行交换操作后的最小汉明距离 (opens new window)

有意思的题目，首先明确题意，交换顺序和次数都是任意，那么对于$[[1,2],[2,3]]$这样的组合来说，1、2、3位置都可以任意交换，即只要是一组的，位置可以任选组内的位置。

根据这一性质，比较容易想到使用并查集来分组，然后一组内的target数据和source数据计算差异的数值。总和即为所求汉明距离。

class Solution1722 {
    fun minimumHammingDistance(source: IntArray, target: IntArray, allowedSwaps: Array<IntArray>): Int {
        val n = source.size
        val ufs = TypedUFS<Int>(n)
        allowedSwaps.forEach {
            ufs.union(it[0], it[1])
        }
        val map = HashMap<Int, HashMap<Int, Int>>()
        for (i in source.indices) {
            val key = ufs.typedFind(i)
            map[key] = map.getOrDefault(key, hashMapOf())
            map[key]!![source[i]] = map[key]!!.getOrDefault(source[i], 0) + 1
            map[key]!![target[i]] = map[key]!!.getOrDefault(target[i], 0) - 1
        }
        var ans = 0
        for (key in map.keys) {
            map[key]!!.forEach { (k, v) ->
                ans += maxOf(v, 0)
            }
        }
        return ans
    }
}

class TypedUFS<T>(var n: Int = 0) {
    private val parent = IntArray(n) { i -> i }
    private val rank = IntArray(n)

    val map = hashMapOf<T, Int>()
    private val rev = hashMapOf<Int, T>()
    private var total = 0

    fun typedFind(key: T): Int {
        var x = total
        if (map.containsKey(key)) {
            x = map[key]!!
        } else {
            map[key] = total
            rev[total] = key
            total++
        }
        if (x != parent[x]) {
            val origin = parent[x]
            parent[x] = typedFind(rev[parent[x]]!!)
        }
        return parent[x]
    }

    fun union(x: T, y: T, value: Double = 1.0): Boolean {
        val px = typedFind(x)
        val py = typedFind(y)
        if (px == py) {
            return false
        }
        when {
            rank[px] > rank[py] -> {
                parent[py] = px
            }
            rank[px] < rank[py] -> {
                parent[px] = py
            }
            else -> {
                parent[px] = py
                rank[px]++
            }
        }
        return true
    }

    fun getCount(): Int {
        val keys = hashSetOf<Int>()
        map.keys.forEach {
            keys.add(typedFind(it))
        }
        return keys.size
    }
}

Q4 1723. 完成所有工作的最短时间 (opens new window)

又是经典的状态压缩+DP的题目。先观察数据范围$1 <= k <= jobs.length <= 12$，则工作组合的状态数最大为$2^{12}$。因此可以把每个状态的消耗时间计算出来。当一个状态分配给多一个人工作时，状态值变为子状态和：

$$dp[i][state] = minOf(\underbrace{maxOf(dp[i - 1][state - subState], sum[subState])}_{subState\subseteq{state}})$$

class Solution1723 {
    fun minimumTimeRequired(jobs: IntArray, k: Int): Int {
        val n = jobs.size
        val dp = Array(k + 1) { IntArray(1 shl n) { Int.MAX_VALUE } }
        dp[0][0] = 0
        val sum = IntArray(1 shl n)
        for (i in 0 until (1 shl n)) {
            for (j in 0 until n) {
                if (i and (1 shl j) != 0) {
                    sum[i] += jobs[j]
                }
            }
        }
        for (i in 1..k) {
            for (state in 0 until (1 shl n)) {
                var subState = state
                while (subState > 0) {
                    dp[i][state] = minOf(dp[i][state], maxOf(dp[i - 1][state - subState], sum[subState]))
                    subState = (subState - 1) and state
                }
            }
        }
        return dp[k][(1 shl n) - 1]
    }
}