雙周賽 111
T1. 統(tǒng)計(jì)和小于目標(biāo)的下標(biāo)對(duì)數(shù)目（Easy）
- 標(biāo)簽：模擬、排序、相向雙指針
T2. 循環(huán)增長(zhǎng)使字符串子序列等于另一個(gè)字符串（Medium）
- 標(biāo)簽：排序、雙指針
T3. 將三個(gè)組排序（Medium）
- 標(biāo)簽：狀態(tài)機(jī) DP、LIS 問(wèn)題、貪心、二分查找
T4. 范圍中美麗整數(shù)的數(shù)目（Hard）
- 標(biāo)簽：數(shù)位 DP、記憶化
T1. 統(tǒng)計(jì)和小于目標(biāo)的下標(biāo)對(duì)數(shù)目（Easy）
https://leetcode.cn/problems/count-pairs-whose-sum-is-less-than-target/
題解一（模擬）
簡(jiǎn)單模擬題。
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
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
- 空間復(fù)雜度：
題解二（排序 + 相向雙指針）
在題解一中存在很多無(wú)意義的比較，我們觀察到配對(duì)的順序是無(wú)關(guān)的，因此可以考慮利用有序性?xún)?yōu)化時(shí)間復(fù)雜度。
- 先對(duì)數(shù)組排序；
- 利用元素的大小關(guān)系，使用雙指針篩選滿(mǎn)足條件的配對(duì)數(shù)。
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
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
瓶頸在排序，雙指針時(shí)間復(fù)雜度為
；
- 空間復(fù)雜度：
排序遞歸?？臻g。
T2. 循環(huán)增長(zhǎng)使字符串子序列等于另一個(gè)字符串（Medium）
https://leetcode.cn/problems/make-string-a-subsequence-using-cyclic-increments/
題解（雙指針 + 貪心）
首先閱讀題意，問(wèn)題相當(dāng)于從 str1 中選擇若干個(gè)位置執(zhí)行 +1 操作后讓 str2 成為 str1 的子序列。其次容易想到貪心算法，對(duì)于 str1[i] 與 str2[j] 來(lái)說(shuō)，如果 str1[i] 能夠在至多操作 1 次的情況下變?yōu)?str2[j]，那么讓 i 與 j 匹配是最優(yōu)的。
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
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
i 指針和 j 指針最多移動(dòng) n + m 次；
- 空間復(fù)雜度：
僅使用常量級(jí)別空間。
T3. 將三個(gè)組排序（Medium）
https://leetcode.cn/problems/sorting-three-groups/
題解一（狀態(tài)機(jī) DP）
根據(jù)題意，我們需要構(gòu)造出非遞減數(shù)組，并使得操作次數(shù)最小。
觀察測(cè)試用例可以發(fā)現(xiàn)逆序數(shù)是問(wèn)題的關(guān)鍵，如示例 1 [2,1,3,2,1] 中存在 2 → 1，3 → 2，2 → 1 的逆序?qū)?，且結(jié)果正好是 3。然而這個(gè)思路是錯(cuò)誤的，我們可以構(gòu)造特殊測(cè)試用例 [3,3,3,1,1,1] 來(lái)驗(yàn)證。
那應(yīng)該怎么解呢？我們發(fā)現(xiàn)問(wèn)題是可以劃分為子問(wèn)題的。定義 dp[i][j] 表示到 [i] 為止構(gòu)造出以 j 為結(jié)尾的非遞減數(shù)組的最少操作次數(shù)，那么 dp[i+1][j] 可以從 dp[i] 的三個(gè)子狀態(tài)轉(zhuǎn)移過(guò)來(lái)：
- dp[i][1] 可以轉(zhuǎn)移到 dp[i+1][1] 和 dp[i+1][2] 和 dp[i+1][3]
- dp[i][2] 可以轉(zhuǎn)移到 dp[i+1][2] 和 dp[i+1][3]
- dp[i][3] 可以轉(zhuǎn)移到 dp[i+1][3]
最后，求出 dp[n][1]、dp[n][2] 和 dp[n][3] 中的最小值即為問(wèn)題的解。
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] 有關(guān)，我們可以使用滾動(dòng)數(shù)組優(yōu)化空間復(fù)雜度：
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()!!
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
僅需要線(xiàn)性時(shí)間，其中
= 9；
- 空間復(fù)雜度：
DP 數(shù)組空間，
= 3。
題解二（LIS 問(wèn)題）
這道題還有第二種思路，我們可以計(jì)算數(shù)組的最長(zhǎng)非遞減子序列長(zhǎng)度 LIS，再使用原數(shù)組長(zhǎng)度 n - 最長(zhǎng)非遞減子序列長(zhǎng)度 LIS，就可以得出最少操作次數(shù)。
LIS 問(wèn)題有兩個(gè)寫(xiě)法：
寫(xiě)法 1 · 動(dòng)態(tài)規(guī)劃
class Solution {
fun minimumOperations(nums: List<Int>): Int {
val n = nums.size
// dp[i] 表示以 [i] 為結(jié)尾的 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
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
內(nèi)存循環(huán)的時(shí)間復(fù)雜度是
- 空間復(fù)雜度：
寫(xiě)法 2 · 動(dòng)態(tài)規(guī)劃 + 貪心 + 二分查找
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 {
// 二分查找維護(hù)增長(zhǎng)更慢的序列：尋找大于 nums[i] 的第一個(gè)數(shù)
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
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
- 空間復(fù)雜度：
相似題目：
T4. 范圍中美麗整數(shù)的數(shù)目（Hard）
https://leetcode.cn/problems/number-of-beautiful-integers-in-the-range/
題解（數(shù)位 DP + 記憶化）
近期經(jīng)常出現(xiàn)數(shù)位 DP 的題目。
-
1、數(shù)位 DP： 我們定義 dp[i, pre, diff, isNumber, isLimit] 表示從第 i 位開(kāi)始的合法方案數(shù)，其中：
- pre 表示已經(jīng)選擇的數(shù)位前綴的值，當(dāng)填入第 i 位的數(shù)字 choice 后更新為 pre * 10 + choice，在終止條件時(shí)判斷 pre % k == 0；
- diff 表示已選擇的數(shù)位中奇數(shù)和偶數(shù)的差值，奇數(shù) + 1，而偶數(shù) - 1，在終止條件時(shí)判斷 diff == 0；
- isNumber 表示已填數(shù)位是否構(gòu)造出合法數(shù)字；
- isLimit 表示當(dāng)前數(shù)位是否被當(dāng)前數(shù)位的最大值約束。
- 2、差值： 要計(jì)算出 [low, high] 之間的合法方案數(shù)，我們可以計(jì)算出 [0, high] 和 [0, low] 之間合法方案數(shù)的差值；
- 3、記憶化： 對(duì)于相同 dp[i, …] 子問(wèn)題，可能會(huì)重復(fù)計(jì)算，可以使用記憶化優(yōu)化時(shí)間復(fù)雜度：
- 4、特征壓縮： 由于所有的備選數(shù)的 pre 都是不用的，這會(huì)導(dǎo)致永遠(yuǎn)不會(huì)命中備忘錄，我們需要找到不同前綴的特征。
-
5、取模公式： 如果
，那么有
，我們可以提前對(duì) pre 取模抽取出特征因子。
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]，我們?cè)黾右粋€(gè) 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)
}
}
// 寫(xiě)備忘錄
if (!isLimit && isNumber) {
memo[i][diff + U][mod] = ret
}
return ret
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
其中
為選擇方案 10。狀態(tài)數(shù)為 “i 的值域 * diff 的值域 * mod 的值域” =
，單個(gè)狀態(tài)的時(shí)間復(fù)雜度是
，整體的時(shí)間復(fù)雜度是狀態(tài)數(shù) · 狀態(tài)時(shí)間 =
- 空間復(fù)雜度：
備忘錄空間。
相似題目：
推薦閱讀
LeetCode 上分之旅系列往期回顧：
