⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 BaguTree Pro 常识星球发问。
学习数据结构与算法的关键在于把握问题背地的算法思维框架，你的思考越形象，它能笼罩的问题域就越广，了解难度也更简单。在这个专栏里，小彭与你分享每场 LeetCode 周赛的解题报告，一起领会上分之旅。
本文是 LeetCode 上分之旅系列的第 40 篇文章，往期回顾请移步到文章开端 \~
双周赛 111
T1. 统计和小于指标的下标对数目（Easy）
- 标签：模仿、排序、相向双指针
T2. 循环增长使字符串子序列等于另一个字符串（Medium）
- 标签：排序、双指针
T3. 将三个组排序（Medium）
- 标签：状态机 DP、LIS 问题、贪婪、二分查找
T4. 范畴中漂亮整数的数目（Hard）
- 标签：数位 DP、记忆化
T1. 统计和小于指标的下标对数目（Easy）
https://leetcode.cn/problems/count-pairs-whose-sum-is-less-than-target/题解一（模仿）
简略模拟题。
class Solution {fun countPairs(nums: List<Int>, target: Int): Int {
var ret = 0
for (i in 0 until nums.size) {for (j in i + 1 until nums.size) {if (nums[i] + nums[j] < target) ret ++
}
}
return ret
}
}复杂度剖析：
- 工夫复杂度：$O(n^2)$
- 空间复杂度：$O(1)$
题解二（排序 + 相向双指针）
在题解一中存在很多无意义的比拟，咱们察看到配对的程序是无关的，因而能够思考利用有序性优化工夫复杂度。
- 先对数组排序；
- 利用元素的大小关系，应用双指针筛选满足条件的配对数。
class Solution {fun countPairs(nums: MutableList<Int>, target: Int): Int {nums.sort()
var ret = 0
var i = 0
var j = nums.size - 1
while (i < j) {while (i < j && nums[i] + nums[j] >= target) {j--}
if (i == j) break
ret += j - i
i++
}
return ret
}
}复杂度剖析：
- 工夫复杂度：$O(nlgn)$ 瓶颈在排序，双指针工夫复杂度为 $O(n)$；
- 空间复杂度：$O(lgn)$ 排序递归栈空间。
T2. 循环增长使字符串子序列等于另一个字符串（Medium）
https://leetcode.cn/problems/make-string-a-subsequence-using-cyclic-increments/题解（双指针 + 贪婪）
首先浏览题意，问题相当于从 str1 中抉择若干个地位执行 +1 操作后让 str2 成为 str1 的子序列。其次容易想到贪婪算法，对于 str1[i] 与 str2[j] 来说，如果 str1[i] 可能在至少操作 1 次的状况下变为 str2[j]，那么让 i 与 j 匹配是最优的。
class Solution {fun canMakeSubsequence(str1: String, str2: String): Boolean {
val U = 26
val n = str1.length
val m = str2.length
var j = 0
for (i in 0 until n) {val x = str1[i] - 'a'
val y = str2[j] - 'a'
if ((y - x + U) % U <= 1) {if (++j == m) break
}
}
return m == j
}
}复杂度剖析：
- 工夫复杂度：$O(n + m)$ i 指针和 j 指针最多挪动 n + m 次；
- 空间复杂度：$O(1)$ 仅应用常量级别空间。
T3. 将三个组排序（Medium）
https://leetcode.cn/problems/sorting-three-groups/题解一（状态机 DP）
依据题意，咱们须要结构出非递加数组，并使得操作次数最小。
察看测试用例能够发现逆序数是问题的要害，如示例 1 [2,1,3,2,1] 中存在 2 → 1，3 → 2，2 → 1 的逆序对，且后果正好是 3。然而这个思路是谬误的，咱们能够结构非凡测试用例 [3,3,3,1,1,1] 来验证。
那应该怎么解呢？咱们发现问题是能够划分为子问题的。定义 dpi 示意到 [i] 为止结构出以 j 为结尾的非递加数组的起码操作次数，那么 dpi+1 能够从 dp[i] 的三个子状态转移过去：
- dpi 能够转移到 dpi+1 和 dpi+1 和 dpi+1
- dpi 能够转移到 dpi+1 和 dpi+1
- dpi 能够转移到 dpi+1
最初，求出 dpn、dpn 和 dpn 中的最小值即为问题的解。
class Solution {fun minimumOperations(nums: List<Int>): Int {
val n = nums.size
val U = 3
val dp = Array(n + 1) {IntArray(U + 1) }
for (i in 1 .. n) {for (j in 1 .. U) {dp[i][j] = dp[i - 1].slice(1..j).min()!!
if (j != nums[i - 1]) dp[i][j] += 1
}
}
return dp[n].slice(1..U).min()!!}
}另外，dp[i+1] 只与 dp[i] 无关，咱们能够应用滚动数组优化空间复杂度：
class Solution {fun minimumOperations(nums: List<Int>): Int {
val n = nums.size
val U = 3
val dp = IntArray(U + 1)
for (i in 0 until n) {for (j in U downTo 1) { // 逆序
dp[j] = dp.slice(1..j).min()!!
if (j != nums[i]) dp[j] += 1
}
}
return dp.slice(1..U).min()!!}
}复杂度剖析：
- 工夫复杂度：$O(C·n)$ 仅须要线性工夫，其中 $C$ = 9；
- 空间复杂度：$O(U)$ DP 数组空间，$U$ = 3。
题解二（LIS 问题）
这道题还有第二种思路，咱们能够计算数组的最长非递加子序列长度 LIS，再应用原数组长度 n – 最长非递加子序列长度 LIS，就能够得出起码操作次数。
LIS 问题有两个写法：
写法 1 · 动静布局
class Solution {fun minimumOperations(nums: List<Int>): Int {
val n = nums.size
// dp[i] 示意以 [i] 为结尾的 LIS
val dp = IntArray(n) {1}
var len = 1
for (i in 0 until n) {for (j in 0 until i) {if (nums[i] >= nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1)
}
len = Math.max(len, dp[i])
}
return n - len
}
}复杂度剖析：
- 工夫复杂度：$O(n^2)$ 内存循环的工夫复杂度是 $O(n)$；
- 空间复杂度：$O(n)$ DP 数组空间。
写法 2 · 动静布局 + 贪婪 + 二分查找
class Solution {fun minimumOperations(nums: List<Int>): Int {
val n = nums.size
val dp = IntArray(n + 1)
var len = 1
dp[len] = nums[0]
for (i in 1 until n) {if (nums[i] >= dp[len]) {dp[++len] = nums[i]
} else {// 二分查找保护增长更慢的序列：寻找大于 nums[i] 的第一个数
var left = 1
var right = len
while (left < right) {val mid = (left + right) ushr 1
if (dp[mid] <= nums[i]) {left = mid + 1} else {right = mid}
}
dp[left] = nums[i]
}
}
return n - len
}
}复杂度剖析：
- 工夫复杂度：$O(nlgn)$ 单次二分查找的工夫复杂度是 $O(lgn)$；
- 空间复杂度：$O(n)$ DP 数组空间。
类似题目：
- 300. 最长递增子序列
T4. 范畴中漂亮整数的数目（Hard）
https://leetcode.cn/problems/number-of-beautiful-integers-in-the-range/题解（数位 DP + 记忆化）
近期经常出现数位 DP 的题目。
-
1、数位 DP： 咱们定义 dp[i, pre, diff, isNumber, isLimit] 示意从第 i 位开始的非法计划数，其中：
- pre 示意曾经抉择的数位前缀的值，当填入第 i 位的数字 choice 后更新为 pre * 10 + choice，在终止条件时判断 pre % k == 0；
- diff 示意已抉择的数位中奇数和偶数的差值，奇数 + 1，而偶数 – 1，在终止条件时判断 diff == 0；
- isNumber 示意已填数位是否结构出非法数字；
- isLimit 示意以后数位是否被以后数位的最大值束缚。
- 2、差值： 要计算出 [low, high] 之间的非法计划数，咱们能够计算出 [0, high] 和 [0, low] 之间非法计划数的差值；
- 3、记忆化： 对于雷同 dp[i, …] 子问题，可能会反复计算，能够应用记忆化优化工夫复杂度：
- 4、特色压缩： 因为所有的备选数的 pre 都是不必的，这会导致永远不会命中备忘录，咱们须要找到不同前缀的特色。
- 5、取模公式： 如果 $(pre * 10 + choice) \% k == 0$，那么有 $((pre \% k) * 10 + choice) \% k == 0$，咱们能够提前对 pre 取模抽取出特色因子。
$$(a + b) \% mod == ((a \% mod) + (b \% mod)) \% mod$$
$$(a · b) \% mod == ((a \% mod) · (b \% mod)) \% mod$$
class Solution {
private val U = 10
fun numberOfBeautifulIntegers(low: Int, high: Int, k: Int): Int {return count(high, k) - count(low - 1, k)
}
private fun count(num: Int, k: Int): Int {
// <i, diff, k>
val memo = Array(U) {Array(U + U) {IntArray(k) {-1}} }
return f(memo, "$num", k, 0, 0, 0, true, false)
}
private fun f(memo: Array<Array<IntArray>>, str: String, k: Int, i: Int, mod: Int, diff: Int, isLimit: Boolean, isNumber: Boolean): Int {
// 终止条件
if (i == str.length) return if (0 != diff || mod % k != 0) 0 else 1
// 读备忘录
if (!isLimit && isNumber && -1 != memo[i][mod]) {return memo[i][mod] // 因为 diff 的取值是 [-10,10]，咱们减少一个 U 的偏移
}
val upper = if (isLimit) str[i] - '0' else 9
var ret = 0
for (choice in 0 .. upper) {val newMod = (mod * 10 + choice) % k // 特色因子
if (!isNumber && choice == 0) {ret += f(memo, str, k, i + 1, 0, 0, false, false)
continue
}
if (choice % 2 == 0) {ret += f(memo, str, k, i + 1, newMod, diff + 1, isLimit && choice == upper, true)
} else {ret += f(memo, str, k, i + 1, newMod, diff - 1, isLimit && choice == upper, true)
}
}
// 写备忘录
if (!isLimit && isNumber) {memo[i][mod] = ret
}
return ret
}
}复杂度剖析：
- 工夫复杂度：$O(C^2·k·D)$ 其中 $C$ 为最大数位长度 10，$D$ 为抉择计划 10。状态数为“i 的值域 diff 的值域 mod 的值域”= $C^2·k$，单个状态的工夫复杂度是 $O(D)$，整体的工夫复杂度是状态数 · 状态工夫 = $O(C^2·k·D)$；
- 空间复杂度：$O(C^2·k)$ 备忘录空间。
类似题目：
- 2801. 统计范畴内的步进数字数目
举荐浏览
LeetCode 上分之旅系列往期回顾：
- LeetCode 单周赛第 358 场 · 联合核心扩大的枯燥栈贪婪问题
- LeetCode 单周赛第 357 场 · 多源 BFS 与连通性问题
- LeetCode 双周赛第 110 场 · 联合排序不等式的动静布局
- LeetCode 双周赛第 109 场 · 循序渐进地解决动静布局问题
⭐️ 永远置信美妙的事件行将产生，欢送退出小彭的 Android 交换社群 \~