<xmp id="63nn9"><video id="63nn9"></video></xmp>

<xmp id="63nn9"></xmp>

<wbr id="63nn9"><ins id="63nn9"></ins></wbr>

<wbr id="63nn9"></wbr><video id="63nn9"><ins id="63nn9"><table id="63nn9"></table></ins></video>

LeetCode 周賽上分之旅 #47 前后綴分解結合單調棧的貢獻問題

?? 本文已收錄到 AndroidFamily,技術和職場問題,請關注公眾號 [彭旭銳] 和 BaguTree Pro 知識星球提問。

學習數據結構與算法的關鍵在于掌握問題背后的算法思維框架,你的思考越抽象,它能覆蓋的問題域就越廣,理解難度也更復雜。在這個專欄里,小彭與你分享每場 LeetCode 周賽的解題報告,一起體會上分之旅。

本文是 LeetCode 上分之旅系列的第 47 篇文章,往期回顧請移步到文章末尾~

LeetCode 周賽 364

T1. 最大二進制奇數(Easy)

  • 標簽:貪心

T2. 美麗塔 I(Medium)

  • 標簽:枚舉、前后綴分解、單調棧

T3. 美麗塔 II(Medium)

  • 標簽:枚舉、前后綴分解、單調棧

T4. 統計樹中的合法路徑數目(Hard)

  • 標簽:DFS、質數


T1. 最大二進制奇數(Easy)

https://leetcode.cn/problems/maximum-odd-binary-number/description/

題解(模擬)

簡單模擬題,先計算 $1$ 的個數,將其中一個 $1$ 置于最低位,其它 $1$ 置于最高位:

class Solution {
    fun maximumOddBinaryNumber(s: String): String {
        val cnt = s.count { it == '1' }
        return StringBuilder().apply {
            repeat(cnt - 1) {
                append("1")
            }
            repeat(s.length - cnt) {
                append("0")
            }
            append("1")
        }.toString()
    }
}
class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        n, cnt = len(s), s.count("1")
        return "1" * (cnt - 1) + "0" * (n - cnt) + "1"
class Solution {
public:
    string maximumOddBinaryNumber(string s) {
       int n = s.length();
       int cnt = 0;
       for (auto& e : s)  {
           if (e == '1') cnt++;
       }
       string ret;
       for (int i = 0; i < cnt - 1; i++) {
           ret.push_back('1');
       }
       for (int i = 0; i < n - cnt; i++) {
           ret.push_back('0');
       }
       ret.push_back('1');
       return ret;
    }
};

復雜度分析:

  • 時間復雜度:$O(n)$ 線性遍歷;
  • 空間復雜度:$O(1)$ 不考慮結果字符串。

T2. 美麗塔 I(Medium)

https://leetcode.cn/problems/beautiful-towers-i/description/

同 T3. 美麗塔 I


T3. 美麗塔 II(Medium)

https://leetcode.cn/problems/beautiful-towers-ii/description/

問題分析

初步分析:

  • 問題目標: 構造滿足條件的方案,使得數組呈現山狀數組,返回元素和;
  • 方案條件: 從數組的最大值向左側為遞減,向右側也為遞減。

思考實現:

  • T2. 美麗塔 I(Medium) 中的數據量只有 $1000$,我們可以枚舉以每個點作為山峰(數組最大值)的方案,從山頂依次向兩側遞減,使得當前位置不高于前一個位置,整體的時間復雜度是 $O(n^2)$;
  • T3. 美麗塔 II(Medium) 中數據量有 $10^5$,我們需要思考低于平方時間復雜度的方法。

思考優化:

以示例 [6,5,3,9,2,7] 為例,我們觀察以 $3$ 和 $9$ 作為山頂的兩個方案:

以 3 作為山頂:
3 3 |3 3| 2 2

以 9 作為山頂
3 3 |3 9| 2 2

可以發現:以 $3$ 作為山頂的左側與以 $9$ 為山頂的右側在兩個方案之間是可以復用的,至此發現解決方法:我們可以分別預處理出以每個節點作為山頂的前綴和后綴的和:

  • $pre[i]$ 表示以 $maxHeights[i]$ 作為山頂時左側段的前綴和;
  • $suf[i]$ 表示以 $maxHeights[i]$ 作為山頂時右側段的后綴和。

那么,最佳方案就是 $pre[i] + suf[i] - maxHeight[i]$ 的最大值。 現在,最后的問題是如何以均攤 $O(1)$ 的時間復雜度計算出每個元素前后綴的和?

思考遞推關系:

繼續以示例 [6,5,3,9,2,7] 為例:

  • 以 $6$ 為山頂,前綴為 $[6]$
  • 以 $5$ 為山頂,需要保證左側元素不大于 $5$,因此找到 $6$ 并修改為 $5$,前綴為 $[5, 5]$
  • 以 $3$ 為山頂,需要保證左側元素不大于 $3$,因此找到兩個 $5$ 并修改為 $3$,前綴為 $[3, 3, 3]$
  • 以 $9$ 為山頂,需要保證左側元素不大于 $9$,不需要修改,前綴為 $[3, 3, 3, 9]$
  • 以 $2$ 為山頂,需要保證左側元素不大于 $2$,修改后為 $[2, 2, 2, 2, 2]$
  • 以 $7$ 為山頂,需要保證左側元素不大于 $7$,不需要修改,前綴為 $[2, 2, 2, 2, 2, 7]$

提高抽象程度:

觀察以上步驟,問題的關鍵在于修改操作:由于數組是遞增的,因此修改的步驟就是在「尋找小于等于當前元素 $x$ 的上一個元素」,再將中間的元素削減為 $x$?!笇ふ疑弦粋€更小元素」,這是單調棧的典型場景。

題解一(枚舉)

枚舉以每個元素作為山頂的方案:

class Solution {
    fun maximumSumOfHeights(maxHeights: List<Int>): Long {
        val n = maxHeights.size
        var ret = 0L
        for (i in maxHeights.indices) {
            var curSum = maxHeights[i].toLong()
            var pre = maxHeights[i]
            for (j in i - 1 downTo 0) {
                pre = min(pre, maxHeights[j])
                curSum += pre
            }
            pre = maxHeights[i]
            for (j in i + 1 ..< n) {
                pre = min(pre, maxHeights[j])
                curSum += pre
            }
            ret = max(ret, curSum)
        }
        return ret
    }
}
class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        n, ret = len(maxHeights), 0
        for i in range(n):
            curSum = maxHeights[i]
            pre = maxHeights[i]
            for j in range(i + 1, n):
                pre = min(pre, maxHeights[j])
                curSum += pre
            pre = maxHeights[i]
            for j in range(i - 1, -1, -1):
                pre = min(pre, maxHeights[j])
                curSum += pre
            ret = max(ret, curSum)
        return ret
class Solution {
public:
    long long maximumSumOfHeights(vector<int>& maxHeights) {
        int n = maxHeights.size();
        long long ret = 0;
        for (int i = 0; i < n; i++) {
            long long curSum = maxHeights[i];
            int pre = maxHeights[i];
            for (int j = i + 1; j < n; j++) {
                pre = min(pre, maxHeights[j]);
                curSum += pre;
            }
            pre = maxHeights[i];
            for (int j = i - 1; j >= 0; j--) {
                pre = min(pre, maxHeights[j]);
                curSum += pre;
            }
            ret = max(ret, curSum);
        }
        return ret;
    }
};

復雜度分析:

  • 時間復雜度:$O(n^2)$ 每個方案的時間復雜度是 $O(n)$,一共有 $n$ 種方案;
  • 空間復雜度:$O(1)$ 僅使用常量級別空間。

題解二(前后綴分解 + 單調棧)

使用單點棧維護前后綴數組,為了便于邊界計算,我們構造長為 $n + 1$ 的數組。以示例 [6,5,3,9,2,7] 為例:

0, 5, 6, 10, 4, 5
13, 8, 6, 2, 1, 0
class Solution {
    fun maximumSumOfHeights(maxHeights: List<Int>): Long {
        val n = maxHeights.size
        val suf = LongArray(n + 1)
        val pre = LongArray(n + 1)
        // 單調棧求前綴
        val stack = java.util.ArrayDeque<Int>()
        for (i in 0 until n) {
            // 彈出棧頂
            while (!stack.isEmpty() && maxHeights[stack.peek()] > maxHeights[i]) {
                stack.pop()
            }
            val j = if (stack.isEmpty()) -1 else stack.peek() 
            pre[i + 1] = pre[j + 1] + 1L * (i - j) * maxHeights[i]
            stack.push(i)
        }
        // 單調棧求后綴
        stack.clear()
        for (i in n - 1 downTo 0) {
            // 彈出棧頂
            while (!stack.isEmpty() && maxHeights[stack.peek()] > maxHeights[i]) {
                stack.pop()
            }
            val j = if (stack.isEmpty()) n else stack.peek()
            suf[i] = suf[j] + 1L * (j - i) * maxHeights[i]
            stack.push(i)
        }
        // 合并
        var ret = 0L
        for (i in 0 until n) {
            ret = max(ret, pre[i + 1] + suf[i] - maxHeights[i])
        }
        return ret
    }
}
class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        n = len(maxHeights)
        suf = [0] * (n + 1)
        pre = [0] * (n + 1)
        stack = []
        # 單調棧求前綴
        for i in range(n):
            # 彈出棧頂
            while stack and maxHeights[stack[-1]] > maxHeights[i]:
                stack.pop()
            j = stack[-1] if stack else -1
            pre[i + 1] = pre[j + 1] + (i - j) * maxHeights[i]
            stack.append(i)
        # 單調棧求后綴
        stack = []
        for i in range(n - 1, -1, -1):
            # 彈出棧頂
            while stack and maxHeights[stack[-1]] > maxHeights[i]:
                stack.pop()
            j = stack[-1] if stack else n
            suf[i] = suf[j] + (j - i) * maxHeights[i]
            stack.append(i)
        # 合并
        ret = 0
        for i in range(n):
            ret = max(ret, pre[i + 1] + suf[i] - maxHeights[i])
        
        return ret
class Solution {
public:
    long long maximumSumOfHeights(vector<int>& maxHeights) {
        int n = maxHeights.size();
        vector<long long> suf(n + 1, 0);
        vector<long long> pre(n + 1, 0);
        stack<int> st;
        // 單調棧求前綴
        for (int i = 0; i < n; i++) {
            // 彈出棧頂
            while (!st.empty() && maxHeights[st.top()] > maxHeights[i]) {
                st.pop();
            }
            int j = st.empty() ? -1 : st.top();
            pre[i + 1] = pre[j + 1] + 1LL * (i - j) * maxHeights[i];
            st.push(i);
        }
        // 單調棧求后綴
        while (!st.empty()) st.pop();
        for (int i = n - 1; i >= 0; i--) {
            // 彈出棧頂
            while (!st.empty() && maxHeights[st.top()] > maxHeights[i]) {
                st.pop();
            }
            int j = st.empty() ? n : st.top();
            suf[i] = suf[j] + 1LL * (j - i) * maxHeights[i];
            st.push(i);
        }
        // 合并
        long long ret = 0;
        for (int i = 0; i < n; i++) {
            ret = max(ret, pre[i + 1] + suf[i] - maxHeights[i]);
        }
        return ret;
    }
};

復雜度分析:

  • 時間復雜度:$O(n)$ 在一側的計算中,每個元素最多如何和出棧 $1$ 次;
  • 空間復雜度:$O(n)$ 前后綴數組空間。

T4. 統計樹中的合法路徑數目(Hard)

https://leetcode.cn/problems/count-valid-paths-in-a-tree/description/

這道題似乎比 T3 還簡單一些。

問題分析

初步分析:

  • 問題目標: 尋找滿足條件的方案數;
  • 問題條件: 路徑 $[a, b]$ 上質數的數目有且僅有 $1$;
  • 問題要素: 路徑和 - 表示路徑上質數的數目。

思考實現:

  • 子問題: 對于以根節點 x 的原問題,可以分為 3 種情況:
    • 左子樹可以構造的方案數
    • 右子樹可以構造的方案數
    • 如果根節點為質數:「從根到子樹節點的路徑和為 $0$ 的數目」與「從根到其它子樹節點的路徑和為 $0$ 的數目」的乘積(乘法原理)

題解(DFS)

構造 DFS 函數,子樹的 DFS 返回值為兩個值:

  • $cnt0$:到子樹節點和為 $0$ 的路徑數;
  • $cnt1$:到子樹節點和為 $1$ 的路徑數;

返回結果時:

  • 如果根節點為質數,那么只能與 $cnt0$ 個路徑和為 $1$ 的路徑;
  • 如果根節點為非質數,那么 $cnt0$ 個路徑可以組成和為 $0$ 的路徑,同理 $cnt1$ 個路徑可以組成和為 $1$ 的路徑。

在子樹的計算過程中還會構造結果:

由于題目說明 $[a, b]$ 與 $[b, a]$ 是相同路徑,我們可以記錄當前子樹左側已經計算過的 $cnt0$ 和 $cnt1$ 的累加和,再與當前子樹的 $cnt0$ 與 $cnt1$ 做乘法:

$ret += cnt0 * cnt[1] + cnt1 * cnt[0]$

class Solution {
    
    companion object {
        val U = 100000
        val primes = LinkedList<Int>()
        val isPrime = BooleanArray(U + 1) { true }
        init {
            isPrime[1] = false
            for (i in 2 .. U) {
                if (isPrime[i]) primes.add(i)
                for (e in primes) {
                    if (i * e > U) break
                    isPrime[i * e] = false
                    if (i % e == 0) break
                }
            }
        }
    }
    
    fun countPaths(n: Int, edges: Array<IntArray>): Long {
        val graph = Array(n + 1) { LinkedList<Int>() }
        for ((from, to) in edges) {
            graph[from].add(to)
            graph[to].add(from)
        }
        
        var ret = 0L
        
        // return 0 和 1 的數量
        fun dfs(i: Int, pre: Int): IntArray {
            // 終止條件
            var cnt = IntArray(2)
            if (isPrime[i]) {
                cnt[1] = 1
            } else {
                cnt[0] = 1
            }
            // 遞歸
            for (to in graph[i]) {
                if (to == pre) continue // 返祖邊
                val (cnt0, cnt1) = dfs(to, i)
                // 記錄方案
                ret += cnt0 * cnt[1] + cnt1 * cnt[0]
                // 記錄影響
                if (isPrime[i]) {
                    cnt[1] += cnt0
                } else {
                    cnt[0] += cnt0
                    cnt[1] += cnt1
                }
            }
            return cnt
        }
        dfs(1, -1) // 隨機選擇根節點
        return ret
    }
}
U = 100000
primes = deque()
isPrime = [True] * (U + 1)

isPrime[1] = False
for i in range(2, U + 1):
    if isPrime[i]: primes.append(i)
    for e in primes:
        if i * e > U: break
        isPrime[i * e] = False
        if i % e == 0: break

class Solution:

    def countPaths(self, n, edges):
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        ret = 0

        def dfs(i, pre):
            nonlocal ret # 修改外部變量
            cnt = [0, 0]
            # 終止條件
            if isPrime[i]:
                cnt[1] = 1
            else:
                cnt[0] = 1
            for to in graph[i]:
                if to == pre: continue # 返祖邊
                cnt0, cnt1 = dfs(to, i)
                # 記錄方案
                ret += cnt0 * cnt[1] + cnt1 * cnt[0]
                # 記錄影響
                if isPrime[i]:
                    cnt[1] += cnt0
                else:
                    cnt[0] += cnt0
                    cnt[1] += cnt1
            return cnt

        dfs(1, -1) # 隨機選擇根節點
        return ret
const int U = 100000;
list<int> primes;
bool isPrime[U + 1];
bool inited = false;

void init() {
    if (inited) return;
    inited = true;
    memset(isPrime, true, sizeof(isPrime));
    isPrime[1] = false;
    for (int i = 2; i <= U; ++i) {
        if (isPrime[i]) primes.push_back(i);
        for (auto e : primes) {
            if (i * e > U) break;
            isPrime[i * e] = false;
            if (i % e == 0) break;
        }
    }
}

class Solution {
public:
    long long countPaths(int n, vector<vector<int>>& edges) {
        init();
        vector<list<int>> graph(n + 1);
        for (const auto& edge : edges) {
            int from = edge[0];
            int to = edge[1];
            graph[from].push_back(to);
            graph[to].push_back(from);
        }

        long long ret = 0;

        // return 0 和 1 的數量
        function<vector<int>(int, int)> dfs = [&](int i, int pre) -> vector<int> {
            // 終止條件
            vector<int> cnt(2, 0);
            if (isPrime[i]) {
                cnt[1] = 1;
            } else {
                cnt[0] = 1;
            }
            // 遞歸
            for (auto to : graph[i]) {
                if (to == pre) continue; // 返祖邊
                vector<int> subCnt = dfs(to, i);
                int cnt0 = subCnt[0];
                int cnt1 = subCnt[1];
                // 記錄方案
                ret += cnt0 * cnt[1] + cnt1 * cnt[0];
                // 記錄影響
                if (isPrime[i]) {
                    cnt[1] += cnt0;
                } else {
                    cnt[0] += cnt0;
                    cnt[1] += cnt1;
                }
            }
            return cnt;
        };
        dfs(1, -1); // 隨機選擇根節點
        return ret;
    }
};

復雜度分析:

  • 時間復雜度:預處理時間為 $O(U)$,建圖時間 和 DFS 時間為 $O(n)$;
  • 空間復雜度:預處理空間為 $O(U)$,模擬空間為 $O(n)$。

枚舉質數

OI - 素數篩法

枚舉法:枚舉 $[2, n]$ ,判斷它是不是質數,整體時間復雜度是 $O(n\sqrt{n})$

// 暴力求質數
fun getPrimes(max: Int): IntArray {
    val primes = LinkedList<Int>()
    for (num in 2..max) {
        if (isPrime(num)) primes.add(num)
    }
    return primes.toIntArray()
}

// 質數判斷
fun isPrime(num: Int): Boolean {
    var x = 2
    while (x * x <= num) {
        if (num % x == 0) return false
        x++
    }
    return true
}

Eratosthenes 埃氏篩:如果 $x$ 是質數,那么 $x$ 的整數倍 $2x$、$3x$ 一定不是質數。我們設 isPrime[i] 表示 $i$ 是否為質數。從小開始遍歷,如果 $i$ 是質數,則同時將所有倍數標記為合數,整體時間復雜度是 $O(nlgn)$

為什么要從 $x^2$, $2x^2$ 開始標記,而不是 $2x$, $3x$ 開始標記,因為 $2x$, $3x$ 已經被小于 $x$ 的質數標記過。

// 埃氏篩求質數
val primes = LinkedList<Int>()
val isPrime = BooleanArray(U + 1) { true }
for (i in 2..U) {
    // 檢查是否為質數,這里不需要調用 isPrime() 函數判斷是否質數,因為它沒被小于它的數標記過,那么一定不是合數
    if (!isPrime[i]) continue
    primes.add(i)
    // 標記
    var x = i * i
    while (x <= U) {
        isPrime[x] = false
        x += i
    }
}

Euler 歐氏線性篩:盡管我們從 $x^2$ 開始標記來減少重復標記,但埃氏篩還是會重復標記合數。為了避免重復標記,標記 $x$ 與 “小于等于 $x$ 的最小質因子的質數” 的乘積為合數,保證每個合數只被標記最小的質因子標記,整體時間復雜度是 $O(n)$

// 線性篩求質數
val primes = LinkedList<Int>()
val isPrime = BooleanArray(U + 1) { true }
for (i in 2..U) {
    // 檢查是否為質數,這里不需要調用 isPrime() 函數判斷是否質數,因為它沒被小于它的數標記過,那么一定不是合數
    if (isPrime[i]) {
        primes.add(i)
    }
    // 標記
    for (e in primes) {
        if (i * e > U) break
        isPrime[i * e] = false
        if (i % e == 0) break
    }
}

推薦閱讀

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

?? 永遠相信美好的事情即將發生,歡迎加入小彭的 Android 交流社群~

posted @ 2023-09-24 20:16  彭旭銳  閱讀(26)  評論(0編輯  收藏  舉報
人碰人摸人爱免费视频播放

<xmp id="63nn9"><video id="63nn9"></video></xmp>

<xmp id="63nn9"></xmp>

<wbr id="63nn9"><ins id="63nn9"></ins></wbr>

<wbr id="63nn9"></wbr><video id="63nn9"><ins id="63nn9"><table id="63nn9"></table></ins></video>