精品一区二区三区2,人人操综合网,婷婷成人色播网五月

LeetCode 雙周賽 113 概覽

T1. 使數(shù)組成為遞增數(shù)組的最少右移次數(shù)（Easy）

標簽：模擬、暴力、線性遍歷

T2. 刪除數(shù)對后的最小數(shù)組長度（Medium）

標簽：二分答案、雙指針、找眾數(shù)、

T3. 統(tǒng)計距離為 k 的點對（Medium）

標簽：枚舉、散列表

T4. 可以到達每一個節(jié)點的最少邊反轉(zhuǎn)次數(shù)（Hard）

標簽：樹上 DP

T1. 使數(shù)組成為遞增數(shù)組的最少右移次數(shù)（Easy）

https://leetcode.cn/problems/minimum-right-shifts-to-sort-the-array/description/

題解一（暴力枚舉）

簡單模擬題。

由于題目數(shù)據(jù)量非常小，可以把數(shù)組復(fù)制一份拼接在尾部，再枚舉從位置 $i$ 開始長為 $n$ 的連續(xù)循環(huán)子數(shù)組是否連續(xù)，是則返回 $(n - i)\%n$ ：

class Solution {
    fun minimumRightShifts(nums: MutableList<Int>): Int {
        val n = nums.size
        nums.addAll(nums)
        for (i in 0 until n) {
            if ((i + 1 ..< i + n).all { nums[it] > nums[it - 1]}) return (n - i) % n
        }
        return -1
    }
}

class Solution:
    def minimumRightShifts(self, nums: List[int]) -> int:
        n = len(nums)
        nums += nums
        for i in range(0, n):
            if all(nums[j] > nums[j - 1] for j in range(i + 1, i + n)):
                return (n - i) % n
        return -1

復(fù)雜度分析：

時間復(fù)雜度： $O(n^2)$ 雙重循環(huán)；
空間復(fù)雜度： $O(n)$ 循環(huán)數(shù)組空間。

題解二（線性遍歷）

更優(yōu)的寫法，我們找到第一個逆序位置，再檢查該位置后續(xù)位置是否全部為升序，且滿足 $nums[n - 1] < nums[0]$ ：

class Solution {
    fun minimumRightShifts(nums: List<Int>): Int {
        val n = nums.size
        for (i in 1 until n) { 
            // 第一段
            if (nums[i] >= nums[i - 1]) continue
            // 第二段
            if (nums[n - 1] > nums[0]) return -1
            for (j in i until n - 1) { 
                if (nums[j] > nums[j + 1]) return -1
            }
            return n - i
        }
        return 0
    }
}

復(fù)雜度分析：

時間復(fù)雜度： $O(n)$ $i$ 指針和 $j$ 指針總計最多移動 $n$ 次；
空間復(fù)雜度： $O(1)$ 僅使用常量級別空間。

T2. 刪除數(shù)對后的最小數(shù)組長度（Medium）

https://leetcode.cn/problems/minimum-array-length-after-pair-removals/

題解一（二分答案）

問題存在單調(diào)性：

當操作次數(shù) $k$ 可以滿足時，操作次數(shù) $k - 1$ 一定能滿足；
當操作次數(shù) $k$ 不可滿足時，操作次數(shù) $k + 1$ 一定不能滿足。

那么，原問題相當于求解滿足目標的最大操作次數(shù)。

現(xiàn)在需要考慮的問題是：如何驗證操作次數(shù) $k$ 是否可以完成？

一些錯誤的思路：

嘗試 1 - 貪心雙指針： $nums[i]$ 優(yōu)先使用最小值， $nums[j]$ 優(yōu)先使用最大值，錯誤用例： $[1 2 3 6]$ ；
嘗試 2 - 貪心： $nums[i]$ 優(yōu)先使用最小值， $nums[j]$ 使用大于 $nums[i]$ 的最小值，錯誤用例： $[1 2 4 6]$ ；
嘗試 3 - 貪心： 從后往前遍歷， $nums[i]$ 優(yōu)先使用較大值， $nums[j]$ 使用大于 $nums[i]$ 的最小值，錯誤用例： $[2 3 4 8]$ 。

開始轉(zhuǎn)換思路：

能否將數(shù)組拆分為兩部分，作為 nums[i] 的分為一組，作為 $nums[j]$ 的分為一組。例如，在用例 $[1 2 | 3 6]$ 和 $[1 2 | 4 6]$ 和 $[2 3 | 4 8]$ 中，將數(shù)組的前部分作為 $nums[i]$ 而后半部分作為 $nums[j]$ 時，可以得到最優(yōu)解，至此發(fā)現(xiàn)貪心規(guī)律。

設(shè)數(shù)組的長度為 $n$ ，最大匹配對數(shù)為 $k$ ：

結(jié)論 1： 使用數(shù)組的左半部分作為 $nums[i]$ 且使用數(shù)組的右半部分作為 $nums[j]$ 總能取到最優(yōu)解。反之，如果使用右半部分的某個數(shù) $nums[t]$ 作為 $nums[i]$ ，相當于占用了一個較大的數(shù)，不利于后續(xù) $nums[i]$ 尋找配對；
結(jié)論 2： 當固定 $nums[i]$ 時， $nums[j]$ 越小越好，否則會占用一個較大的位置，不利于后續(xù) $nums[i]$ 尋找配對。因此最優(yōu)解一定是使用左半部分的最小值與右半部分的最小值配對。

總結(jié)：如果存在 $k$ 對匹配，那么一定可以讓最小的 $k$ 個數(shù)和最大的 $k$ 個數(shù)匹配。

基于以上分析，可以寫出二分答案：

class Solution {
    fun minLengthAfterRemovals(nums: List<Int>): Int {
        val n = nums.size
        var left = 0
        var right = n / 2
        while (left < right) {
            val k = (left + right + 1) ushr 1
            if ((0 ..< k).all { nums[it] < nums[n - k + it] }) {
                left = k
            } else {
                right = k - 1
            }
        }
        return n - 2 * left
    }
}

復(fù)雜度分析：

時間復(fù)雜度： $O(nlgn)$ 二分答案次數(shù)最大為 $lgn$ 次，單次檢驗的時間復(fù)雜度是 $O(n)$ ；
空間復(fù)雜度： $O(1)$ 僅使用常量級別空間。

題解二（雙指針）

基于題解一的分析，以及刪除操作的上界 $n / 2$ ，我們可以僅使用數(shù)組的后半部分與前半部分作比較，具體算法：

i 指針指向索引 $0$
j 指針指向索引 $(n + 1) / 2$
向右枚舉 $j$ 指針，如果 $i$ 、 $j$ 指針指向的位置能夠匹配，則向右移動 $i$ 指針；
最后 $i$ 指針移動的次數(shù)就等于刪除操作次數(shù)。

class Solution {
    fun minLengthAfterRemovals(nums: List<Int>): Int {
        val n = nums.size
        var i = 0
        for (j in (n + 1) / 2 until n) {
            if (nums[i] < nums[j]) i++
        }
        return n - 2 * i
    }
}

復(fù)雜度分析：

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

題解三（眾數(shù)）

由于題目的操作只要滿足 $nums[i] < nums[j]$ ，即兩個數(shù)不相等即可，那么問題的解最終僅取決于數(shù)組中的眾數(shù)的出現(xiàn)次數(shù)：

如果眾數(shù)的出現(xiàn)次數(shù)比其他元素少，那么所有元素都能刪除，問題的結(jié)果就看數(shù)組總長度是奇數(shù)還是偶數(shù)；
否則，剩下的元素就是眾數(shù)： $s - (n - s)$

最后，由于數(shù)組是非遞減的，因此可以在 $O(1)$ 空間求出眾數(shù)的出現(xiàn)次數(shù)：

class Solution {
    fun minLengthAfterRemovals(nums: List<Int>): Int {
        val n = nums.size
        var s = 1
        var cur = 1
        for (i in 1 until n) {
            if (nums[i] == nums[i - 1]) {
                s = max(s, ++ cur)
            } else {
                cur = 1
            }
        }
        if (s <= n - s) {
            return n % 2
        } else {
            return s - (n - s)
        }
    }
}

復(fù)雜度分析：

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

題解四（找規(guī)律 + 二分查找）

繼續(xù)挖掘數(shù)據(jù)規(guī)律：

$s <= n - s$ 等價于眾數(shù)的出現(xiàn)次數(shù)超過數(shù)組長度的一半，由于數(shù)組是有序的，那么一定有數(shù)組的中間位置就是眾數(shù)，我們可以用二分查找找出眾數(shù)在數(shù)組中出現(xiàn)位置的邊界，從而計算出眾數(shù)的出現(xiàn)次數(shù)。

由此，我們甚至不需要線性掃描都能計算出眾數(shù)以及眾數(shù)的出現(xiàn)次數(shù)，Nice！

當然，最后計算出來的出現(xiàn)次數(shù)有可能沒有超過數(shù)組長度的一半。

class Solution {
    fun minLengthAfterRemovals(nums: List<Int>): Int {
        val n = nums.size
        val x = nums[n / 2]
        val s = lowerBound(nums, x + 1) - lowerBound(nums, x)
        return max(2 * s - n, n % 2)
    }

    fun lowerBound(nums: List<Int>, target: Int): Int {
        var left = 0
        var right = nums.size - 1
        while (left < right) {
            val mid = (left + right + 1) ushr 1
            if (nums[mid] >= target) {
                right = mid - 1
            } else {
                left = mid
            }
        }
        return if (nums[left] == target) left else left + 1
    }
}

復(fù)雜度分析：

時間復(fù)雜度： $O(lgn)$ 單次二分查找的時間復(fù)雜度是 $O(lgn)$ ；
空間復(fù)雜度： $O(1)$ 僅使用常量級別空間。

相似題目：

2576. 求出最多標記下標

T3. 統(tǒng)計距離為 k 的點對（Medium）

https://leetcode.cn/problems/count-pairs-of-points-with-distance-k/

題解（散列表）

問題目標： 求 $(x1 xor x2) + (y1 xor y2) == k$ 的方案數(shù)；
技巧： 對于存在多個變量的問題，可以考慮先固定其中一個變量；

容易想到兩數(shù)之和的問題模板，唯一需要思考的問題是如何設(shè)計散列表的存取方式：

對于滿足 $(x1\ xor\ x2) + (y1\ xor\ y2) == k$ 的方案，我們抽象為兩部分 $i + j = k$ ，其中， $i = (x1\ xor\ x2)$ 的取值范圍為 $[0, k]$ ，而 $j = k - i$ ，即總共有 $k + 1$ 種方案。本題的 $k$ 數(shù)據(jù)范圍很小，所以我們可以寫出時間復(fù)雜度 $O(nk)$ 的算法。

class Solution {
    fun countPairs(coordinates: List<List<Int>>, k: Int): Int {
        var ret = 0
        // <x, <y, cnt>>
        val map = HashMap<Int, HashMap<Int, Int>>()
        for ((x2, y2) in coordinates) {
            // 記錄方案
            for (i in 0 .. k) {
                if (!map.containsKey(i xor x2)) continue
                ret += map[i xor x2]!!.getOrDefault((k - i) xor y2, 0)
            }
            // 累計次數(shù)
            map.getOrPut(x2) { HashMap<Int, Int>() }[y2] = map[x2]!!.getOrDefault(y2, 0) + 1
        }
        return ret
    }
}

Python 計數(shù)器支持復(fù)合數(shù)據(jù)類型的建，可以寫出非常簡潔的代碼：

class Solution:
    def countPairs(self, coordinates: List[List[int]], k: int) -> int:
        c = Counter()
        ret = 0
        for x2, y2 in coordinates:
            # 記錄方案
            for i in range(k + 1):
                ret += c[(i ^ x2, (k - i) ^ y2)]
            # 累計次數(shù)
            c[(x2, y2)] += 1
        return ret

復(fù)雜度分析：

時間復(fù)雜度： $O(n·k)$ 線性枚舉，每個元素枚舉 $k$ 種方案；
空間復(fù)雜度： $O(n)$ 散列表空間。

T4. 可以到達每一個節(jié)點的最少邊反轉(zhuǎn)次數(shù)（Hard）

https://leetcode.cn/problems/minimum-edge-reversals-so-every-node-is-reachable/

問題分析

初步分析：

問題目標： 求出以每個節(jié)點為根節(jié)點時，從根節(jié)點到其他節(jié)點的反轉(zhuǎn)操作次數(shù)，此題屬于換根 DP 問題

思考實現(xiàn)：

暴力： 以節(jié)點 $i$ 為根節(jié)點走一次 BFS/DFS，就可以在 $O(n)$ 時間內(nèi)求出每個節(jié)點的解，整體的時間復(fù)雜度是 $O(n^2)$

思考優(yōu)化：

重疊子問題： 相鄰邊連接的節(jié)點間存在重疊子問題，當我們從根節(jié)點 $u$ 移動到其子節(jié)點 $v$ 時，我們可以利用已有信息在 $O(1)$ 時間算出 $v$ 為根節(jié)點時的解。

具體實現(xiàn)：

1、隨機選擇一個點為根節(jié)點 $u$ ，在一次 DFS 中根節(jié)點 $u$ 的反轉(zhuǎn)操作次數(shù)：
2、的狀態(tài)轉(zhuǎn)移：
- 如果 $u → v$ 是正向邊，則反轉(zhuǎn)次數(shù) $+ 1$ ；
- 如果 $u → v$ 是反向邊，則反轉(zhuǎn)次數(shù) $- 1$ （從 $v$ 到 $u$ 不用反轉(zhuǎn)）；
3、由于題目是有向圖，我們可以轉(zhuǎn)換為無向圖，再利用標記位 $1$ 和 $-1$ 表示邊的方向， $1$ 為正向邊， $-1$ 為反向邊。

題解（換根 DP）

class Solution {
    fun minEdgeReversals(n: Int, edges: Array<IntArray>): IntArray {
        val dp = IntArray(n)
        val graph = Array(n) { LinkedList<IntArray>() }
        // 建圖
        for ((from, to) in edges) {
            graph[from].add(intArrayOf(to, 1))
            graph[to].add(intArrayOf(from, -1))
        }

        // 以 0 為根節(jié)點
        fun dfs(i: Int, fa: Int) {
            for ((to, gain) in graph[i]) {
                if (to == fa) continue
                if (gain == -1) dp[0] ++
                dfs(to, i)
            }
        }

        fun dp(i: Int, fa: Int) {
            for ((to, gain) in graph[i]) {
                if (to == fa) continue
                // 狀態(tài)轉(zhuǎn)移
                dp[to] = dp[i] + gain
                dp(to, i)
            }
        }

        dfs(0, -1)
        dp(0, -1)
        
        return dp
    }
}

復(fù)雜度分析：

時間復(fù)雜度： $O(n)$ DFS 和換根 DP 都是 $O(n)$ ；
空間復(fù)雜度： $O(n)$ 遞歸棧空間與 DP 數(shù)組空間。

推薦閱讀

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

LeetCode 單周賽第 361 場 · 同余前綴和問題與經(jīng)典倍增 LCA 算法

LeetCode 單周賽第 360 場 · 當 LeetCode 考樹上倍增，出題的趨勢在變化嗎

LeetCode 雙周賽第 112 場 · 計算機科學(xué)本質(zhì)上是數(shù)學(xué)嗎？

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

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

LeetCode 周賽上分之旅 #45 精妙的 O(lgn) 掃描算法與樹上 DP 問題

LeetCode 周賽上分之旅 #45 精妙的 O(lgn) 掃描算法與樹上 DP 問題

LeetCode 雙周賽 113 概覽

T1. 使數(shù)組成為遞增數(shù)組的最少右移次數(shù)（Easy）

題解一（暴力枚舉）

題解二（線性遍歷）

T2. 刪除數(shù)對后的最小數(shù)組長度（Medium）

題解一（二分答案）

題解二（雙指針）

題解三（眾數(shù)）

題解四（找規(guī)律 + 二分查找）

T3. 統(tǒng)計距離為 k 的點對（Medium）

題解（散列表）

T4. 可以到達每一個節(jié)點的最少邊反轉(zhuǎn)次數(shù)（Hard）

問題分析

題解（換根 DP）

推薦閱讀

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

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

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

LeetCode 周賽上分之旅 #45 精妙的 O(lgn) 掃描算法與樹上 DP 問題

LeetCode 雙周賽 113 概覽

T1. 使數(shù)組成為遞增數(shù)組的最少右移次數(shù)（Easy）

題解一（暴力枚舉）

題解二（線性遍歷）

T2. 刪除數(shù)對后的最小數(shù)組長度（Medium）

題解一（二分答案）

題解二（雙指針）

題解三（眾數(shù)）

題解四（找規(guī)律 + 二分查找）

T3. 統(tǒng)計距離為 k 的點對（Medium）

題解（散列表）

T4. 可以到達每一個節(jié)點的最少邊反轉(zhuǎn)次數(shù)（Hard）

問題分析

題解（換根 DP）

推薦閱讀

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

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

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