往期回顾:LeetCode 单周赛第 347 场 · 二维空间上的 LIS 最长递增子序列问题周赛 348 概览本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 加入知识星球提问!
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:高位是否为数字,这题不要考虑前导 03、定义 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 场 · 区间求和的树状数组经典应用标签: