第 271 场周赛题解

Q1 2103. 环和杆 (opens new window)

读题读了半天... 这文本描述和入参逻辑...

class SolutionA {
    fun countPoints(rings: String): Int {
        val map = HashMap<Char, HashSet<Char>>()
        var i = 0
        while (i in rings.indices) {
            val index = rings[i + 1]
            val c = rings[i]
            i += 2
            map[index] = map.getOrDefault(index, hashSetOf())
            map[index]!!.add(c)
        }
        return map.filterKeys { map[it]!!.size == 3 }.count()
    }
}

Q2 2104. 子数组范围和 (opens new window)

看数据范围，直接生算。

class SolutionB {
    fun subArrayRanges(nums: IntArray): Long {
        fun getBound(l: Int, r: Int): Long {
            var min = Long.MAX_VALUE
            var max = Long.MIN_VALUE
            for (i in l..r) {
                max = maxOf(max, nums[i].toLong())
                min = minOf(min, nums[i].toLong())
            }
            return max - min
        }

        var ans = 0L
        for (i in nums.indices) {
            for (j in i + 1 until nums.size) {
                if (i == j) continue
                ans += getBound(i, j)
            }
        }
        return ans
    }
}

Q3 2105. 给植物浇水 II (opens new window)

两个人给一株植物浇水是同时的，且耗时相同。然后取水不算时间... 模拟即可...

class SolutionC {
    fun minimumRefill(plants: IntArray, capacityA: Int, capacityB: Int): Int {
        var l = 0
        var r = plants.lastIndex
        var a = capacityA
        var b = capacityB
        var c = 0
        while (l <= r) {
            if (l == r) break
            if (l in plants.indices && a >= plants[l]) {
                a -= plants[l]
                l++
            } else {
                a = capacityA
                c++
                a -= plants[l]
                l++
            }
            if (r in plants.indices && b >= plants[r]) {
                b -= plants[r]
                r--
            } else {
                b = capacityB
                c++
                b -= plants[r]
                r--
            }
        }
        if (l == r) {
            if (b >= plants[l] || a >= plants[l]) {

            } else {
                c++
            }
        }
        return c
    }
}

Q4 2106. 摘水果 (opens new window)

先前缀和计算，向左走1~K和向右走1~K分别可获得多少水果。然后存在折返的情况（最多折返一次），折返前的路程消耗要*2。

class SolutionD {
    fun maxTotalFruits(fruits: Array<IntArray>, startPos: Int, k: Int): Int {
        val f = IntArray(200005)
        fruits.forEach {
            f[it[0]] = it[1]
        }
        val left = IntArray(k + 1)
        for (i in 1..k) {
            left[i] = left[i - 1]
            if (startPos - i in f.indices) {
                left[i] += f[startPos - i]
            }
        }
        val right = IntArray(k + 1)
        for (i in 1..k) {
            right[i] = right[i - 1]
            if (startPos + i in f.indices) {
                right[i] += f[startPos + i]
            }
        }

        var max = f[startPos]
        var ans = 0
        for (i in 1..k) {
            ans = f[startPos]
            ans += left[i]
            if (k - 2 * i in right.indices)
                ans += right[k - 2 * i]
            max = maxOf(max, ans)
        }
        for (i in 1..k) {
            ans = f[startPos]
            ans += right[i]
            if (k - 2 * i in left.indices)
                ans += left[k - 2 * i]
            max = maxOf(max, ans)
        }

        return max
    }
}