LeetCode 周赛 348（2023/06/05）数位 DP 模板学会了吗

本文已收录到 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.sizeval 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<IntArray>): Long {var ret = 0Lval visitSet = Array(2) { HashSet<Int>() }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) * valuevisitSet[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-9
isNum：高位是否为数字，这题不要考虑前导 0

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

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

class Solution {private val MOD = 1000000007fun 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 = 0for (c in num) sum += c - '0'return if (sum in min_sum..max_sum) 1 else 0}// 数位 DPprivate fun count(num: String, min_sum: Int, max_sum: Int): Int {fun dfs(num: String, memo: Array<IntArray>, i: Int, sum: Int, isLimit: Boolean): Int {// 终止条件if (sum > max_sum) return 0if (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 9var ret = 0for (choice in 0 .. upper) {ret = (ret + dfs(num, memo, i + 1, sum + choice , isLimit && choice == upper)) % MOD}// 备忘录if (!isLimit) memo[i][sum] = retreturn ret}val n = num.lengthval m = Math.min(9 * n, max_sum) + 1return dfs(num, Array(n) { IntArray(m) { -1 } }, 0, 0, true)}
}