第 235 场周赛题解

Q1 1816. 截断句子 (opens new window)

Kotlin操作十分简单，需要合理利用工具。

class Solution1816 {
    fun truncateSentence(s: String, k: Int): String {
        return s.split(" ").take(k).joinToString(" ")
    }
}

Q2 1817. 查找用户活跃分钟数 (opens new window)

直接用$Map$记录每个用户的操作分钟$Set$，模拟给出结果即可。

class Solution1817 {
    fun findingUsersActiveMinutes(logs: Array<IntArray>, k: Int): IntArray {
        val map = HashMap<Int, HashSet<Int>>()
        logs.forEach {
            map[it[0]] = map.getOrDefault(it[0], hashSetOf())
            map[it[0]]!!.add(it[1])
        }
        val ans = IntArray(k)
        map.forEach { (i, set) ->
            if (set.size in ans.indices) {
                ans[set.size - 1]++
            }
        }
        return ans
    }
}

Q3 1818. 绝对差值和 (opens new window)

计算出每个元素替换后带来的绝对值变化差，使用$TreeSet$降低这个时间复杂度。然后遍历替换哪个元素使最终的结果最小即可。

class Solution5724 {
    fun minAbsoluteSumDiff(nums1: IntArray, nums2: IntArray): Int {
        val mod = 1000000007L
        var ans = 0L
        for (i in nums1.indices) {
            ans += abs(nums1[i] - nums2[i])
        }
        val ts = TreeSet<Int>()
        nums1.forEach {
            ts.add(it)
        }
        var res = ans
        for (i in nums1.indices) {
            if (ts.ceiling(nums2[i]) != null)
                res = minOf(res, ans - abs(nums1[i] - nums2[i]) + abs(ts.ceiling(nums2[i])!! - nums2[i]))
            if (ts.floor(nums2[i]) != null)
                res = minOf(res, ans - abs(nums1[i] - nums2[i]) + abs(ts.floor(nums2[i])!! - nums2[i]))
        }
        return (res % mod).toInt()
    }
}

Q4 1819. 序列中不同最大公约数的数目 (opens new window)

转变思路，查询$1..200000$中是给定数组中两个数的最大公约数。

class Solution1819 {
    fun countDifferentSubsequenceGCDs(nums: IntArray): Int {
        val seen = BooleanArray(200001) { false }
        nums.forEach { seen[it] = true }
        var ans = 0
        for (i in 1..200000) {
            var cur = -1
            for (j in i..200000 step i) {
                if (seen[j]) {
                    cur = if (cur == -1) j else gcd(cur, j)
                    if (cur == i) {
                        ans++
                        break
                    }
                }
            }
        }
        return ans
    }
}

fun gcd(a: Int, b: Int): Int {
    return if (b == 0) a else gcd(b, a % b)
}