亚洲日韩诱惑,九九一区二区三区

周賽 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/

題解（模擬）

簡單模擬題。

在遇到 i 字符時對已填入字符進(jìn)行反轉(zhuǎn)，時間復(fù)雜度是 O(n^2)；
使用隊列和標(biāo)記位可以優(yōu)化時間復(fù)雜度，在遇到 i 時修改標(biāo)記位和寫入方向，在最后輸出時根據(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ù)雜度分析：

時間復(fù)雜度： $O(n)$ 線性遍歷和輸出時間；
空間復(fù)雜度： $O(n)$ 臨時字符串空間。

T2. 判斷是否能拆分?jǐn)?shù)組（Medium）

https://leetcode.cn/problems/check-if-it-is-possible-to-split-array/

題解（思維題）

思維題，主要題目的兩個條件只要滿足其中一個即可 ??

條件 1：子數(shù)組的長度為 1 ? 說明數(shù)組長度小于等于 2 的時候，一定可以滿足（子數(shù)組的長度不大于 1）；
條件 2：子數(shù)組元素之和大于或等于 m ? 需滿足子數(shù)組 {a1, a2, a3} 與 {a4, a5, a6} 的子數(shù)組和均大于等于 m。

結(jié)合兩個條件，如果我們能找到兩個相鄰的元素之和大于等于 m，那么總可以通過消除 1 個元素的方式完成題目要求。

例如在示例 3 [2, 3, 3, 2, 3] 中，我們以 [3,3] 為起點倒推：

[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ù)雜度分析：

時間復(fù)雜度： $O(n)$ 線性遍歷時間；
空間復(fù)雜度： $O(1)$ 僅使用常量級別空間。

T3. 找出最安全路徑（Medium）

https://leetcode.cn/problems/find-the-safest-path-in-a-grid/

題解一（多源 BFS + 二分答案）

根據(jù)題目描述，每個節(jié)點的安全系數(shù)定位為該節(jié)點到「小偷」節(jié)點的最小曼哈頓距離，而題目要求是尋找從 [0][0] 到 [n-1][n-1] 的最大安全系數(shù)?！甘沟米钚÷D距離最大」暗示可能是需要使用二分答案的極大化極小問題。

多源 BFS 預(yù)處理： 先從每個「小偷」節(jié)點開始走 BFS 更新相鄰節(jié)點的最小曼哈頓距離，單次 BFS 的時間復(fù)雜度是 O(n^2)，雖然我們可以用剪枝優(yōu)化，但整體的時間復(fù)雜度上界是 O(n^4)。為了優(yōu)化時間復(fù)雜度，我們使用多源 BFS（也可以理解為拓?fù)渑判?，每次彈出的?jié)點的曼哈頓距離最?。?，整體的時間僅為 O(n^2)；
二分答案： 安全系數(shù)與路徑可達(dá)性存在單調(diào)性：
- 當(dāng)安全系數(shù)越大時，越不容易可達(dá)；
- 當(dāng)安全系數(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á)終點）
        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ù)雜度分析：

時間復(fù)雜度： $O(n^2·lgn^2)$ 其中多源 BFS 時間為 $O(n^2)$ ，單次檢查的 BFS 時間復(fù)雜度為 $O(n^2)$ ，二分的次數(shù)為 $lgn^2$ ，整體時間復(fù)雜度是 $O(n^2·lgn^2)$ ；
空間復(fù)雜度： $O(n^2)$ safe 安全系數(shù)矩陣空間。

題解二（多源 BFS + 堆）

思路參考雪景式的題解。

在題解一預(yù)處理的基礎(chǔ)上，同樣走一次 BFS 也能夠算出最大安全系數(shù)，思路類似于 Dijkstra 最最短路算法中使用當(dāng)前最短路最短的節(jié)點去松弛相鄰邊，我們優(yōu)先讓當(dāng)前曼哈頓距離最大的節(jié)點去松弛相鄰節(jié)點，以保證每個節(jié)點都能夠從較大的路徑轉(zhuǎn)移過來。

class Solution {
    fun maximumSafenessFactor(grid: List<List<Int>>): Int {
        ...
        // 類最短路（使用曼哈頓距離最大的節(jié)點去松弛相鄰邊）
        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ù)雜度分析：

時間復(fù)雜度： $O(n^2·lgn^2)$ 其中多源 BFS 時間為 $O(n^2)$ ，基于堆的 BFS 的時間復(fù)雜度為 $O(n^2·lgn^2)$ ；
空間復(fù)雜度： $O(n^2)$ safe 安全系數(shù)矩陣空間。

題解三（多源 BFS + 分層并查集）

思路參考靈神的題解。

其實，求從 [0][0] 到 [n - 1][n - 1] 的最大安全系數(shù)，也相當(dāng)于連通性問題的變形，而連通性問題有并查集的解法。為了求得最大安全系數(shù)，我們使用分層并查集：

首先，在預(yù)處理階段求出每個節(jié)點的最小曼哈頓距離，并將節(jié)點按照曼哈頓距離分類；
其次，我們從最大的曼哈頓距離開始逆序合并，當(dāng) [0][0] 和 [n - 1][n - 1] 連通時返回結(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é)點
                    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ù)雜度分析：

時間復(fù)雜度： $O(n^2)$ 其中多源 BFS 時間為 $O(n^2)$ ，基于路徑壓縮和按秩合并的并查集時間復(fù)雜度為 $O(n^2)$ ；
空間復(fù)雜度： $O(n^2)$ safe 安全系數(shù)矩陣空間。

T4. 子序列最大優(yōu)雅度（Hard）

https://leetcode.cn/problems/maximum-elegance-of-a-k-length-subsequence/

題解（反悔貪心 + 堆）

固定一個維度： 題目定義的優(yōu)雅度 total_profit + distinct_categories^2 存在兩個維度的變量，我們考慮固定其中一個維度來簡化問題討論：
- 對所有節(jié)點按照利潤從大到小逆序排列，并選擇前 k 個節(jié)點，此時的 total_profit 是最大的；
- 在此基礎(chǔ)上，我們繼續(xù)遍歷剩余的 n - k 個節(jié)點，并考慮替換前 k 個節(jié)點中的某個節(jié)點，由于已經(jīng)選擇的節(jié)點 total_profit 是最大的，因此需要讓替換后的類目數(shù)變多。
分類討論（替換哪個）：
- 1、如果某個已選節(jié)點與第 i 個節(jié)點的類目相同，那么替換后不會讓類目數(shù)變大，不可能讓優(yōu)雅度變大；
- 2、如果某個已選節(jié)點與第 i 個節(jié)點的類目不同，但只出現(xiàn)一次，那么替換出不會讓類目變大，不可能讓優(yōu)雅度變大。否則，如果出現(xiàn)多次，替換后類目數(shù)變大，有可能讓優(yōu)雅度變大；
- 3、為了讓優(yōu)雅度盡可能大，我們期望替換后的 total_profit 的減少量盡可能小，同時數(shù)目類別應(yīng)該增大，否則無法獲得更大的優(yōu)雅度。為了讓替換后的 total_profit 的減少量盡可能小，我們應(yīng)該替換已選列表中利潤最小同時重復(fù)的節(jié)點。
怎么高效替換：
- 使用堆維護(hù)利潤最小同時重復(fù)的元素，由于我們是從大到小線性枚舉的，因此直接使用線性表模擬堆的能力；
- 新替換進(jìn)去的不會被替換出去（想想為什么）。

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é)點
                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 {
                // 不會讓類目數(shù)量變大
            }
            // println(duplicate.joinToString())
            ret = Math.max(ret, totalProfit + 1L * categorySet.size * categorySet.size)
        }
        return ret
    }
}

復(fù)雜度分析：

時間復(fù)雜度： $O(nlgn)$ 瓶頸在排序；
空間復(fù)雜度： $O(n)$ 堆空間。

推薦閱讀

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

LeetCode 單周賽第 356 場 · KMP 字符串匹配殊途同歸

LeetCode 單周賽第 355 場 · 兩題坐牢，菜雞現(xiàn)出原形

LeetCode 雙周賽第 109 場 · 按部就班地解決動態(tài)規(guī)劃問題

LeetCode 雙周賽第 107 場 · 很有意思的 T2 題

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

LeetCode 周賽上分之旅 # 37 多源 BFS 與連通性問題

LeetCode 周賽上分之旅 # 37 多源 BFS 與連通性問題

周賽 357

T1. 故障鍵盤（Easy）

題解（模擬）

T2. 判斷是否能拆分?jǐn)?shù)組（Medium）

題解（思維題）

T3. 找出最安全路徑（Medium）

題解一（多源 BFS + 二分答案）

題解二（多源 BFS + 堆）

題解三（多源 BFS + 分層并查集）

T4. 子序列最大優(yōu)雅度（Hard）

題解（反悔貪心 + 堆）

推薦閱讀

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

LeetCode 周賽上分之旅 # 37 多源 BFS 與連通性問題

周賽 357

T1. 故障鍵盤（Easy）

題解（模擬）

T2. 判斷是否能拆分?jǐn)?shù)組（Medium）

題解（思維題）

T3. 找出最安全路徑（Medium）

題解一（多源 BFS + 二分答案）

題解二（多源 BFS + 堆）

題解三（多源 BFS + 分層并查集）

T4. 子序列最大優(yōu)雅度（Hard）

題解（反悔貪心 + 堆）

推薦閱讀

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av