本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 加入知识星球提问！

往期回顾：LeetCode 单周赛第 347 场 · 二维空间上的 LIS 最长递增子序列问题周赛 348 概览

T1. 最小化字符串长度（Medium）

(资料图片仅供参考)

标签：散列表、计数

T2. 半有序排列（Easy）

标签：散列表

T3. 查询后矩阵的和（Medium）

标签：散列表

T4. 统计整数数目（Hard）

标签：数位 DP、构造T1. 最小化字符串长度（Medium）

https://leetcode.cn/problems/minimize-string-length/

题解（散列表 + 计数）

无论每个字符有多少，最终每个字符都会剩下 1 个，因此只需要记录字符种类数：

class Solution {    fun minimizedStringLength(s: String): Int {        return s.toHashSet().size    }}

复杂度分析：

时间复杂度：$O(n)$空间复杂度：$O(n)$T2. 半有序排列（Easy）

https://leetcode.cn/problems/semi-ordered-permutation/

题解（模拟）

我们只需要考虑 1 和 n，每次操作可以把 1 向左边移动一位，或者将 n 向右移动一位，但是考虑到 1 和 n 的移动方向有交叉时，要减少一次操作次数。

class Solution {    fun semiOrderedPermutation(nums: IntArray): Int {        val n = nums.size        val i = nums.indexOf(1)        val j = nums.indexOf(n)        return i + (n - 1 - j) - if (i > j) 1 else 0    }}

复杂度分析：

时间复杂度：$O(n)$空间复杂度：$O(1)$T3. 查询后矩阵的和（Medium）

https://leetcode.cn/problems/sum-of-matrix-after-queries/

题解（散列表）

这道题需要一点逆向思维，越靠后的操作会覆盖越靠前的操作，所以我们逆序遍历，并维护：

rowSet：操作过的行号（逆序）colSet：操作过的列号（逆序）

那么，在每次行操作中可以填充的次数就是该行中没有被操作过的列数，而每次行操作中可以填充的次数就是该列中没有被操作过的行数。

class Solution {    fun matrixSumQueries(n: Int, queries: Array): Long {        var ret = 0L        val visitSet = Array(2) { HashSet() }        for (query in queries.reversed()) {            val type = query[0]            val index = query[1]            val value = query[2]            // 重复操作            if (visitSet[type].contains(index)) continue            // 这次操作可以填充的数字            ret += 1L * (n - visitSet[type xor 1].size) * value            visitSet[type].add(index)        }        return ret    }}

复杂度分析：

时间复杂度：$O(q)$空间复杂度：$O(n + q)$T4. 统计整数数目（Hard）

https://leetcode.cn/problems/count-of-integers/

题解（数位 DP）

1、定义 f(n) 表示 [1,n] 中满足条件的好整数，那么原问题的解为：f(num2) - f(num1) + if(num1)

2、使用数位 DP：

以 n = 234 为例

isLimit：高位是否约束当前位。例如百位填 2 时，十位就受到高位约束只能填 0-3，否则可以填 0-9isNum：高位是否为数字，这题不要考虑前导 0

3、定义 dfs(i:Int, sum:Int, isLimit:Int) 表示子问题中满足条件的个数

4、在备忘录中，isLimit 为 true 的子问题只会递归 1 次，可以不为 isLimit 提供记忆化维度：

class Solution {    private val MOD = 1000000007    fun count(num1: String, num2: String, min_sum: Int, max_sum: Int): Int {        return count(num2, min_sum, max_sum) - count(num1, min_sum, max_sum) + check(num1, min_sum, max_sum)    }    private fun check(num: String, min_sum: Int, max_sum: Int): Int {        var sum = 0        for (c in num) sum += c - "0"        return if (sum in min_sum..max_sum) 1 else 0    }    // 数位 DP    private fun count(num: String, min_sum: Int, max_sum: Int): Int {        fun dfs(num: String, memo: Array, i: Int, sum: Int, isLimit: Boolean): Int {            // 终止条件            if (sum > max_sum) return 0            if (i == num.length) return if (sum >= min_sum) 1 else 0            // 备忘录            if (!isLimit && memo[i][sum] != -1) return memo[i][sum]            // 上界            val upper = if (isLimit) num[i] - "0" else 9            var ret = 0            for (choice in 0 .. upper) {                ret = (ret + dfs(num, memo, i + 1, sum + choice , isLimit && choice == upper)) % MOD            }            // 备忘录            if (!isLimit) memo[i][sum] = ret            return ret        }        val n = num.length        val m = Math.min(9 * n, max_sum) + 1        return dfs(num, Array(n) { IntArray(m) { -1 } }, 0, 0, true)    }}

复杂度分析：

时间复杂度：$O(10·n·m)$空间复杂度：$O(n·m)$往期回顾LeetCode 单周赛第 347 场 · 二维空间上的 LIS 最长递增子序列问题LeetCode 单周赛第 346 场 · 仅 68 人 AK 的最短路问题LeetCode 双周赛第 104 场 · 流水的动态规划，铁打的结构化思考LeetCode 双周赛第 103 场 · 区间求和的树状数组经典应用

标签：