<xmp id="63nn9"><video id="63nn9"></video></xmp>

<xmp id="63nn9"></xmp>

<wbr id="63nn9"><ins id="63nn9"></ins></wbr>

<wbr id="63nn9"></wbr><video id="63nn9"><ins id="63nn9"><table id="63nn9"></table></ins></video>

LeetCode 周賽上分之旅 #40 結合特征壓縮的數位 DP 問題

?? 本文已收錄到 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)$ 排序遞歸??臻g。

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] 來驗證。

那應該怎么解呢?我們發現問題是可以劃分為子問題的。定義 dp[i][j] 表示到 [i] 為止構造出以 j 為結尾的非遞減數組的最少操作次數,那么 dp[i+1][j] 可以從 dp[i] 的三個子狀態轉移過來:

  • dp[i][1] 可以轉移到 dp[i+1][1] 和 dp[i+1][2] 和 dp[i+1][3]
  • dp[i][2] 可以轉移到 dp[i+1][2] 和 dp[i+1][3]
  • dp[i][3] 可以轉移到 dp[i+1][3]

最后,求出 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()!!
    }
}

復雜度分析:

  • 時間復雜度:$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 數組空間。

相似題目:


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][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
    }
}

復雜度分析:

  • 時間復雜度:$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)$ 備忘錄空間。

相似題目:


推薦閱讀

LeetCode 上分之旅系列往期回顧:

?? 永遠相信美好的事情即將發生,歡迎加入小彭的 Android 交流社群~

posted @ 2023-08-20 20:02  彭旭銳  閱讀(168)  評論(0編輯  收藏  舉報
人碰人摸人爱免费视频播放

<xmp id="63nn9"><video id="63nn9"></video></xmp>

<xmp id="63nn9"></xmp>

<wbr id="63nn9"><ins id="63nn9"></ins></wbr>

<wbr id="63nn9"></wbr><video id="63nn9"><ins id="63nn9"><table id="63nn9"></table></ins></video>