題目列表

3541. 找到頻率最高的元音和輔音
3542. 將所有元素變為 0 的最少操作次數
3543. K 條邊路徑的最大邊權和
3544. 子樹反轉和

一、找到頻率最高的元音和輔音

分別統計元音和輔音的出現次數最大值，然后相加即可，代碼如下

// C++
class Solution {const string str = "aeiou";
public:int maxFreqSum(string s) {int cnt[26]{};int mx1 = 0, mx2 = 0;for(auto & e : s){cnt[e - 'a']++;if(str.find(e) == string::npos){mx1 = max(mx1, cnt[e - 'a']); // 更新輔音}else{mx2 = max(mx2, cnt[e - 'a']); // 更新輔音}}return mx1 + mx2;}
};

# Python
class Solution:def maxFreqSum(self, s: str) -> int:cnt = [0] * 26mx1 = 0mx2 = 0for e in s:x = ord(e) - ord('a')cnt[x] += 1if e in "aeiou":mx1 = max(mx1, cnt[x])else:mx2 = max(mx2, cnt[x])return mx1 + mx2

二、將所有元素變為 0 的最少操作次數

本題的難點在于一旦我們將區間內的最小值變為 0，那么剩余的不為 0 的數字就會被分成一段一段的區間，此時，我們需要在這些區間內再去進行操作，而這需要我們維護區間內的最小值，顯然很困難，那有沒有什么其他的思路？

• 思路
  對于一個數字 x 來說，只有當它是區間內的最小值時，才可以通過操作被置為 0，而從貪心的角度來說，這個區間越大，則置為 0 的數越多，所進行的操作就會越少。所以我們只要計算對于同一個數字 x，它需要被分為多少個區間，才能讓所有的 x 全部變為 0，而它分出的區間數就是它需要進行的最少操作次數。統計所有的數字對于答案的貢獻即可

  • 這里暗含一個貪心的策略，優先將小的數字置為 0 會更優，因為小的數字置為 0，它依舊是小的數字，不會影響大的數字的分區個數，但是反過來，大的數字置為 0，就有可能將小的數字分成更多的區間，導致操作次數變多
  • 故這里我們計算出每個數字區間個數后直接相加，看似不論順序，實質是從小的數字開始進行操作
  • 求解 x 為最小數字的區間，本質是求距離 x 最近的比它小的數字下標，可以用單調棧來求解

// C++
class Solution {
public:int minOperations(vector<int>& nums) {int n = nums.size();stack<int> st;vector<int> left(n, -1), right(n, n);// 計算區間for(int i = 0; i < n; i++){while(st.size() && nums[st.top()] > nums[i]){right[st.top()] = i;st.pop();}st.push(i);}st = stack<int>();for(int i = n - 1; i >= 0; i--){while(st.size() && nums[st.top()] > nums[i]){left[st.top()] = i;st.pop();}st.push(i);}unordered_map<int,set<pair<int,int>>> mp;for(int i = 0; i < n; i++){mp[nums[i]].emplace(left[i], right[i]);}int ans = 0;for(auto& [x, st] : mp){if(x){ // x = 0 不需要進行操作ans += st.size();}}return ans;}
};

• 優化

  • 對于求區間個數的操作，我們可以在一次循環中得到，具體如下

// C++
class Solution {
public:int minOperations(vector<int>& nums) {int n = nums.size(), ans = 0;stack<int> st; // 單調遞增 & 棧中無重復數字 & 不包含 0for(int i = 0; i < n; i++){while(st.size() && nums[st.top()] >= nums[i]){// 這里只統計一定需要進行一次操作的數字個數，即左右邊界已經明確的數字// 和 nums[i] 相同的數字，由于右邊界還不確定，此處不統計，等區間明確后在統計if(nums[st.top()] != nums[i]){ans++;}st.pop();}if(nums[i]) // 0 不需要入棧st.push(i);}// 棧中剩余的數字，此時右邊界已經確定，也需要進行一次操作才能被置為 0return ans + st.size();}
};

#Python
class Solution:def minOperations(self, nums: List[int]) -> int:ans = 0bottom, top = 0, 0 # 可以直接將 nums 當作棧進行使用，空間復雜度為 O(1)for i in range(len(nums)):while bottom != top and nums[top-1] >= nums[i]:if nums[top-1] != nums[i]:ans += 1top -= 1if nums[i] > 0:nums[top] = nums[i]top += 1return ans + top - bottom

三、K 條邊路徑的最大邊權和

本題先建圖，然后直接用 dfs 進行遍歷即可，注意，為了防止重復遍歷某個狀態，需要記憶化已經遍歷過的狀態，代碼如下

// C++
class Solution {
public:int maxWeight(int n, vector<vector<int>>& edges, int k, int t) {vector<vector<pair<int,int>>> g(n);for(auto& e : edges){g[e[0]].emplace_back(e[1], e[2]);}int ans = -1;set<tuple<int,int,int>> st; // 記憶化遍歷過的狀態auto dfs = [&](this auto&& dfs, int x, int d, int s)->void{if(d == k){ans = max(ans, s);return;}if(st.count({x, d, s}))return;st.emplace(x, d, s);for(auto& [y, w] : g[x]){if(s + w < t){dfs(y, d + 1, w + s);}}};for(int i = 0; i < n; i++){dfs(i, 0, 0);}return ans;}
};

# Python
class Solution:def maxWeight(self, n: int, edges: List[List[int]], k: int, t: int) -> int:g = [[] for _ in range(n)]for x, y, w in edges:g[x].append((y, w))ans = -1@cachedef dfs(x:int, d:int, s:int):if d == k:nonlocal ansans = max(ans, s)returnfor y, w in g[x]:if w + s < t:dfs(y, d + 1, w + s)for i in range(n):dfs(i, 0, 0)return ans

四、子樹反轉和

本題的反轉操作有距離限制，也就是說對當前結點進行反轉操作之后，與它距離小于 k 的結點就不能進行反轉操作了，所以我們在 dfs 遍結點的時候，需要增加兩個參數 mul : 表示當前的結點取正還是取負，cd : 多少距離后，就能再次進行反轉操作，故我們有 dfs(x,fa,mul,cd)

• 當 x 結點不反轉時，$dfs(x,fa,mul,cd)=sum(dfs(y,x,mul,(cd?cd?1,0)))+(mul?nums[x]:?nums[x])$，其中 y 是結點 x 的所有子節點
• 當 x 結點反轉且 cd == 0 時，$dfs(x,fa,mul,cd)=sum(dfs(y,x,!mul,k?1))+(mul??nums[x]:nums[x])$，其中 y 是結點 x 的所有子節點

代碼如下

// C++
class Solution {
public:long long subtreeInversionSum(vector<vector<int>>& edges, vector<int>& nums, int k) {int n = nums.size();vector<vector<int>> g(n);for(auto & e : edges){g[e[0]].push_back(e[1]);g[e[1]].push_back(e[0]);}vector memo(n, vector(2, vector<long long>(k, -1)));auto dfs = [&](this auto&& dfs, int x, int fa, bool mul, int cd)->long long{ // f0, cd0, f1if(memo[x][mul][cd] != -1) return memo[x][mul][cd];long long res = mul ? nums[x] : -nums[x];for(int y : g[x]){if(y != fa){res += dfs(y, x, mul, (cd ? cd - 1 : 0));}}if(cd == 0){long long res2 = mul ? -nums[x] : nums[x];for(int y : g[x]){if(y != fa){res2 += dfs(y, x, !mul, k - 1);}}res = max(res, res2);}return memo[x][mul][cd] = res;};return dfs(0, -1, true, 0);}
};

# Python
class Solution:def subtreeInversionSum(self, edges: List[List[int]], nums: List[int], k: int) -> int:n = len(nums)g = [[] for _ in range(n)]for x,y in edges:g[x].append(y)g[y].append(x)memo = {}def dfs(x:int, fa:int, mul:bool, cd:int)->int:t = (x, mul, cd)if t in memo:return memo[t]res = nums[x] if mul else -nums[x]for y in g[x]:if y != fa:res += dfs(y, x, mul, cd - 1 if cd > 0 else 0)if cd == 0:res2 = -nums[x] if mul else nums[x]for y in g[x]:if y != fa:res2 += dfs(y, x, not mul, k - 1)res = max(res, res2)memo[t] = resreturn resreturn dfs(0, -1, True, 0)