- 往期回顧:LeetCode 單周賽第 348 場 · 數位 DP 模版學會了嗎?
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) 查詢索引數組空間 + 散清單空間。
往期回顧
- LeetCode 單周賽第 348 場 · 數位 DP 模版學會了嗎?
- LeetCode 單周賽第 347 場 · 二維空間上的 LIS 最長遞增子序列問題
- LeetCode 雙周賽第 104 場 · 流水的動态規劃,鐵打的結構化思考
- LeetCode 雙周賽第 103 場 · 區間求和的樹狀數組經典應用