技術文章 » LeetCode 周賽 332，在套路里摸爬滾打~

LeetCode 周賽 332，在套路里摸爬滾打~

2023-02-17 06:00:20

本文已收錄到 AndroidFamily，技術和職場問題，請關注公眾號 [彭旭銳] 提問。

大家好，今天是 3T 選手小彭。

上週是 LeetCode 第 332 場周賽，你參加了嗎？演演算法解題思維需要長時間鍛鍊，加入我們一起刷題吧~

小彭的 Android 交流群 02 群已經建立啦，公眾號回覆 「加群」 加入我們~

2562.  找出陣列的串聯值（Easy）

題目地址

https://leetcode.cn/problems/find-the-array-concatenation-value/

題目描述

給你一個下標從  0  開始的整數陣列  nums 。

現定義兩個數位的  串聯  是由這兩個數值串聯起來形成的新數位。

  • 例如，15  和  49  的串聯是  1549 。

nums  的  串聯值  最初等於  0 。執行下述操作直到  nums  變為空：

  • 如果  nums  中存在不止一個數位，分別選中  nums  中的第一個元素和最後一個元素，將二者串聯得到的值加到  nums  的  串聯值  上，然後從  nums  中刪除第一個和最後一個元素。
  • 如果僅存在一個元素，則將該元素的值加到  nums  的串聯值上，然後刪除這個元素。

返回執行完所有操作後  nums  的串聯值。

題解

簡單模擬題，使用雙指標向中間逼近即可。


class Solution {
    fun findTheArrayConcVal(nums: IntArray): Long {
        var left = 0
        var right = nums.size - 1
        var result = 0L
        while (left <= right) {
            result += if (left == right) {
                 nums[left]
            } else{
                Integer.valueOf("${nums[left]}${nums[right]}")
            }
            left++
            right--
        }
        return result
    }
}

複雜度分析：

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

2563.  統計公平數對的數目（Medium）

題目地址

https://leetcode.cn/problems/count-the-number-of-fair-pairs/

題目描述

給你一個下標從  0  開始、長度為  n  的整數陣列  nums ，和兩個整數  lower  和  upper ，返回  公平數對的數目 。

如果  (i, j)  數對滿足以下情況，則認為它是一個  公平數對 ：

  • 0 <= i < j < n，且
  • lower <= nums[i] + nums[j] <= upper

題解一（排序 + 列舉組合）

題目要求尋找 2 個目標數 nums[i] 和 nums[j] 滿足兩數之和處於區間 [lower, upper] 。雖然題目強調了下標 i 和下標 j 滿足 0 <= i < j < n，但事實上兩個數的順序並不重要，我們選擇 nums[2] + nums[4] 與選擇 nums[4] + nums[2] 的結果是相同的。因此，第一反應可以使用 「樸素組合模板」，時間複雜度是 $O(n^2)$，但在這道題中會超出時間限制。

// 組合模板
class Solution {
    fun countFairPairs(nums: IntArray, lower: Int, upper: Int): Long {
        val n = nums.size
        var result = 0L
        for (i in 0 until nums.size - 1) {
            for (j in i + 1 until nums.size) {
                val sum = nums[i] + nums[j]
                if (sum in lower..upper) result++
            }
        }
        return result
    }
}

以範例 1 來說，我們發現在外層迴圈選擇 nums[i] = 4 的一趟迴圈中，當內層迴圈選擇 $[4 + 4]$ 組合不滿足條件後，選擇一個比 $4$ 更大的 $[4 + 5]$ 組合顯得沒有必要。從這裡容易想到使用 「排序」 剪去不必要的組合方案：我們可以先對輸入資料進行排序，當內層迴圈的 nums[j] 不再可能滿足條件時提前終止內層迴圈：

class Solution {
    fun countFairPairs(nums: IntArray, lower: Int, upper: Int): Long {
        // 排序 + 列舉組合
        var result = 0L
        nums.sort()
        for (i in 0 until nums.size - 1) {
            for (j in i + 1 until nums.size) {
                val sum = nums[i] + nums[j]
                if (sum < lower) continue
                if (sum > upper) break
                result++
            }
        }
        return result
    }
}

複雜度分析：

  • 時間複雜度：$O(nlgn + n^2)$ 快速排序 + 組合的時間，其中 $O(n^2)$ 是一個比較鬆的上界。
  • 空間複雜度：$O(lgn)$ 快速排序佔用的遞迴棧空間。

題解二（排序 + 二分查詢）

使用排序優化後依然無法滿足題目要求，我們發現：內層迴圈並不需要線性掃描，我們可以使用 $O(lgn)$ 二分查詢尋找：

  • 第一個大於等於 min 的數
  • 最後一個小於等於 max 的數

再使用這 2 個邊界數的下標相減，即可獲得內層迴圈中的目標組合個數。

class Solution {
    fun countFairPairs(nums: IntArray, lower: Int, upper: Int): Long {
        // 排序 + 二分查詢
        var result = 0L
        nums.sort()
        for (i in 0 until nums.size - 1) {
            // nums[i] + x >= lower
            // nums[i] + x <= upper
            // 目標數的範圍：[lower - nums[i], upper - nums[i]]
            val min = lower - nums[i]
            val max = upper - nums[i]
            // 二分查詢優化：尋找第一個大於等於 min 的數
            var left = i + 1
            var right = nums.size - 1
            while (left < right) {
                val mid = (left + right - 1) ushr 1
                if (nums[mid] < min) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            val minIndex = if (nums[left] >= min) left else continue
            // 二分查詢優化：尋找最後一個小於等於 max 的數
            left = minIndex
            right = nums.size - 1
            while (left < right) {
                val mid = (left + right + 1) ushr 1
                if (nums[mid] > max) {
                    right = mid - 1
                } else {
                    left = mid
                }
            }
            val maxIndex = if (nums[left] <= max) left else continue
            result += maxIndex - minIndex + 1
        }
        return result
    }
}

複雜度分析：

  • 時間複雜度：$O(nlgn + nlgn)$ 快速排序 + 組合的時間，內層迴圈中每次二分查詢的時間是 $O(lgn)$。
  • 空間複雜度：$O(lgn)$ 快速排序佔用的遞迴棧空間。

2564.  子字串互斥或查詢（Medium）

題目地址

https://leetcode.cn/problems/substring-xor-queries/

題目描述

給你一個  二進位制字串 s  和一個整數陣列  queries ，其中  queries[i] = [firsti, secondi] 。

對於第  i  個查詢，找到  s  的  最短子字串 ，它對應的  十進位制值  val  與  firsti 按位元互斥或  得到  secondi ，換言之，val ^ firsti == secondi 。

第  i  個查詢的答案是子字串  [lefti, righti]  的兩個端點（下標從  0  開始），如果不存在這樣的子字串，則答案為  [-1, -1] 。如果有多個答案，請你選擇  lefti  最小的一個。

請你返回一個陣列  ans ，其中  ans[i] = [lefti, righti]  是第  i  個查詢的答案。

子字串  是一個字串中一段連續非空的字元序列。

前置知識

記 ⊕ 為互斥或運算，互斥或運算滿足以下性質：

  • 基本性質：x ⊕ y = 0
  • 交換律：x ⊕ y = y ⊕ x
  • 結合律：(x ⊕ y) ⊕ z = x ⊕ (y ⊕ z)
  • 自反律：x ⊕ y ⊕ y = x

題解一（滑動視窗）

題目要求字串 s 的最短子字串，使其滿足其對應的數值 val ⊕ first = second，根據互斥或的自反律性質可知（等式兩邊同互斥或 first），題目等價於求滿足 val = first ⊕ second 的最短子字串。

容易想到的思路是：我們單獨處理 queries 陣列中的每個查詢，並計算目標互斥或值 target = first ⊕ second，而目標字串的長度一定與 target 的二進位制數的長度相同。所以，我們先獲取 target 的有效二進位制長度 len，再使用長度為 len 的滑動視窗尋找目標子字串。由於題目要求 [left 最小的方案，所以需要在每次尋找到答案後提前中斷。

class Solution {
    fun substringXorQueries(s: String, queries: Array<IntArray>): Array<IntArray> {
        // 尋找等於目標值的子字串
        // 滑動視窗
        val n = s.length
        val result = Array(queries.size) { intArrayOf(-1, -1) }
        for ((index, query) in queries.withIndex()) {
            val target = query[0] xor query[1]
            // 計算 target 的二進位制長度
            var len = 1
            var num = target
            while (num >= 2) {
                num = num ushr 1
                len++
            }
            for (left in 0..n - len) {
                val right = left + len - 1
                if (s.substring(left, right + 1).toInt(2) == target) {
                    result[index][0] = left
                    result[index][1] = right
                    break
                }
            }
        }
        return result
    }
}

複雜度分析：

  • 時間複雜度：$O(mn)$，其中 m 是 queries 陣列的長度，n 是字串的長度，在這道題中會超時。
  • 空間複雜度：$O(1)$，不考慮結果陣列。

題解二（滑動視窗 + 分桶預處理）

事實上，如果每次都單獨處理 queries 陣列中的每個查詢，那麼題目將查詢設定為陣列就沒有意義了，而且在遇到目標互斥或值 target 的二進位制長度 len 相同時，會存在大量重複計算。因此，容易想到的思路是：我們可以預先將 queries 陣列中所有二進位制長度 len 相同的查詢劃分為一組，使相同長度的滑動視窗只會計算一次。

另一個細節是題目的測試用例中存在相同的查詢，所以我們需要在對映表中使用 LinkedList 記錄相同目標互斥或值 target 到查詢下標 index 的關係。

class Solution {
    fun substringXorQueries(s: String, queries: Array<IntArray>): Array<IntArray> {
        // 尋找等於目標值的子字串
        // 根據長度分桶：len to <target,index>
        val lenMap = HashMap<Int, HashMap<Int, LinkedList<Int>>>()
        for ((index, query) in queries.withIndex()) {
            val target = query[0] xor query[1]
            // 計算 target 的二進位制長度
            var len = 1
            var num = target
            while (num >= 2) {
                num = num ushr 1
                len++
            }
            lenMap.getOrPut(len) { HashMap<Int, LinkedList<Int>>() }.getOrPut(target) { LinkedList<Int>() }.add(index)
        }
        // 滑動視窗
        val n = s.length
        val result = Array(queries.size) { intArrayOf(-1, -1) }
        for ((len, map) in lenMap) {
            for (left in 0..n - len) {
                val right = left + len - 1
                val curValue = s.substring(left, right + 1).toInt(2)
                if (map.containsKey(curValue)) {
                    for (index in map[curValue]!!) {
                        result[index][0] = left
                        result[index][1] = right
                    }
                    map.remove(curValue)
										// 該長度搜尋結束
                    if (map.isEmpty()) break
                }
            }
        }
        return result
    }
}

複雜度分析：

  • 時間複雜度：$O(m + Ln)$，其中 n 是字串的長度， m 是 queries 陣列的長度，L 是不同長度的視窗個數，$O(m)$ 是預處理的時間。根據題目輸入滿足 $10^9 < 2^{30}$ 可知 L 的最大值是 30。
  • 空間複雜度：$O(m)$，雜湊表總共需要記錄 m 個查詢的對映關係。

題解三（滑動視窗 + 預處理字串）

這道題的思路也是通過預處理過濾相同長度的滑動視窗，區別在於預處理的是輸入字串，我們直接計算字串 s 中所有可能出現的數位以及對應的 [left,right] 下標，再利用這份資料給予 queries 陣列進行 $O(1)$ 打表查詢。

class Solution {
    fun substringXorQueries(s: String, queries: Array<IntArray>): Array<IntArray> {
        val n = s.length
        // 預處理
        val valueMap = HashMap<Int, IntArray>()
        for (len in 1..Math.min(n,31)) {
            for (left in 0..n - len) {
                val right = left + len - 1
                val num = s.substring(left, right + 1).toInt(2)
                if (!valueMap.containsKey(num)) {
                    valueMap[num] = intArrayOf(left, right)
                }
            }
        }
        val result = Array(queries.size) { intArrayOf(-1, -1) }
        for ((index, query) in queries.withIndex()) {
            val target = query[0] xor query[1]
            if (valueMap.containsKey(target)) {
                result[index] = valueMap[target]!!
            }
        }
        return result
    }
}

複雜度分析：

  • 時間複雜度：$O(Ln + m)$，其中 n 是字串的長度， m 是 queries 陣列的長度，L 是不同長度的視窗個數。$O(Ln)$ 是預處理的時間，根據題目輸入滿足 $10^9 < 2^{30}$ 可知 L 的最大值是 30。
  • 空間複雜度：$O(nL)$，雜湊表總共需要記錄 nL 個數的對映關係。

2565.  最少得分子序列（Hard）

題目地址

https://leetcode.cn/problems/subsequence-with-the-minimum-score/

題目描述

給你兩個字串  s  和  t 。

你可以從字串  t  中刪除任意數目的字元。

如果沒有從字串  t  中刪除字元，那麼得分為  0 ，否則：

  • 令  left  為刪除字元中的最小下標。
  • 令  right  為刪除字元中的最大下標。

字串的得分為  right - left + 1 。

請你返回使  t  成為  s  子序列的最小得分。

一個字串的  子序列  是從原字串中刪除一些字元后（也可以一個也不刪除），剩餘字元不改變順序得到的字串。（比方說  "ace"  是  "acde"  的子序列，但是  "aec"  不是）。

題解（前字尾分解）

這道題第一感覺是 LCS 最長公共子序列的衍生問題，我們可以使用樸素 LCS 模板求解字串 s 和字串 t 的最長公共子序列 ，再使用 t 字串的長度減去公共部分長度得到需要刪除的字元個數。

然而，這道題目的輸出得分取決於最左邊被刪除的字元下標 $index_{left}$ 和最右邊被刪除字元的下標 $index_{right}$，常規套路顯得無從下手。所以，我們嘗試對原問題進行轉換：

  • 思考 1： 假設刪除 left 和 right 兩個字元后能夠滿足條件，那麼刪除 [left,right] 中間所有字元也同樣能滿足條件（貪心思路：刪除更多字元后成為子序列的可能性更大）；
  • 思考 1 結論： 原問題等價於求刪除字串 t 中的最短字串 [i,j]，使得剩餘部分 [0, i - 1] 和 [j + 1, end] 合併後成為字串 s 的一個子序列。
  • 思考 2： 如果字串 t 刪除 [i, j] 區間的字元后能夠滿足條件，那麼一定存在剩餘部分 [0, i - 1] 與字串 s 的字首匹配，而 [j + 1, end] 與字串 s 的字尾匹配，而且這兩段匹配的區域一定 「不存在」 交集。
  • 思考 2 結論： 我們可以列舉字串 s 中的所有分割點，分別位於分割點的 s 字首匹配 t 的字首，用 s 的字尾匹配 t 的字尾，計算匹配後需要減去的子串長度，將所有列舉方案的解取最小值就是原題目的解。

思路參考視訊講解：https://www.bilibili.com/video/BV1GY411i7RP/ —— 靈茶山艾府 著

class Solution {
    fun minimumScore(s: String, t: String): Int {
        // 前字尾分解
        val n = s.length
        val m = t.length
        // s 的字尾和 t 的字尾匹配的最長子串的起始下標
        val sub = IntArray(n + 1).apply {
            var right = m - 1
            for (index in n - 1 downTo 0) {
                if (right >= 0 && s[index] == t[right]) right--
                this[index] = right + 1
            }
            this[n] = m
        }
        // s 的字首和 t 的字首匹配的最長子串的終止下標
        val pre = IntArray(n).apply {
            var left = 0
            for (index in 0..n - 1) {
                if (left < m && s[index] == t[left]) left++
                this[index] = left - 1
            }
        }
        // 列舉分割點
        var result = sub[0]
        if (0 == result) return 0 // 整個 t 是 s 的子序列
        for (index in 0 until n) {
            result = Math.min(result, m - (m - sub[index + 1]) - (pre[index] + 1))
        }
        return result
    }
}

複雜度分析：

  • 時間複雜度：$O(n)$，其中 n 是字串 s 的長度，預處理和列舉的時間複雜度都是 $O(n)$。
  • 空間複雜度：$O(n)$，前字尾陣列的空間。

我們下週見，有用請讚賞上榜！想看小彭的更多題解程式碼，可關注 Github：https://github.com/pengxurui/LeetCode-Kotlin/tree/main/leetcode