LeetCode 周賽 365
- 標(biāo)簽：模擬、前后綴分解、線性遍歷
- 標(biāo)簽：模擬、前后綴分解、線性遍歷
T3. 無限數(shù)組的最短子數(shù)組（Medium）
- 標(biāo)簽：滑動窗口
- 標(biāo)簽：內(nèi)向基環(huán)樹、拓?fù)渑判?、DFS
T1. 有序三元組中的最大值 I（Easy）
https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-i/description/
同 T2。
T2. 有序三元組中的最大值 II（Medium）
https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-ii/description/
問題分析
初步分析：
- 問題目標(biāo)： 構(gòu)造滿足條件的合法方案，使得計算結(jié)果最大；
-
問題條件： 數(shù)組下標(biāo)滿足
的三位數(shù)；
-
計算結(jié)果：
。
思考實(shí)現(xiàn)：
-
T1. 有序三元組中的最大值 I 的數(shù)據(jù)量只有
，枚舉所有合法的
組合，時間復(fù)雜度是
；
-
T2. 有序三元組中的最大值 II 的數(shù)據(jù)量有
，我們需要思考更優(yōu)解法。
思考優(yōu)化：
為了使得計算結(jié)果盡可能大，顯然應(yīng)該讓乘法的左右兩部分盡可能大。對于存在多個變量的問題，一個重要的技巧是 「固定一個，思考另一個」 ，這就容易多了。
-
固定
： 為了讓結(jié)果更大，應(yīng)該找到
左邊最大的
和右邊最大的
組合，時間復(fù)雜度是
。我們也可以使用前后綴分解預(yù)處理出來，這樣時間復(fù)雜度就是
；
-
固定
： 同理，固定
最大的方案，這可以實(shí)現(xiàn)線性時間和常量空間。
題解一（枚舉）
枚舉所有方案，記錄最優(yōu)解。
class Solution {
fun maximumTripletValue(nums: IntArray): Long {
var ret = 0L
val n = nums.size
for (i in 0 until n) {
for (j in i + 1 until n) {
for (k in j + 1 until n) {
ret = max(ret, 1L * (nums[i] - nums[j]) * nums[k])
}
}
}
return ret
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
- 空間復(fù)雜度：
題解二（前后綴分解）
預(yù)處理出每個位置前后的最大值，再枚舉 記錄最優(yōu)解。
class Solution {
fun maximumTripletValue(nums: IntArray): Long {
val n = nums.size
val preMax = IntArray(n)
var sufMax = IntArray(n)
for (i in 1 until n) {
preMax[i] = max(preMax[i - 1], nums[i - 1])
}
for (i in n - 2 downTo 0) {
sufMax[i] = max(sufMax[i + 1], nums[i + 1])
}
return max(0, (1 .. n - 2).maxOf { 1L * (preMax[it] - nums[it]) * sufMax[it] })
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
- 空間復(fù)雜度：
題解三（線性遍歷）
線性遍歷 并記錄
的最大值，記錄最優(yōu)解。
class Solution {
fun maximumTripletValue(nums: IntArray): Long {
val n = nums.size
var ret = 0L
var maxDelta = 0
var maxI = 0
for (e in nums) {
ret = max(ret, 1L * maxDelta * e)
maxDelta = max(maxDelta, maxI - e)
maxI = max(maxI, e)
}
return ret
}
}
class Solution:
def maximumTripletValue(self, nums: List[int]) -> int:
ret = maxDelta = maxI = 0
for e in nums:
ret = max(ret, maxDelta * e)
maxDelta = max(maxDelta, maxI - e)
maxI = max(maxI, e)
return ret
class Solution {
public:
long long maximumTripletValue(vector<int> &nums) {
long long ret = 0;
int max_delta = 0, max_i = 0;
for (int e : nums) {
ret = max(ret, (long long) max_delta * e);
max_delta = max(max_delta, max_i - e);
max_i = max(max_i, e);
}
return ret;
}
};
復(fù)雜度分析：
- 時間復(fù)雜度：
- 空間復(fù)雜度：
T3. 無限數(shù)組的最短子數(shù)組（Medium）
https://leetcode.cn/problems/minimum-size-subarray-in-infinite-array/description/
問題分析
令 數(shù)組的整體元素和為
，考慮
的兩種情況：
- 對于
很小的情況（小于數(shù)組整體和
）：這是很簡單的滑動窗口問題；
- 對于
的子數(shù)組。
class Solution {
fun minSizeSubarray(nums: IntArray, t: Int): Int {
val n = nums.size
val s = nums.sum()
val k = t % s
// 同向雙指針
var left = 0
var sum = 0
var len = n
for (right in 0 until 2 * n) {
sum += nums[right % n]
while (sum > k) {
sum -= nums[left % n]
left ++
}
if (sum == k) len = min(len, right - left + 1)
}
return if (len == n) -1 else n * (t / s) + len
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
倍數(shù)組長度；
- 空間復(fù)雜度：僅使用常量級別空間。
T4. 有向圖訪問計數(shù)（Hard）
https://leetcode.cn/problems/count-visited-nodes-in-a-directed-graph/description/
問題分析
初步分析：
對于 個點(diǎn)
條邊的有向弱連通圖，圖中每個點(diǎn)的出度都是
，因此它是一棵 「內(nèi)向基環(huán)樹」。那么，對于每個點(diǎn)有
種情況：
- 環(huán)上節(jié)點(diǎn)：繞環(huán)行走一圈后就會回到當(dāng)前位置，因此最長訪問路徑就是環(huán)長；
- 樹鏈節(jié)點(diǎn)：那么從樹鏈走到環(huán)上后也可以繞環(huán)行走一圈，因此最長訪問路徑就是走到環(huán)的路徑 + 環(huán)長。
思考實(shí)現(xiàn)：
- 只有一個連通分量的情況： 那么問題就相對簡單，我們用拓?fù)渑判蚣羧滏?，并記錄鏈上?jié)點(diǎn)的深度（到環(huán)上的距離），最后剩下的部分就是基環(huán)；
- 有多個連通分量的情況： 我們需要枚舉每個連通分量的基環(huán)，再將基環(huán)的長度累加到該連通分量的每個節(jié)點(diǎn)。
題解（拓?fù)渑判?+ DFS）
- 第一個問題：將基環(huán)的長度累加到該連通分量的每個節(jié)點(diǎn)
拓?fù)渑判驕p去樹鏈很容易實(shí)現(xiàn)，考慮到我們這道題在找到基環(huán)后需要反向遍歷樹鏈，因此我們考慮構(gòu)造反向圖（外向基環(huán)樹）；
- 第二個問題：找到基環(huán)長度
在拓?fù)渑判蚝?，樹鏈上?jié)點(diǎn)的入度都是 ，因此入度大于
的節(jié)點(diǎn)就位于基環(huán)上。枚舉未訪問的基環(huán)節(jié)點(diǎn)走 DFS，就可以找到該連通分量的基環(huán)。
class Solution {
fun countVisitedNodes(edges: List<Int>): IntArray {
// 內(nèi)向基環(huán)樹
val n = edges.size
val degree = IntArray(n)
val graph = Array(n) { LinkedList<Int>() }
for ((x,y) in edges.withIndex()) {
graph[y].add(x)
degree[y]++ // 入度
}
// 拓?fù)渑判? val ret = IntArray(n)
var queue = LinkedList<Int>()
for (i in 0 until n) {
if (0 == degree[i]) queue.offer(i)
}
while(!queue.isEmpty()) {
val x = queue.poll()
val y = edges[x]
if (0 == -- degree[y]) queue.offer(y)
}
// 反向 DFS
fun rdfs(i: Int, depth: Int) {
for (to in graph[i]) {
if (degree[to] == -1) continue
ret[to] = depth
rdfs(to, depth + 1)
}
}
// 枚舉連通分量
for (i in 0 until n) {
if (degree[i] <= 0) continue
val ring = LinkedList<Int>()
var x = i
while (true) {
degree[x] = -1
ring.add(x)
x = edges[x]
if (x == i) break
}
for (e in ring) {
ret[e] = ring.size
rdfs(e, ring.size + 1)
}
}
return ret
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
- 空間復(fù)雜度：
題解二（樸素 DFS）
思路參考小羊的題解。
我們發(fā)現(xiàn)這道題的核心在于 「找到每個基環(huán)的節(jié)點(diǎn)」 ，除了拓?fù)渑判蚣糁ν猓瑢τ趦?nèi)向基環(huán)樹來，從任何一個節(jié)點(diǎn)走 DFS 走到的最后一個節(jié)點(diǎn)一定是基環(huán)上的節(jié)點(diǎn)。
在細(xì)節(jié)上，對于每個未訪問過的節(jié)點(diǎn)走 DFS 的結(jié)果會存在 種情況：
- 環(huán)上節(jié)點(diǎn)：剛好走過基環(huán)；
- 樹鏈節(jié)點(diǎn)：走過樹鏈 + 基環(huán)。
- 還有
種情況：DFS 起點(diǎn)是從樹鏈的末端走的，而前面樹鏈的部分和基環(huán)都被走過，此時 DFS 終點(diǎn)就不一定是基環(huán)節(jié)點(diǎn)了。這種情況就同理從終點(diǎn)直接反向遍歷就好了，等于說省略了處理基環(huán)的步驟。
class Solution {
fun countVisitedNodes(edges: List<Int>): IntArray {
val n = edges.size
val ret = IntArray(n)
val visit = BooleanArray(n)
for (i in 0 until n) {
if (visit[i]) continue
// DFS
val link = LinkedList<Int>()
var x = i
while (!visit[x]) {
visit[x] = true
link.add(x)
x = edges[x]
}
if (ret[x] == 0) {
val depth = link.size - link.indexOf(x) // (此時 x 位于基環(huán)入口)
repeat(depth) {
ret[link.pollLast()] = depth
}
}
var depth = ret[x]
while (!link.isEmpty()) {
ret[link.pollLast()] = ++depth
}
}
return ret
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：
- 空間復(fù)雜度：
推薦閱讀
LeetCode 上分之旅系列往期回顧：
