第 278 场周赛题解 (opens new window)

Q1 2154. 将找到的值乘以 2 (opens new window)

暴力。

class SolutionA {
    fun findFinalValue(nums: IntArray, original: Int): Int {
        var c = original
        while (c in nums) {
            c *= 2
        }
        return c
    }
}

Q2 2155. 分组得分最高的所有下标 (opens new window)

前缀和后缀和。这里不是求最大值，而是下标，还得倒一步。

class SolutionB {
    fun maxScoreIndices(nums: IntArray): List<Int> {
        val left = IntArray(nums.size + 1)
        val right = IntArray(nums.size + 1)
        for (i in 1..nums.size) {
            left[i] = left[i - 1]
            if (nums[i - 1] == 0) {
                left[i]++
            }
        }
        for (i in nums.indices.reversed()) {
            right[i] = right[i + 1]
            if (nums[i] == 1) {
                right[i]++
            }
        }

        val ans = ArrayList<Int>()
        var max = 0
        for (i in left.indices) {
            if (left[i] + right[i] > max) {
                max = left[i] + right[i]
                ans.clear()
                ans.add(i)
            } else if (left[i] + right[i] == max) {
                ans.add(i)
            }
        }
        return ans
    }
}

Q3 2156. 查找给定哈希值的子串 (opens new window)

模拟。注意就是power的k次方mod可以提前求好。

class SolutionC {
    fun subStrHash(s: String, power: Int, modulo: Int, k: Int, hashValue: Int): String {
        var cur = 0L
        var l = 0
        var ans = ""
        val powerMod = quickPower(power.toLong(), k.toLong(), modulo.toLong())
        for (i in s.indices.reversed()) {
            cur *= power
            cur += s[i] - 'a' + 1
            l++
            if (l > k) {
                cur -= (s[i + k] - 'a' + 1) * powerMod
                cur %= modulo
                cur = (cur + modulo) % modulo
            }
            if (l >= k && cur % modulo == hashValue.toLong()) {
                ans = s.substring(i, i + k)
            }
            cur %= modulo
        }
        return ans
    }
}

Q4 2157. 字符串分组 (opens new window)

一看就是并查集，但是遍历需要用可变换的字符串，而不是剩余字符串做匹配，不然复杂度是$O(n^2)$。

class SolutionD {
    fun groupStrings(words: Array<String>): IntArray {
        val map = HashMap<Int, Int>()
        words.forEach {
            var c = 0
            for (i in it.indices) {
                c += 1 shl (it[i] - 'a')
            }
            map[c] = map.getOrDefault(c, 0) + 1
        }

        val ufs = TypedUFS<Int>(words.size)
        map.keys.forEach {
            ufs.union(it, it)
        }

        fun union(i: Int, j: Int) {
            if (i == j) return
            if (map.getOrDefault(j, 0) == 0) return
            ufs.union(i, j)
        }

        // mask 第i位变化 第j位变化
        for (mask in map.keys) {
            for (i in 0 until 26) {
                // 令第i位变化
                union(mask, mask xor (1 shl i))
                for (j in 0 until 26) {
                    // 注意 i位j位的变化，不可以同时为增加 or 减少
                    if (mask shr i and 1 != mask shr j and 1) {
                        union(mask, (mask xor (1 shl i)) xor (1 shl j))
                    }
                }
            }
        }
        val seen = HashSet<Int>()
        var c = 0
        val maxArr = IntArray(map.keys.size)
        for (i in map.keys) {
            val find = ufs.typedFind(i)
            if (find !in seen) {
                seen.add(ufs.typedFind(i))
                c++
            }
            maxArr[find] += map[i]!!
        }
        return intArrayOf(c, maxArr.maxOrNull()!!)
//        return intArrayOf(c, maxArr.max()!!)
    }
}