LeetCode 雙周賽 113 概覽
T1. 使數(shù)組成為遞增數(shù)組的最少右移次數(shù)（Easy）
- 標簽：模擬、暴力、線性遍歷
T2. 刪除數(shù)對后的最小數(shù)組長度（Medium）
- 標簽：二分答案轻腺、雙指針帖努、找眾數(shù)、
T3. 統(tǒng)計距離為 k 的點對（Medium）
- 標簽：枚舉宇姚、散列表
T4. 可以到達每一個節(jié)點的最少邊反轉次數(shù)（Hard）
- 標簽：樹上 DP
T1. 使數(shù)組成為遞增數(shù)組的最少右移次數(shù)（Easy）
https://leetcode.cn/problems/minimum-right-shifts-to-sort-the-array/description/
題解一（暴力枚舉）
簡單模擬題尝哆。
由于題目數(shù)據(jù)量非常小秉撇，可以把數(shù)組復制一份拼接在尾部，再枚舉從位置 開始長為
的連續(xù)循環(huán)子數(shù)組是否連續(xù)较解，是則返回
：
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
復雜度分析：
- 時間復雜度：
雙重循環(huán)畜疾；
- 空間復雜度：
循環(huán)數(shù)組空間赴邻。
題解二（線性遍歷）
更優(yōu)的寫法印衔，我們找到第一個逆序位置，再檢查該位置后續(xù)位置是否全部為升序姥敛，且滿足 ：
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
}
}
復雜度分析：
- 時間復雜度：
指針和
指針總計最多移動
次奸焙；
- 空間復雜度：
僅使用常量級別空間。
T2. 刪除數(shù)對后的最小數(shù)組長度（Medium）
https://leetcode.cn/problems/minimum-array-length-after-pair-removals/
題解一（二分答案）
問題存在單調性：
- 當操作次數(shù)
可以滿足時彤敛，操作次數(shù)
一定能滿足与帆；
- 當操作次數(shù)
一定不能滿足墨榄。
那么玄糟，原問題相當于求解滿足目標的最大操作次數(shù)。
現(xiàn)在需要考慮的問題是：如何驗證操作次數(shù) 是否可以完成袄秩？
一些錯誤的思路：
-
嘗試 1 - 貪心雙指針：
優(yōu)先使用最小值阵翎，
優(yōu)先使用最大值，錯誤用例：
之剧；
-
嘗試 2 - 貪心：
背稼；
-
嘗試 3 - 貪心： 從后往前遍歷贰军，
词疼。
開始轉換思路：
能否將數(shù)組拆分為兩部分，作為 nums[i] 的分為一組帘腹，作為 的分為一組寒跳。 例如，在用例
和
和
中竹椒，將數(shù)組的前部分作為
而后半部分作為
時童太，可以得到最優(yōu)解，至此發(fā)現(xiàn)貪心規(guī)律。
設數(shù)組的長度為 书释，最大匹配對數(shù)為
：
-
結論 1： 使用數(shù)組的左半部分作為
作為
-
結論 2： 當固定
總結：如果存在 對匹配，那么一定可以讓最小的
個數(shù)和最大的
個數(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
}
}
復雜度分析：
- 時間復雜度：
二分答案次數(shù)最大為
次，單次檢驗的時間復雜度是
- 空間復雜度：
題解二（雙指針）
基于題解一的分析，以及刪除操作的上界 吏恭，我們可以僅使用數(shù)組的后半部分與前半部分作比較拗小，具體算法：
- i 指針指向索引
- j 指針指向索引
- 向右枚舉
- 最后
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
}
}
復雜度分析：
- 時間復雜度：
- 空間復雜度：
題解三（眾數(shù)）
由于題目的操作只要滿足 盏筐，即兩個數(shù)不相等即可围俘，那么問題的解最終僅取決于數(shù)組中的眾數(shù)的出現(xiàn)次數(shù)：
- 如果眾數(shù)的出現(xiàn)次數(shù)比其他元素少，那么所有元素都能刪除琢融，問題的結果就看數(shù)組總長度是奇數(shù)還是偶數(shù)界牡；
- 否則，剩下的元素就是眾數(shù)：
最后漾抬，由于數(shù)組是非遞減的宿亡，因此可以在 空間求出眾數(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)
}
}
}
復雜度分析：
- 時間復雜度：
- 空間復雜度：
題解四（找規(guī)律 + 二分查找）
繼續(xù)挖掘數(shù)據(jù)規(guī)律：
等價于眾數(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
}
}
復雜度分析：
- 時間復雜度：
單次二分查找的時間復雜度是
- 空間復雜度：
相似題目：
T3. 統(tǒng)計距離為 k 的點對（Medium）
https://leetcode.cn/problems/count-pairs-of-points-with-distance-k/
題解（散列表）
-
問題目標： 求
的方案數(shù)叹括；
- 技巧： 對于存在多個變量的問題算墨，可以考慮先固定其中一個變量；
容易想到兩數(shù)之和的問題模板领猾，唯一需要思考的問題是如何設計散列表的存取方式：
對于滿足 的方案米同，我們抽象為兩部分
骇扇，其中摔竿，
的取值范圍為
，而
少孝，即總共有
種方案继低。本題的
數(shù)據(jù)范圍很小，所以我們可以寫出時間復雜度
的算法稍走。
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ù)器支持復合數(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
復雜度分析：
- 時間復雜度：
線性枚舉，每個元素枚舉
- 空間復雜度：
T4. 可以到達每一個節(jié)點的最少邊反轉次數(shù)（Hard）
https://leetcode.cn/problems/minimum-edge-reversals-so-every-node-is-reachable/
問題分析
初步分析：
- 問題目標： 求出以每個節(jié)點為根節(jié)點時，從根節(jié)點到其他節(jié)點的反轉操作次數(shù)狐树，此題屬于換根 DP 問題
思考實現(xiàn)：
-
暴力： 以節(jié)點
思考優(yōu)化：
-
重疊子問題： 相鄰邊連接的節(jié)點間存在重疊子問題抑钟，當我們從根節(jié)點
移動到其子節(jié)點
時涯曲，我們可以利用已有信息在
具體實現(xiàn)：
- 1在塔、隨機選擇一個點為根節(jié)點
- 2、
的狀態(tài)轉移：
- 如果
绰沥；
- 如果
（從
- 如果
- 3徽曲、由于題目是有向圖态兴，我們可以轉換為無向圖，再利用標記位
和
表示邊的方向疟位，
題解（換根 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)轉移
dp[to] = dp[i] + gain
dp(to, i)
}
}
dfs(0, -1)
dp(0, -1)
return dp
}
}
復雜度分析：
- 時間復雜度：
- 空間復雜度：
推薦閱讀
LeetCode 上分之旅系列往期回顧：
