第 268 场周赛题解

Q1 2078. 两栋颜色不同且距离最远的房子 (opens new window)

签到。

class Solution2078 {
    fun maxDistance(colors: IntArray): Int {
        var ans = 0
        for (i in 0 until colors.lastIndex) {
            for (j in i + 1 until colors.size) {
                if (colors[i] != colors[j]) {
                    ans = maxOf(ans, j - i)
                }
            }
        }
        return ans
    }
}

Q2 2079. 给植物浇水 (opens new window)

简单模拟。

class Solution2079 {
    fun wateringPlants(plants: IntArray, capacity: Int): Int {
        var cur = capacity
        var ans = 0
        for (i in plants.indices) {
            if (cur >= plants[i]) {
                ans++
                cur -= plants[i]
            } else {
                cur = capacity - plants[i]
                ans += i * 2 + 1
            }
        }
        return ans
    }
}

Q3 2080. 区间内查询数字的频率 (opens new window)

直接用线段树会超时，还是先按数字拆分下，再用TreeMap二分处理。

class RangeFreqQuery(arr: IntArray) {

    val map = HashMap<Int, TreeMap<Int, Int>>()

    init {
        for (i in arr.indices) {
            if (arr[i] !in map.keys) {
                map[arr[i]] = TreeMap<Int, Int>()
            }
            val index = map[arr[i]]!!.size
            map[arr[i]]!![i] = index + 1
        }
    }

    fun query(left: Int, right: Int, value: Int): Int {
        val tm = map[value]
        if (tm.isNullOrEmpty()) return 0
        val r = tm.floorKey(right)
        val l = tm.ceilingKey(left)
        if (r == null || l == null) return 0
        return tm[r]!! - tm[l]!! + 1
    }

}

Q4 2081. k 镜像数字的和 (opens new window)

从小到大构造K进制回文串，并将其中满足十进制也是回文的进行相加即可。

class Solution2081 {
    fun kMirror(k: Int, n: Int): Long {
        var ans = 0L
        var cur = 0
        val queue: Queue<ArrayList<Int>> = LinkedList<ArrayList<Int>>()
        for (i in 1 until k) {
            queue.offer(arrayListOf(i))
        }
        while (queue.isNotEmpty()) {
            val size = queue.size
            for (i in 0 until size) {
                val item = queue.poll()
                val valK = item.joinToString("")
                val val10 = valK.toLong(k)
                if (val10.toString() == val10.toString().reversed()) {
                    ans += val10
                    cur++
                    if (cur == n) return ans
                }

                if (item.size % 2 == 0) {
                    for (j in 0 until k) {
                        val next = item.clone() as ArrayList<Int>
                        next.add(item.size / 2, j)
                        queue.offer(next)
                    }
                } else {
                    item.add(item.size / 2, item[item.size / 2])
                    queue.offer(item)
                }
            }
        }
        return 0L
    }
}