技術文章 » LeetCode 雙週賽 107（2023/06/24）滑動視窗與離散化

LeetCode 雙週賽 107（2023/06/24）滑動視窗與離散化

2023-06-26 06:00:36

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

T1. 最大字串配對數目（Easy）

  • 標籤：雜湊表

T2. 構造最長的新字串（Medium）

  • 標籤：模擬

T3. 字串連線刪減字母（Medium）

  • 標籤：狀態 DP

T4. 統計沒有收到請求的伺服器數目（Medium）

  • 標籤：排序、滑動視窗、離散化

T1. 最大字串配對數目（Easy）

https://leetcode.cn/problems/find-maximum-number-of-string-pairs/

題解（雜湊表）

題目說明所有字串不相同，因此我們可以列舉每個字串，檢查其反轉是否存在，模板類似於兩數之和；

  • 擴充套件：如果字串存在重複，可以將配對的字元分組再按兩兩配對計算；
  • 擴充套件：如果字串長度很長會存在雜湊衝突，可以調整 U 為較大素數。
class Solution {
    fun maximumNumberOfStringPairs(words: Array<String>): Int {
        val U = 26
        val set = HashSet<Int>()
        var ret = 0
        for (word in words) {
            if (word.length != 2) continue
            val key = (word[0] - 'a') * U + (word[1] - 'a')
            val reversedKey = (word[1] - 'a') * U + (word[0] - 'a')
            if (set.contains(reversedKey)) ret ++
            set.add(key)
        }
        return ret
    }
}

複雜度分析：

  • 時間複雜度：$O(L)$ 需要存取每個單詞的每個字元；
  • 空間複雜度：$O(n)$ 雜湊表空間。

T2. 構造最長的新字串（Medium）

https://leetcode.cn/problems/construct-the-longest-new-string/

題解（模擬）

根據題意分析，我們總可以將 ABAB..ABAB 置於結果中間，再將 AA 或 BB 置於兩邊。此時所有 AB 都可選，而 AA BB 最多隻能選擇較少者 + 1，分類討論即可：

class Solution {
    fun longestString(x: Int, y: Int, z: Int): Int {
        return if (x == y) {
            (x + y + z) * 2
        } else {
            (Math.min(x, y) * 2 + 1 + z) * 2
        }
    }
}

複雜度分析：

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

T3. 字串連線刪減字母（Medium）

https://leetcode.cn/problems/decremental-string-concatenation/

題解（狀態 DP）

  • 對於每個字串 [i]，有拼接到前方或拼接到後方兩種方案；
  • 當考慮 join(i, i + 1) 時，我們只需要關心兩個字串的首尾 4 個字元，對於中間的字元是不關心的。因此在遍歷到字串 [i] 時，我們檢查以 [i - 1] 為結尾的子問題的可能方案，並維護以 [i] 為結尾的子問題的所有方案。
class Solution {
    fun minimizeConcatenatedLength(words: Array<String>): Int {
        val INF = 0x3F3F3F3F
        val n = words.size
        val dp = Array(n) { Array(26) { IntArray(26) { INF } }}
        // 起始狀態
        dp[0][words[0][0] - 'a'][words[0][words[0].length - 1] - 'a'] = words[0].length
        for (i in 1 until n) {
            val word = words[i]
            val x = word[0] - 'a'
            val y = word[word.length - 1] - 'a'
            // 列舉子問題狀態
            for (j in 0 until 26) {
                for (k in 0 until 26) {
                    // 拼接到前方
                    if (y == j) {
                        dp[i][x][k] = Math.min(dp[i][x][k], dp[i - 1][j][k] + word.length - 1)
                    } else {
                        dp[i][x][k] = Math.min(dp[i][x][k], dp[i - 1][j][k] + word.length)
                    }
                    // 拼接到後方
                    if (x == k) {
                        dp[i][j][y] = Math.min(dp[i][j][y], dp[i - 1][j][k] + word.length - 1)
                    } else {
                        dp[i][j][y] = Math.min(dp[i][j][y], dp[i - 1][j][k] + word.length)
                    }
                }
            }
        }
        var ret = INF
        for (j in 0 until 26) {
            for (k in 0 until 26) {
                ret = Math.min(ret, dp[n - 1][j][k])
            }
        }
        return ret
    }
}

複雜度分析：

  • 時間複雜度：$O(n·C^2)$ C= 26
  • 空間複雜度：$O(n·C^2)$

T4. 統計沒有收到請求的伺服器數目（Medium）

https://leetcode.cn/problems/count-zero-request-servers/

題解一（暴力）

線性掃描紀錄檔，併線性掃描查詢列表，將紀錄檔記錄投遞到對應的查詢中，同時使用雜湊表對相同伺服器去重。

class Solution {
    fun countServers(n: Int, logs: Array<IntArray>, x: Int, queries: IntArray): IntArray {
        val m = queries.size
        val sets = Array(m) { HashSet<Int>() }
        val ret = IntArray(m)
        // 暴力
        for (log in logs) {
            for ((i, query) in queries.withIndex()) {
                if (log[1] in query - x .. query) {
                    sets[i].add(log[0])
                }
            }
        }
        // 輸出
        for (i in 0 until m) {
            ret[i] = n - sets[i].size
        }
        return ret
    }
}

複雜度分析：

  • 時間複雜度：$O(nm)$ 超出時間限制；
  • 空間複雜度：$O(nm)$ 雜湊表空間，最壞情況下每個查詢中包含所有伺服器記錄。

題解二（排序 + 滑動視窗 + 離散化）

需要注意題目中的單調性，對於紀錄檔時間 log_i < log_j，當 log_i 時間晚於 query_k 時，那麼紀錄檔時間更晚的 log_k 必然無法投遞到 query_k 中，而暴力演演算法中沒有利用單調性質。因此，我們先對 log 紀錄檔列表和 queries 查詢列表按時間順序排序，再來使用滑動視窗來維護每個查詢中覆蓋的紀錄檔資訊。

class Solution {
    fun countServers(n: Int, logs: Array<IntArray>, x: Int, queries: IntArray): IntArray {
        val l = logs.size
        val m = queries.size
        val ret = IntArray(m)
        // 查詢索引
        val indexs = Array(m) { it }
        // 排序
        Arrays.sort(logs) { i1, i2 ->
            i1[1] - i2[1]
        }
        Arrays.sort(indexs) { i1, i2 -> 
            queries[i1] - queries[i2]
        }
        // 滑動視窗 + 離散化
        var i = 0
        var j = 0
        val cnts = HashMap<Int, Int>()
        for (id in indexs) {
            val to = queries[id]
            if (to <= x) throw IllegalStateException()
            // 拓展右指標
            while (j < l && logs[j][1] <= to) {
                cnts[logs[j][0]] = cnts.getOrDefault(logs[j][0], 0) + 1
                j++
            }
            // 收縮左指標
            while (i < l && logs[i][1] <  to - x) {
                cnts[logs[i][0]] = cnts[logs[i][0]]!! - 1
                if (cnts[logs[i][0]]!! == 0) cnts.remove(logs[i][0])
                i++
            }
            ret[id] = n - cnts.size
        }
        return ret
    }
}

複雜度分析：

  • 時間複雜度：$O(mlgm + llogl + m + l)$ 瓶頸在排序；
  • 空間複雜度：$O(m + n)$ 查詢索引陣列空間 + 雜湊表空間。

往期回顧