周賽 357
T1. 故障鍵盤（Easy）
- 標(biāo)簽：模擬完残、字符串
T2. 判斷是否能拆分?jǐn)?shù)組（Medium）
- 標(biāo)簽：思維
T3. 找出最安全路徑（Medium）
- 標(biāo)簽：BFS业稼、連通性盗痒、分層并查集、極大化極小、二分查找
T4. 子序列最大優(yōu)雅度（Hard）
- 標(biāo)簽：貪心俯邓、排序骡楼、堆
T1. 故障鍵盤（Easy）
https://leetcode.cn/problems/faulty-keyboard/
題解（模擬）
簡(jiǎn)單模擬題。
- 在遇到
i字符時(shí)對(duì)已填入字符進(jìn)行反轉(zhuǎn)稽鞭，時(shí)間復(fù)雜度是 O(n^2)鸟整； - 使用隊(duì)列和標(biāo)記位可以優(yōu)化時(shí)間復(fù)雜度，在遇到
i時(shí)修改標(biāo)記位和寫入方向朦蕴，在最后輸出時(shí)根據(jù)標(biāo)記位輸出篮条，避免中間的反轉(zhuǎn)操作。
class Solution {
public:
string finalString(string s) {
vector<char> dst;
for (auto& c : s) {
if (c == 'i') {
reverse(dst.begin(), dst.end());
} else {
dst.push_back(c);
}
}
return string(dst.begin(), dst.end());
}
};
class Solution {
public:
string finalString(string s) {
deque<char> dst;
bool rear = true;
for (auto& c : s) {
if (c == 'i') {
rear = !rear;
} else {
if (rear) {
dst.push_back(c);
} else {
dst.push_front(c);
}
}
}
return rear ? string(dst.begin(), dst.end()) : string(dst.rbegin(), dst.rend());
}
};
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
線性遍歷和輸出時(shí)間吩抓；
- 空間復(fù)雜度：
T2. 判斷是否能拆分?jǐn)?shù)組（Medium）
https://leetcode.cn/problems/check-if-it-is-possible-to-split-array/
題解（思維題）
思維題，主要題目的兩個(gè)條件只要滿足其中一個(gè)即可 ??
- 條件 1：子數(shù)組的長(zhǎng)度為 1 ? 說(shuō)明數(shù)組長(zhǎng)度小于等于 2 的時(shí)候疹娶，一定可以滿足（子數(shù)組的長(zhǎng)度不大于 1）伴栓；
- 條件 2：子數(shù)組元素之和大于或等于 m ? 需滿足子數(shù)組 {a1, a2, a3} 與 {a4, a5, a6} 的子數(shù)組和均大于等于 m。
結(jié)合兩個(gè)條件雨饺，如果我們能找到兩個(gè)相鄰的元素之和大于等于 m钳垮，那么總可以通過消除 1 個(gè)元素的方式完成題目要求。
例如在示例 3 [2, 3, 3, 2, 3] 中沛膳，我們以 [3,3] 為起點(diǎn)倒推：
- [3, 3]
- [2, 3, 3] 消除 2
- [2, 3, 3, 2] 消除 2
- [2, 3, 3, 2, 3] 消除 3
class Solution {
public:
bool canSplitArray(vector<int>& nums, int m) {
// 2 | 3, 3 | 2 | 3
// 1, 3, 2, 2, 3
// 1, 1, 1, 3, 3
if (nums.size() <= 2) return true;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] + nums[i - 1] >= m) return true;
}
return false;
}
};
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
- 空間復(fù)雜度：
僅使用常量級(jí)別空間。
T3. 找出最安全路徑（Medium）
https://leetcode.cn/problems/find-the-safest-path-in-a-grid/
題解一（多源 BFS + 二分答案）
根據(jù)題目描述锹安，每個(gè)節(jié)點(diǎn)的安全系數(shù)定位為該節(jié)點(diǎn)到「小偷」節(jié)點(diǎn)的最小曼哈頓距離短荐，而題目要求是尋找從 [0][0] 到 [n-1][n-1] 的最大安全系數(shù)√究蓿「使得最小曼哈頓距離最大」暗示可能是需要使用二分答案的極大化極小問題忍宋。
- 多源 BFS 預(yù)處理： 先從每個(gè)「小偷」節(jié)點(diǎn)開始走 BFS 更新相鄰節(jié)點(diǎn)的最小曼哈頓距離，單次 BFS 的時(shí)間復(fù)雜度是 O(n^2)风罩，雖然我們可以用剪枝優(yōu)化糠排，但整體的時(shí)間復(fù)雜度上界是 O(n^4)。為了優(yōu)化時(shí)間復(fù)雜度超升，我們使用多源 BFS（也可以理解為拓?fù)渑判蛉牖拢看螐棾龅墓?jié)點(diǎn)的曼哈頓距離最小）室琢，整體的時(shí)間僅為 O(n^2)乾闰；
-
二分答案： 安全系數(shù)與路徑可達(dá)性存在單調(diào)性：
- 當(dāng)安全系數(shù)越大時(shí)，越不容易可達(dá)盈滴；
- 當(dāng)安全系數(shù)越小時(shí)涯肩，越容易可達(dá)。
- 安全系數(shù)的下界為 0，上界為 n * 2 - 1病苗，通過二分答案尋找滿足可達(dá)性的最大安全系數(shù)：
class Solution {
fun maximumSafenessFactor(grid: List<List<Int>>): Int {
val INF = Integer.MAX_VALUE
val directions = arrayOf(intArrayOf(0,1), intArrayOf(1,0), intArrayOf(0,-1), intArrayOf(-1,0))
val n = grid.size
// 特判
if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return 0
// 多源 BFS（拓?fù)渑判颍? val safe = Array(n) { IntArray(n) { -1 }}
var queue = LinkedList<IntArray>()
for (r in 0 until n) {
for (c in 0 until n) {
if (grid[r][c] == 1) {
queue.offer(intArrayOf(r, c))
safe[r][c] = 0
}
}
}
while (!queue.isEmpty()) {
val temp = LinkedList<IntArray>()
for (node in queue) {
for (direction in directions) {
val newX = node[0] + direction[0]
val newY = node[1] + direction[1]
if (newX < 0 || newX >= n || newY < 0 || newY >= n || safe[newX][newY] != -1) continue
temp.offer(intArrayOf(newX, newY))
safe[newX][newY] = safe[node[0]][node[1]] + 1
}
}
queue = temp
}
// for (row in safe) println(row.joinToString())
// BFS（檢查只通過大于等于 limit 的格子疗垛，能否到達(dá)終點(diǎn)）
fun check(limit: Int) : Boolean {
val visit = Array(n) { BooleanArray(n) }
var queue = LinkedList<IntArray>()
queue.offer(intArrayOf(0, 0))
visit[0][0] = true
while (!queue.isEmpty()) {
val temp = LinkedList<IntArray>()
for (node in queue) {
// 終止條件
if (node[0] == n - 1 && node[1] == n - 1) return true
for (direction in directions) {
val newX = node[0] + direction[0]
val newY = node[1] + direction[1]
if (newX < 0 || newX >= n || newY < 0 || newY >= n || visit[newX][newY] || safe[newX][newY] < limit) continue
temp.offer(intArrayOf(newX, newY))
visit[newX][newY] = true
}
}
queue = temp
}
return false
}
// 二分查找
var left = 0
var right = Math.min(safe[0][0], safe[n - 1][n - 1])
while (left < right) {
val mid = (left + right + 1) ushr 1
if (!check(mid)) {
right = mid - 1
} else {
left = mid
}
}
return left
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
其中 多源 BFS 時(shí)間為
，單次檢查的 BFS 時(shí)間復(fù)雜度為
贷腕，整體時(shí)間復(fù)雜度是
- 空間復(fù)雜度：
題解二（多源 BFS + 堆）
思路參考雪景式的題解花履。
在題解一預(yù)處理的基礎(chǔ)上，同樣走一次 BFS 也能夠算出最大安全系數(shù)挚赊，思路類似于 Dijkstra 最最短路算法中使用當(dāng)前最短路最短的節(jié)點(diǎn)去松弛相鄰邊，我們優(yōu)先讓當(dāng)前曼哈頓距離最大的節(jié)點(diǎn)去松弛相鄰節(jié)點(diǎn)济瓢，以保證每個(gè)節(jié)點(diǎn)都能夠從較大的路徑轉(zhuǎn)移過來(lái)荠割。
class Solution {
fun maximumSafenessFactor(grid: List<List<Int>>): Int {
...
// 類最短路（使用曼哈頓距離最大的節(jié)點(diǎn)去松弛相鄰邊）
val heap = PriorityQueue<IntArray>() { e1, e2 ->
e2[0] - e1[0]
}
heap.offer(intArrayOf(safe[0][0], 0, 0))
val visit = Array(n) { BooleanArray(n) }
visit[0][0] = true
while (!heap.isEmpty()) {
val node = heap.poll()
if (node[1] == n - 1 && node[2] == n - 1) return node[0]
for (direction in directions) {
val newX = node[1] + direction[0]
val newY = node[2] + direction[1]
if (newX < 0 || newX >= n || newY < 0 || newY >= n || visit[newX][newY]) continue
// 松弛相鄰邊
heap.offer(intArrayOf(Math.min(node[0], safe[newX][newY]), newX, newY))
visit[newX][newY] = true
}
}
return 0
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
- 空間復(fù)雜度：
題解三（多源 BFS + 分層并查集）
思路參考靈神的題解。
其實(shí)箕宙，求從 [0][0] 到 [n - 1][n - 1] 的最大安全系數(shù)嚎朽，也相當(dāng)于連通性問題的變形，而連通性問題有并查集的解法柬帕。為了求得最大安全系數(shù)哟忍，我們使用分層并查集：
- 首先，在預(yù)處理階段求出每個(gè)節(jié)點(diǎn)的最小曼哈頓距離陷寝，并將節(jié)點(diǎn)按照曼哈頓距離分類锅很；
- 其次，我們從最大的曼哈頓距離開始逆序合并凤跑，當(dāng) [0][0] 和 [n - 1][n - 1] 連通時(shí)返回結(jié)果爆安。
class Solution {
fun maximumSafenessFactor(grid: List<List<Int>>): Int {
val directions = arrayOf(intArrayOf(0,1), intArrayOf(1,0), intArrayOf(0,-1), intArrayOf(-1,0))
val n = grid.size
// 特判
if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return 0
// 多源 BFS（拓?fù)渑判颍? val safe = Array(n) { IntArray(n) { -1 }}
// 分層
val groups = LinkedList<LinkedList<IntArray>>()
var queue = LinkedList<IntArray>()
for (r in 0 until n) {
for (c in 0 until n) {
if (grid[r][c] == 1) {
queue.offer(intArrayOf(r, c))
safe[r][c] = 0
}
}
}
groups.add(queue)
while (!queue.isEmpty()) {
val temp = LinkedList<IntArray>()
for (node in queue) {
for (direction in directions) {
val newX = node[0] + direction[0]
val newY = node[1] + direction[1]
if (newX < 0 || newX >= n || newY < 0 || newY >= n || safe[newX][newY] != -1) continue
temp.offer(intArrayOf(newX, newY))
safe[newX][newY] = safe[node[0]][node[1]] + 1
}
}
queue = temp
if (!queue.isEmpty()) groups.add(queue)
}
// for (row in safe) println(row.joinToString())
// for (row in groups) println(row.joinToString())
val helper = UnionFind(n)
// 逆序合并
for (i in groups.size - 1 downTo 0) {
for (node in groups[i]) {
val x = node[0]
val y = node[1]
for (direction in directions) {
val newX = x + direction[0]
val newY = y + direction[1]
// 合并曼哈頓距離大于等于當(dāng)前層的節(jié)點(diǎn)
if (newX < 0 || newX >= n || newY < 0 || newY >= n || safe[newX][newY] < i) continue
helper.union(x * n + y, newX * n + newY)
}
}
if (helper.find(0) == helper.find(n * n - 1)) return i
}
return 0
}
class UnionFind(private val n: Int) {
private val parents = IntArray(n * n) { it }
private val ranks = IntArray(n * n)
fun find(x: Int): Int {
var cur = x
while (cur != parents[cur]) {
parents[cur] = parents[parents[cur]]
cur = parents[cur]
}
return cur
}
fun union(x: Int, y: Int) {
val rootX = find(x)
val rootY = find(y)
if (ranks[rootX] < ranks[rootY]) {
parents[rootX] = rootY
} else if (ranks[rootX] > ranks[rootY]){
parents[rootY] = rootX
} else {
parents[rootY] = rootX
ranks[rootX]++
}
}
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
- 空間復(fù)雜度：
T4. 子序列最大優(yōu)雅度（Hard）
https://leetcode.cn/problems/maximum-elegance-of-a-k-length-subsequence/
題解（反悔貪心 + 堆）
-
固定一個(gè)維度： 題目定義的優(yōu)雅度 total_profit + distinct_categories^2 存在兩個(gè)維度的變量，我們考慮固定其中一個(gè)維度來(lái)簡(jiǎn)化問題討論：
- 對(duì)所有節(jié)點(diǎn)按照利潤(rùn)從大到小逆序排列咖耘，并選擇前 k 個(gè)節(jié)點(diǎn)翘簇，此時(shí)的 total_profit 是最大的；
- 在此基礎(chǔ)上鲤看，我們繼續(xù)遍歷剩余的 n - k 個(gè)節(jié)點(diǎn)缘揪，并考慮替換前 k 個(gè)節(jié)點(diǎn)中的某個(gè)節(jié)點(diǎn)，由于已經(jīng)選擇的節(jié)點(diǎn) total_profit 是最大的，因此需要讓替換后的類目數(shù)變多找筝。
-
分類討論（替換哪個(gè)）：
- 1蹈垢、如果某個(gè)已選節(jié)點(diǎn)與第 i 個(gè)節(jié)點(diǎn)的類目相同，那么替換后不會(huì)讓類目數(shù)變大袖裕，不可能讓優(yōu)雅度變大曹抬；
- 2、如果某個(gè)已選節(jié)點(diǎn)與第 i 個(gè)節(jié)點(diǎn)的類目不同急鳄，但只出現(xiàn)一次谤民，那么替換出不會(huì)讓類目變大，不可能讓優(yōu)雅度變大疾宏。否則张足，如果出現(xiàn)多次，替換后類目數(shù)變大坎藐，有可能讓優(yōu)雅度變大为牍；
- 3、為了讓優(yōu)雅度盡可能大岩馍，我們期望替換后的 total_profit 的減少量盡可能小碉咆，同時(shí)數(shù)目類別應(yīng)該增大，否則無(wú)法獲得更大的優(yōu)雅度蛀恩。為了讓替換后的 total_profit 的減少量盡可能小疫铜，我們應(yīng)該替換已選列表中利潤(rùn)最小同時(shí)重復(fù)的節(jié)點(diǎn)。
-
怎么高效替換：
- 使用堆維護(hù)利潤(rùn)最小同時(shí)重復(fù)的元素双谆，由于我們是從大到小線性枚舉的壳咕，因此直接使用線性表模擬堆的能力；
- 新替換進(jìn)去的不會(huì)被替換出去（想想為什么）顽馋。
class Solution {
fun findMaximumElegance(items: Array<IntArray>, k: Int): Long {
Arrays.sort(items) { e1, e2 ->
e2[0] - e1[0]
}
var ret = 0L
var totalProfit = 0L
// duplicate：小頂堆
val duplicate = LinkedList<Int>()
// categorySet：類目表
val categorySet = HashSet<Int>()
for ((i, item) in items.withIndex()) {
val profit = item[0]
val category = item[1]
if (i < k) {
totalProfit += item[0]
// 記錄重復(fù)節(jié)點(diǎn)
if (categorySet.contains(category)) {
duplicate.add(profit)
}
categorySet.add(category)
} else if (!duplicate.isEmpty() && !categorySet.contains(category)){
// 替換
totalProfit += profit - duplicate.pollLast()
categorySet.add(category)
} else {
// 不會(huì)讓類目數(shù)量變大
}
// println(duplicate.joinToString())
ret = Math.max(ret, totalProfit + 1L * categorySet.size * categorySet.size)
}
return ret
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
瓶頸在排序囱井；
- 空間復(fù)雜度：
推薦閱讀
LeetCode 上分之旅系列往期回顧：
