技術文章 » LeetCode 周賽上分之旅 #43 電腦科學本質上是數學嗎？

LeetCode 周賽上分之旅 #43 電腦科學本質上是數學嗎？

2023-09-04 15:00:53

⭐️ 本文已收錄到 AndroidFamily，技術和職場問題，請關注公眾號 [彭旭銳] 和 BaguTree Pro 知識星球提問。

學習資料結構與演演算法的關鍵在於掌握問題背後的演演算法思維框架，你的思考越抽象，它能覆蓋的問題域就越廣，理解難度也更復雜。在這個專欄裡，小彭與你分享每場 LeetCode 周賽的解題報告，一起體會上分之旅。

本文是 LeetCode 上分之旅系列的第 43 篇文章，往期回顧請移步到文章末尾~

LeetCode 雙週賽 112

T1. 判斷通過操作能否讓字串相等 I（Easy）

  • 標籤：模擬

T2. 判斷通過操作能否讓字串相等 II（Medium）

  • 標籤：模擬、計數、排序

T3. 幾乎唯一子陣列的最大和（Medium）

  • 標籤：滑動視窗、計數

T4. 統計一個字串的 k 子序列美麗值最大的數目（Hard）

  • 標籤：列舉、貪心、排序、乘法原理、組合數

T1. 判斷通過操作能否讓字串相等 I（Easy）

https://leetcode.cn/problems/check-if-strings-can-be-made-equal-with-operations-i/

題解（模擬）

因為只能交換距離偶數倍的位置，因此相當於比較兩個字串相同奇偶性下標上的元素是否相等。

  • 寫法 1：基於雜湊表
class Solution {
    fun canBeEqual(s1: String, s2: String): Boolean {
        return setOf(s1[0], s1[2]) == setOf(s2[0], s2[2]) && setOf(s1[1], s1[3]) == setOf(s2[1], s2[3])
    }
}
  • 寫法 2：基於字串
class Solution:
    def checkStrings(self, s1: str, s2: str) -> bool:
        return sorted(s1[0::2]) == sorted(s2[0::2]) and sorted(s1[1::2]) == sorted(s2[1::2])

複雜度分析：

  • 時間複雜度：$O(1)$
  • 空間複雜度：$O(1)$

T2. 判斷通過操作能否讓字串相等 II（Medium）

https://leetcode.cn/problems/check-if-strings-can-be-made-equal-with-operations-ii/

題解（模擬）

同上，分別統計奇偶下標上的元素個數是否相等。

寫法 1：基於計數；

class Solution {
    fun checkStrings(s1: String, s2: String): Boolean {
        val U = 26
        val cnts = Array(2) { IntArray(U) }
        for ((i, e) in s1.withIndex()) {
            cnts[i % 2][e - 'a']++
        }
        for ((i, e) in s2.withIndex()) {
            cnts[i % 2][e - 'a']--
        }
        return cnts[0].all {it == 0} && cnts[1].all {it == 0}
    }
}

複雜度分析：

  • 時間複雜度：$O(n + U)$ 線性遍歷時間與計數時間；
  • 空間複雜度：$O(U)$ 計數陣列空間。

寫法 2：基於字串：

class Solution:
    def checkStrings(self, s: str, t: str) -> bool:
        return all(sorted(s[p::2]) == sorted(t[p::2]) for p in range(2))

複雜度分析：

  • 時間複雜度：$O(nlgn)$ 排序時間；
  • 空間複雜度：$O(n)$ 構造字串空間。

T3. 幾乎唯一子陣列的最大和（Medium）

https://leetcode.cn/problems/maximum-sum-of-almost-unique-subarray/

題解（滑動視窗 + 計數）

滑動視窗模板題，維護視窗中不同元素的種類數和總和：

class Solution {
    fun maxSum(nums: List<Int>, m: Int, k: Int): Long {
        var cnts = HashMap<Int, Int>()
        var type = 0
        var sum = 0L
        var ret = 0L
        for (j in nums.indices) {
            // 滑入
            cnts[nums[j]] = cnts.getOrDefault(nums[j], 0) + 1
            if (1 == cnts[nums[j]]!!) type++
            sum += nums[j]
            // 滑出
            if (j >= k) {
                val i = j - k
                cnts[nums[i]] = cnts[nums[i]]!! - 1
                if (0 == cnts[nums[i]]) type --
                sum -= nums[i]
            }
            // 記錄
            if (j >= k - 1 && type >= m) {
                ret = max(ret, sum)
            }
        }
        return ret
    }
}

複雜度分析：

  • 時間複雜度：$O(n)$ 線性遍歷時間；
  • 空間複雜度：$O(n)$ 雜湊表空間。

T4. 統計一個字串的 k 子序列美麗值最大的數目（Hard）

https://leetcode.cn/problems/count-k-subsequences-of-a-string-with-maximum-beauty/

問題分析

  • 問題目標： 求所有長為 $k$ 的子序列中美麗值是最大值的子序列數目；
  • 問題要件： 先計算長為 $k$ 的子序列的最大美麗值，再計算滿足美麗值是最大值的子序列方案數；
  • 關鍵資訊 1： 子序列要選擇不重複的字母；
  • 關鍵資訊 2： 同一個字元在原字串中的不同位置可以構造不同子序列；
  • 核心變數： $f(c)$ 是 字元 $c$ 的出現次數，美麗值是子序列中字元的 $f(c)$ 之和；
  • 邊界情況： 既然子序列要選擇不重複的字母，那麼存在邊界情況，當 $k$ > 字串的字元種類數：那麼一定不能構造 $k$ 子序列，返回 $0$。

題解一（暴力列舉 + 乘法原理）

最簡單的做法，我們可以列舉所有可能的 $k$ 子序列，並記錄出現最大美麗值的方案數，怎麼實現呢？

  • 方法 1 - 考慮到子序列需要保留原字串的順序，直接的想法是列舉字串中的每個下標 $s[i]$ 選和不選，但是時間複雜度是 $O(2^n)$ 顯然不成立；
  • 方法 2 - 事實上我們不需要從原字串的角度列舉，而是可以從字元集的角度列舉，那樣時間複雜度就可以用乘法原理來優化。比如說 a 的出現次數是 $2$，而 b 的出現次數是 $3$，那麼所有 a 與 b 可以構造的子序列方案數就是 2 * 3 = 6。

那麼，方法會不會超時呢，我們來簡單分析下：

由於字元集的大小 $U$ 最多隻有 $26$ 個，那麼子序列的方案數最多有 $C_{26}^k$ 個，而由於 $k$ 大於 $U$ 的方案是不存在的，因此合法的方案數最多隻有 $C_{U}^{\frac{U}{2}} = C_{26}^{13} = 10400600$ 約等於 $10^7$。只要我們保證求解每個子問題的時間複雜度是 $O(1)$ 的話是可以通過的。

列舉實現：

class Solution {
    fun countKSubsequencesWithMaxBeauty(s: String, k: Int): Int {
        val MOD = 1000000007
        // 計數
        val cnts = HashMap<Char, Int>()
        for (e in s) {
            cnts[e] = cnts.getOrDefault(e, 0) + 1
        }
        val m = cnts.size
        if (m < k) return 0 // 特判
        // 列舉子序列
        val keys = cnts.toList()
        var maxCount = 0L
        var maxF = 0
        // 回溯
        fun count(index: Int, size: Int, curF: Int, curCount: Long) {
            // 終止條件
            if (size == k) {                
                if (curF > maxF) {
                    maxF = curF
                    maxCount = curCount // 更新最大美麗值方案數
                } else if (curF == maxF) {
                    maxCount = (maxCount + curCount) % MOD // 增加方案數
                }
                return
            }
            if (size + m - index < k) return // 剪枝（長度不夠）
            for (i in index until m) {
                val (c, cnt) = keys[i]
                count(i + 1, size + 1, curF + cnt, curCount * cnt % MOD /* 乘法原理 */) 
            }
        }
        count(0, 0, 0, 1)
        return maxCount.toInt()
    }
}

複雜度分析：

  • 時間複雜度：$O(C_m^k)$ 其中 $m$ 為字元種類 ；
  • 空間複雜度：$O(m)$ 雜湊表空間與遞迴棧空間。

題解二（排序 + 貪心 + 乘法原理）

考慮 $k = 1$ 的邊界情況：

顯然需要選擇 $f(c)$ 值最大的 $1$ 個字母，如果存在 $m$ 個字母的 $f(c)$ 等於最大值，那麼存在 $C_m^1 = m$ 種方案。這說明我們沒必要列舉所有字母的子序列： 由於子序列中的字元是不重複的，因此 $k$ 子序列必然要選擇 $f(c)$ 值最大的 $k$ 個字母，我們可以將字母按照 $f(c)$ 倒序排序，優先取 $f(c)$ 更大的字母。

具體實現上：

我們將字母按照 $f(c)$ 分桶排序，如果桶內字母數量 $K$ 小於等於 $k$，那麼桶內元素都需要選擇，否則還要計算桶內元素選擇 $k$ 個的方案數：

  • 選擇桶內所有元素，方案數為 $cnt^K$
  • 選擇桶內部分元素，方案數為 $C_K^k · cnt^k$

其中涉及到冪運算，本質是倍增思想：

// 快速冪 x^n
private fun powM(a: Int, b: Int, mod: Int) : Long {
    var x = a.toLong()
    var n = b.toLong()
    var ret = 1L
    while (n > 0L) {
        if (n % 2 == 1L) ret = ret * x % mod
        x = x * x % mod
        n /= 2
    }
    return ret
}

其中涉及到 組合數：

  • 計算式：
// 組合數計算公式 O(k)
private fun comb(n: Int, k: Int, mod: Int) : Int {
    var ret = 1L
    for (i in 1 .. k) {
        ret = ret * (n - i + 1) / i % mod
    }
    return ret.toInt()
}
  • 遞推式（楊輝三角）：
// 遞迴 O(n^2)
private fun comb(n: Int, k: Int, mod: Int) : Int {
    if (n == k) {
        return 1
    } else if (k == 1) {
        return n
    } else {
        return (comb(n - 1, k - 1, mod) + comb(n - 1, k, mod)) % mod
    }
}

// 迭代 O(n^2)
private fun comb(n: Int, k: Int, mod: Int) : Int {
    val c = Array(n + 1) { IntArray(n + 1) }
    for (i in 1 .. n) {
        c[i][0] = 1
        c[i][i] = 1
        for (j in 1 until i) {
            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod
        }
    }
    return c[n][k]
}


// 組合數計算公式
private fun comb(n: Long, k: Long, mod: Int) : Int {
    var n = n
    var ret = 1L
    for (i in 1 .. k) {
        ret = ret * n-- / i % mod
    }
    return ret.toInt()
}

// 盧卡斯定理
fun Lucas(n: Long, k: Long, mod: Int) : Long {
    if (k == 0L) return 1L;
    return (comb(n % mod, k % mod, mod) * Lucas(n / mod, k / mod, mod)) % mod;
}

完整程式碼：

class Solution {
    fun countKSubsequencesWithMaxBeauty(s: String, k: Int): Int {
        val MOD = 1000000007
        // 計數
        val cnts = HashMap<Char, Int>()
        var maxCnt = 0
        for (e in s) {
            cnts[e] = cnts.getOrDefault(e, 0) + 1
            maxCnt = max(maxCnt, cnts[e]!!)
        }
        val m = cnts.size
        if (m < k) return 0 // 特判
        // 有序集合
        val map = TreeMap<Int, Int>() { c1, c2 -> 
            c2 - c1
        }
        // 二次頻率
        for ((_, c) in cnts) {
            map[c] = map.getOrDefault(c, 0) + 1
        }
        val cntCnts = map.toList()
        // println(cntCnts.joinToString())
        // 構造方案
        var ret = 1L
        var leftK = k
        for ((cnt, K) in cntCnts) {
            if (K > leftK) {
                ret = ret * powM(cnt, leftK, MOD) * comb(K, leftK, MOD) % MOD
            } else {
                ret = ret * powM(cnt, K, MOD) % MOD
            }
            leftK -= K
            if (leftK <= 0) break
        }
        return ret.toInt()
    }

    // 組合數計算公式 C_n^k
    private fun comb(n: Int, k: Int, mod: Int) : Int {
        if (n == k) {
            return 1
        } else if (k == 1) {
            return n
        } else {
            return (comb(n - 1, k - 1, mod) + comb(n - 1, k, mod)) % mod
        }
    }

    // 快速冪 x^n
    private fun powM(x_: Int, n_: Int, mod: Int) : Long {
        var x = x_.toLong()
        var n = n_.toLong()
        var ret = 1L
        while (n > 0L) {
            if (n % 2 == 1L) ret = ret * x % mod
            x = x * x % mod
            n /= 2
        }
        return ret
    }
}

Python 中組合數和冪運算可以很方便地使用庫函數：

class Solution:
    def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
        MOD = 10 ** 9 + 7
        ans = 1
        cnt = Counter(Counter(s).values())
        for c, num in sorted(cnt.items(), reverse=True): # 二次計數
            if num >= k:
                return ans * pow(c, k, MOD) * comb(num, k) % MOD
            ans *= pow(c, num, MOD)
            k -= num
        return 0

複雜度分析：

  • 時間複雜度：$O(n + m)$ 主要時間在列舉字串的環節；
  • 空間複雜度：$O(m)$ 雜湊表空間。

推薦閱讀

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

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