文章目錄

• • 1. 比賽結(jié)果
  • 2. 題目
  • • LeetCode 5336. 上升下降字符串 easy
    • LeetCode 5337. 每個元音包含偶數(shù)次的最長子字符串 medium
    • LeetCode 5338. 二叉樹中的最長交錯路徑 medium
    • LeetCode 5339. 二叉搜索子樹的最大鍵值和 hard

1. 比賽結(jié)果

只做出來了第1題，第3題有一個例子超時，沒解決

全國排名：779 / 1913，40.7%；全球排名：2027 / 4729，42.8%

2. 題目

LeetCode 5336. 上升下降字符串 easy

題目鏈接

給你一個字符串 s ，請你根據(jù)下面的算法重新構(gòu)造字符串：

從 s 中選出 最小 的字符，將它 接在 結(jié)果字符串的后面。

從 s 剩余字符中選出 最小 的字符，且該字符比上一個添加的字符大，將它 接在 結(jié)果字符串后面。

重復(fù)步驟 2 ，直到你沒法從 s 中選擇字符。

從 s 中選出 最大 的字符，將它 接在 結(jié)果字符串的后面。

從 s 剩余字符中選出 最大 的字符，且該字符比上一個添加的字符小，將它 接在 結(jié)果字符串后面。

重復(fù)步驟 5 ，直到你沒法從 s 中選擇字符。

重復(fù)步驟 1 到 6 ，直到 s 中所有字符都已經(jīng)被選過。

在任何一步中，如果最小或者最大字符不止一個 ，你可以選擇其中任意一個，并將其添加到結(jié)果字符串。

請你返回將 s 中字符重新排序后的 結(jié)果字符串 。

示例 1： 輸入：s = "aaaabbbbcccc" 輸出："abccbaabccba" 解釋：第一輪的步驟 1，2，3 后，結(jié)果字符串為 result = "abc" 第一輪的步驟 4，5，6 后，結(jié)果字符串為 result = "abccba" 第一輪結(jié)束，現(xiàn)在 s = "aabbcc" ，我們再次回到步驟 1 第二輪的步驟 1，2，3 后，結(jié)果字符串為 result = "abccbaabc" 第二輪的步驟 4，5，6 后，結(jié)果字符串為 result = "abccbaabccba"示例 2： 輸入：s = "rat" 輸出："art" 解釋：單詞 "rat" 在上述算法重排序以后變成 "art"示例 3： 輸入：s = "leetcode" 輸出："cdelotee"示例 4： 輸入：s = "ggggggg" 輸出："ggggggg"示例 5： 輸入：s = "spo" 輸出："ops"提示： 1 <= s.length <= 500 s 只包含小寫英文字母。

---

解答：

• 一次遍歷，對字符進(jìn)行計數(shù)
• 正反遍歷計數(shù)數(shù)組，直到計數(shù)全部為0

class Solution { public:string sortString(string s) {int m[26] = {0}, sum = 0, i;for(auto& ch : s){m[ch-'a']++;sum++;}string ans;while(sum){for(i = 0; i < 26; i++){if(m[i]){ans.push_back(i+'a');sum--;m[i]--;} }for(i = 25; i >= 0; i--){if(m[i]){ans.push_back(i+'a');sum--;m[i]--;} }}return ans;} };

執(zhí)行用時：12 ms
內(nèi)存消耗：9.9 MB

LeetCode 5337. 每個元音包含偶數(shù)次的最長子字符串 medium

題目鏈接

給你一個字符串 s ，請你返回滿足以下條件的最長子字符串的長度：每個元音字母，即 ‘a(chǎn)’，‘e’，‘i’，‘o’，‘u’ ，在子字符串中都恰好出現(xiàn)了偶數(shù)次。

示例 1： 輸入：s = "eleetminicoworoep" 輸出：13 解釋：最長子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 個，以及 0 個 a，u 。示例 2： 輸入：s = "leetcodeisgreat" 輸出：5 解釋：最長子字符串是 "leetc" ，其中包含 2 個 e 。示例 3： 輸入：s = "bcbcbc" 輸出：6 解釋：這個示例中，字符串 "bcbcbc" 本身就是最長的，因為所有的元音 a，e，i，o，u 都出現(xiàn)了 0 次。提示： 1 <= s.length <= 5 x 10^5 s 只包含小寫英文字母。

---

解題：

• 哈希map 記錄所有元音字符的前綴異或值，及當(dāng)前位置
• 當(dāng)哈希表中可以查到該異或值時，說明當(dāng)前位置與查到的位置之間的子串是滿足題意的

舉個例子：

"qacaba"

初始：沒有元音，前綴異或值0，位置記為 -1；m[0] = -1
i = 0，沒有元音，前綴異或值0，0 存在map，len = 0-(-1) = 1，最長“q”；
i = 1，出現(xiàn)元音a，前綴異或值a，位置 1；m[a] = 1
i = 2，沒有元音，前綴異或值a，len = 2-m[a] = 1；
i = 3，出現(xiàn)元音a，前綴異或值a^a=0，len = 3-m[0] = 3-(-1) = 4，最長“qaca”；
i = 4，沒有元音，前綴異或值0，len = 4-m[0] = 4-(-1)=5，最長“qacab”；
i = 5，出現(xiàn)元音a，前綴異或值0^a=a，len = 5-m[a] = 5-1 = 4，最長“caba”；

所以最長的是5個字符qacab

class Solution { public:int findTheLongestSubstring(string s) {unordered_map<int,int> m; // 前綴異或值，對應(yīng)的位置int XOR = 0, i, maxlen = 0;m[0] = -1; //沒有元音，位置為-1，方便計算個數(shù)for(i = 0; i < s.size(); i++) {if(s[i]!='a' && s[i]!='e' && s[i]!='i' && s[i]!='o' && s[i]!='u'){if(m.count(XOR))maxlen = max(maxlen, i-m[XOR]);}else //s[i] 是元音{XOR ^= s[i];//元音異或值if(m.count(XOR))maxlen = max(maxlen, i-m[XOR]);elsem[XOR] = i;}}return maxlen;} };

or

class Solution { public:int findTheLongestSubstring(string s) {unordered_map<int,int> m; // 前綴異或值，對應(yīng)的位置int XOR = 0, i, maxlen = 0;m[0] = -1; //沒有元音，位置為-1，方便計算個數(shù)for(i = 0; i < s.size(); i++) {if(s[i]=='a' || s[i]=='e' || s[i]=='i' || s[i]=='o' || s[i]=='u')XOR ^= s[i];//元音異或值 if(m.count(XOR))maxlen = max(maxlen, i-m[XOR]);elsem[XOR] = i;}return maxlen;} };

執(zhí)行用時：184 ms
內(nèi)存消耗：18.7 MB

LeetCode 5338. 二叉樹中的最長交錯路徑 medium

題目鏈接

給你一棵以 root 為根的二叉樹，二叉樹中的交錯路徑定義如下：

• 選擇二叉樹中 任意 節(jié)點和一個方向（左或者右）。
• 如果前進(jìn)方向為右，那么移動到當(dāng)前節(jié)點的的右子節(jié)點，否則移動到它的左子節(jié)點。
• 改變前進(jìn)方向：左變右或者右變左。
• 重復(fù)第二步和第三步，直到你在樹中無法繼續(xù)移動。

交錯路徑的長度定義為：訪問過的節(jié)點數(shù)目 - 1（單個節(jié)點的路徑長度為 0 ）。

請你返回給定樹中最長 交錯路徑 的長度。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-zigzag-path-in-a-binary-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

---

解題：

52 / 58 個通過測試用例
超時例子，代碼如下：

class Solution {int ans = 0; public:int longestZigZag(TreeNode* root) {if(!root)return 0;dfs(root->left,0,0);dfs(root->right,0,1);longestZigZag(root->left);longestZigZag(root->right);return ans;}void dfs(TreeNode* root, int count, bool dir){if(!root){ans = max(ans,count);return;}if(dir==true)dfs(root->left,count+1,!dir);elsedfs(root->right,count+1,!dir);} };

• 原因：主函數(shù)遍歷了每個點，重復(fù)走了很多次
• 改：在調(diào)用的時候，遇到?jīng)]變方向的，直接count計數(shù)置為 0 ，繼續(xù)向下走。

class Solution {int ans = 0; public:int longestZigZag(TreeNode* root) {if(!root)return 0;dfs(root->left,0,0);dfs(root->right,0,1);return ans;}void dfs(TreeNode* root, int count, bool dir){if(!root) {ans = max(ans,count);return;}if(dir)//前一個是右節(jié)點{dfs(root->left,count+1,0);dfs(root->right,0,1);}else//前一個是左節(jié)點{dfs(root->left,0,0);dfs(root->right,count+1,1);}} };

LeetCode 5339. 二叉搜索子樹的最大鍵值和 hard

題目鏈接

給你一棵以 root 為根的 二叉樹 ，請你返回 任意 二叉搜索子樹的最大鍵值和。

二叉搜索樹的定義如下：

• 任意節(jié)點的左子樹中的鍵值都 小于 此節(jié)點的鍵值。
• 任意節(jié)點的右子樹中的鍵值都 大于 此節(jié)點的鍵值。
• 任意節(jié)點的左子樹和右子樹都是二叉搜索樹。

---

解題：

參考大佬的解法：

• 自底向上，返回4個變量的 vector
• 【0】是不是搜索樹【1】左子樹最小值【2】右子樹最大值【3】子樹val 的 sum
• 空節(jié)點 返回 {true,INT_MAX,INT_MIN,0}
• 獲得左右子樹的狀態(tài)后，開始判斷：
• 都必須是搜索樹，左子樹最大值小于 root，右子樹最小值 大于 root，全部滿足，才是搜索樹

class Solution {int maxSum = 0; public:int maxSumBST(TreeNode* root) {dfs(root);return maxSum;}vector<int> dfs(TreeNode* root) {if(!root)return {true,INT_MAX,INT_MIN,0};//子樹是不是二叉搜索樹 vec[0]//子樹的最小值 vec[1]//子樹的最大值 vec[2]//子樹的sum值 vec[3]auto Lstate = dfs(root->left);auto Rstate = dfs(root->right);if(!Lstate[0] || !Rstate[0] || Lstate[2] >= root->val || Rstate[1] <= root->val)return {false,INT_MAX,INT_MIN,0};//后三個參數(shù)隨意//是二叉搜索樹int Lmin = root->left ? Lstate[1] : root->val;int Rmax = root->right ? Rstate[2] : root->val;int cursum = root->val+Lstate[3]+Rstate[3];maxSum = max(maxSum, cursum);return {true,Lmin,Rmax,cursum};} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 第 21 场双周赛（779/1913，前40.7%）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。