第 234 场周赛题解

Q1 1805. 字符串中不同整数的数目 (opens new window)

不会写正则的我只好用$for$循环自己加，注意范围需要$BigInteger$，不然会越界。

class Solution1805 {
    fun numDifferentIntegers(word: String): Int {
        var cur = ""
        val ans = hashSetOf<BigInteger>()
        for (i in word.indices) {
            if (word[i] in '0'..'9') {
                cur += word[i]
            }
            if (word[i] !in '0'..'9' || i == word.lastIndex) {
                cur.toBigIntegerOrNull()?.let {
                    ans.add(it)
                }
                cur = ""
            }
        }
        return ans.size
    }
}

Q2 1806. 还原排列的最少操作步数 (opens new window)

看数据范围最大只有$1000$，于是直接硬模拟了。

class Solution1806 {
    fun reinitializePermutation(n: Int): Int {
        var cur = IntArray(n) { i -> i }
        val ans = cur.joinToString(",")
        val tmp = IntArray(n) { i -> i }
        var c = 0
        do {
            c++
            for (i in cur.indices) {
                if (i % 2 == 0) {
                    tmp[i] = cur[i / 2]
                } else {
                    tmp[i] = cur[n / 2 + (i - 1) / 2]
                }
            }
            cur = tmp.clone()
        } while (cur.joinToString(",") != ans)
        return c
    }
}

Q3 1807. 替换字符串中的括号内容 (opens new window)

正常栈的使用，无特殊点，也可以硬$replace$。

class Solution5714 {
    fun evaluate(s: String, knowledge: List<List<String>>): String {
        val map = HashMap<String, String>()
        knowledge.forEach {
            map[it[0]] = it[1]
        }
        val st = Stack<Char>()
        var ans = ""
        var meet = false
        for (i in s.indices) {
            if (s[i] == '(') {
                meet = true
                continue
            } else if (s[i] == ')') {
                meet = false
                ans += map.getOrDefault(st.joinToString(""), "?")
                st.clear()
                continue
            }
            if (meet) {
                st.add(s[i])
            } else {
                ans += s[i]
            }
        }
        return ans
    }
}

Q4 1808. 好因子的最大数目 (opens new window)

就是剪绳子原题... 需要注意数字范围较大，需要使用快速幂。

class Solution5716 {
    fun maxNiceDivisors(primeFactors: Int): Int {
        if (primeFactors == 1) return 1
        val mod = 1000000007L
        var ans = 1L
        val c = primeFactors / 3
        when (primeFactors % 3) {
            1 -> {
                ans = quickPower(3, (c - 1).toLong(), mod) * 4
            }
            2 -> {
                ans = quickPower(3, (c).toLong(), mod) * 2
            }
            0 -> {
                ans = quickPower(3, (c).toLong(), mod)
            }
        }
        return (ans % mod).toInt()
    }
}

fun quickPower(base: Long, pow: Long, m: Long = 1000000007L): Long {
    var res = 1L
    var a = base
    var b = pow
    while (b > 0) {
        if (b and 1L != 0L)
            res = res * a % m
        a = a * a % m
        b = b shr 1
    }
    return res
}