⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。
学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭与你分享每场 LeetCode 周赛的解题报告，一起体会上分之旅。
本文是 LeetCode 上分之旅系列的第 40 篇文章，往期回顾请移步到文章末尾~
T1. 统计和小于目标的下标对数目（Easy）
T2. 循环增长使字符串子序列等于另一个字符串（Medium）
T3. 将三个组排序（Medium）
T4. 范围中美丽整数的数目（Hard）
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
}
}
复杂度分析：
在题解一中存在很多无意义的比较，我们观察到配对的顺序是无关的，因此可以考虑利用有序性优化时间复杂度。
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
}
}
复杂度分析：
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
}
}
复杂度分析：
https://leetcode.cn/problems/sorting-three-groups/
根据题意，我们需要构造出非递减数组，并使得操作次数最小。
观察测试用例可以发现逆序数是问题的关键，如示例 1 [2,1,3,2,1] 中存在 2 → 1，3 → 2，2 → 1 的逆序对，且结果正好是 3。然而这个思路是错误的，我们可以构造特殊测试用例 [3,3,3,1,1,1] 来验证。
那应该怎么解呢？我们发现问题是可以划分为子问题的。定义 dp[i][j] 表示到 [i] 为止构造出以 j 为结尾的非递减数组的最少操作次数，那么 dp[i+1][j] 可以从 dp[i] 的三个子状态转移过来：
最后，求出 dp[n][1]、dp[n][2] 和 dp[n][3] 中的最小值即为问题的解。
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()!!
}
}
复杂度分析：
这道题还有第二种思路，我们可以计算数组的最长非递减子序列长度 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
}
}
复杂度分析：
写法 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
}
}
复杂度分析：
相似题目：
https://leetcode.cn/problems/number-of-beautiful-integers-in-the-range/
近期经常出现数位 DP 的题目。
$$(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][diff + U][mod]) {
return memo[i][diff + U][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][diff + U][mod] = ret
}
return ret
}
}
复杂度分析：
相似题目：
推荐阅读
LeetCode 上分之旅系列往期回顾：
⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~
