双周赛 – 21

1. 上升下降字符串

给你一个字符串 s ,请你根据下面的算法重新构造字符串:

  1. 从 s 中选出 最小 的字符,将它 接在 结果字符串的后面。
  2. 从 s 剩余字符中选出 最小 的字符,且该字符比上一个添加的字符大,将它 接在 结果字符串后面。
  3. 重复步骤 2 ,直到你没法从 s 中选择字符。
  4. 从 s 中选出 最大 的字符,将它 接在 结果字符串的后面。
  5. 从 s 剩余字符中选出 最大 的字符,且该字符比上一个添加的字符小,将它 接在 结果字符串后面。
  6. 重复步骤 5 ,直到你没法从 s 中选择字符。
  7. 重复步骤 1 到 6 ,直到 s 中所有字符都已经被选过。

在任何一步中,如果最小或者最大字符不止一个 ,你可以选择其中任意一个,并将其添加到结果字符串。
请你返回将 s 中字符重新排序后的 结果字符串

样例

示例 1:

输入:s = “aaaabbbbcccc”
输出:”abccbaabccba”
解释:第一轮的步骤 1,2,3 后,结果字符串为 result = “abc”
第一轮的步骤 4,5,6 后,结果字符串为 result = “abccba”
第一轮结束,现在 s = “aabbcc” ,我们再次回到步骤 1
第二轮的步骤 1,2,3 后,结果字符串为 result = “abccbaabc”
第二轮的步骤 4,5,6 后,结果字符串为 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 只包含小写英文字母。

代码

viv丑陋版

题目简单翻译一下就是将原有字符串包含的字符按照波浪形式输出
统计每个字母出现的次数。然后分别从’a’到’z’和从’z’到’a’遍历一遍,如果有未输出次数则输出。

class Solution {
public:
    string sortString(string s) {
        int cnt[26]; memset(cnt, 0, sizeof(cnt));
        int n = s.size();
        for(int i=0; i<n; i++) cnt[s[i]-'a']++;
        string ans;
        while(n) {
            for(int i=0; i<26; i++) if(cnt[i] > 0) ans += i + 'a', cnt[i]--, n--;
            for(int i=25; i>=0; i--) if(cnt[i] > 0) ans += i + 'a', cnt[i]--, n--;
        }
        return ans;
    }
};

zz美丽版

zz的视频还没出,但是我看到他代码之后不想知道他的思路了……
我的zz被掉包了???

class Solution {
public:
    string sortString(string s) {
        int n = s.length(), cnt = 0;
        string ans = "";
        
        bool vis[n];
        memset(vis, false, sizeof(vis));
        
        while(cnt < n){
            int mi = -1, mx = -1;
            char last;
            
            for (int i = 0; i < n; i++){
                if (vis[i]) continue;
                if (mi == -1 || s[mi] > s[i]) mi = i;
            }
            if (mi != -1){
                ans += s[mi];
                vis[mi] = true; ++cnt;
                last = s[mi];
            }
            
            while(mi != - 1){
                mi = -1;
                for (int i = 0; i < n; i++){
                    if (vis[i] || last >= s[i]) continue;
                    if (mi == -1 || s[mi] > s[i]) mi = i;
                }
                if (mi == -1) break;
                ans += s[mi];
                vis[mi] = true; ++cnt;
                last = s[mi];
            }
            
            for (int i = 0; i < n; i++){
                if (vis[i]) continue;
                if (mx == -1 || s[mx] < s[i]) mx = i;
            }
            if (mx != -1){
                ans += s[mx];
                vis[mx] = true; ++cnt;
                last = s[mx];
            }
            
            while(mx != -1){
                mx = -1;
                for (int i = 0; i < n; i++){
                    if (vis[i] || last <= s[i]) continue;
                    if (mx == -1 || s[mx] < s[i]) mx = i;
                }
                if (mx == -1) break;
                ans += s[mx];
                vis[mx] = true; ++cnt;
                last = s[mx];
            }
        }
        
        return ans;
    }
};

2. 每个元音包含偶数次的最长子字符串

给你一个字符串 s ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 ‘a’,’e’,’i’,’o’,’u’ ,在子字符串中都恰好出现了偶数次。

样例

示例 1:

输入:s = “eleetminicoworoep”
输出:13
解释:最长子字符串是 “leetminicowor” ,它包含 eio 各 2 个,以及 0 个 au

示例 2:

输入:s = “leetcodeisgreat”
输出:5
解释:最长子字符串是 “leetc” ,其中包含 2 个 e

示例 3:

输入:s = “bcbcbc”
输出:6
解释:这个示例中,字符串 “bcbcbc” 本身就是最长的,因为所有的元音 aeiou 都出现了 0 次。 

提示

  • 1 <= s.length <= 5 x 10^5
  • s 只包含小写英文字母。

代码

viv丑陋版

我不会qwqwqwqwqwq……

zz美丽版

每个元音字母有出现奇数和偶数两种情况,五个元音字母一共有$2^5=32$种情况。
统计每个位置五个元音字母的奇偶状态,相同状态之间是一个合法的字符串。
贪心的思想,对于每一个状态,尽量取最早出现的相同状态为界限,中间部分的字符串一定是满足要求的最长。
$begin[i]$记录第$i$种状态第一次出现的位置。

class Solution {
public:
    int c2i(char c) {
        if(c == 'a') return 0;
        if(c == 'e') return 1;
        if(c == 'i') return 2;
        if(c == 'o') return 3;
        if(c == 'u') return 4;
        return -1;
    }
    int findTheLongestSubstring(string s) {
        int begin[32], n = s.size(), ans = 0;

        int cnt[5]; memset(cnt, 0, sizeof(cnt));
        for(int i=0; i<32; i++) begin[i] = n;
        begin[0] = -1;

        for(int i=0; i<n; i++) {
            if(c2i(s[i]) != -1) cnt[c2i(s[i])]++;
            int s = 0;
            for(int k=0; k<5; k++) s += (1<<k) * (cnt[k] & 1);
            if(begin[s] == n) begin[s] = i;
            ans = max(ans, i - begin[s]);
        }
        return ans;
    }
};

3. 二叉树中的最长交错路径

给你一棵以 root 为根的二叉树,二叉树中的交错路径定义如下:

  • 选择二叉树中 任意 节点和一个方向(左或者右)。
  • 如果前进方向为右,那么移动到当前节点的的右子节点,否则移动到它的左子节点。
  • 改变前进方向:左变右或者右变左。
  • 重复第二步和第三步,直到你在树中无法继续移动。

交错路径的长度定义为:访问过的节点数目 – 1(单个节点的路径长度为 0 )。
请你返回给定树中最长 交错路径 的长度。

样例

示例 1:

输入:root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
输出:3
解释:蓝色节点为树中最长交错路径(右 -> 左 -> 右)。

示例 2:

输入:root = [1,1,1,null,1,null,null,1,1,null,1]
输出:4
解释:蓝色节点为树中最长交错路径(左 -> 右 -> 左 -> 右)。

示例 3:

输入:root = [1]
输出:0

提示

  • 每棵树最多有 50000 个节点。
  • 每个节点的值在 [1, 100] 之间。

代码

viv丑陋版

不删注释了,留个纪念。
一开始看到这道题立马想到了上周周赛dfs的题,我写到最后一团糟而zz却用dfs套dfs很简洁的写出来了。于是我当机立断写下了注释里的内容。先写了一个dfs遍历每个节点,遍历到每个节点时再dfs求从当前节点出发的最长交错路径长度。然后光荣的TLE了,发现有$5e4$个节点。
仔细想想这应该是一道树形DP。dfs时,如果下一步走和上一步相交错的方向,路径长度+1;否则,直接从1开始重新计数。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
int ans = 0;
// void check(TreeNode* root, int len, bool left) {
//     if(root == NULL) return;
//     ans = max(ans, len);
//     if(root->left && !left) check(root->left, len+1, !left);
//     if(root->right && left) check(root->right, len+1, !left);
// }
// void dfs(TreeNode* root) {
//     if(root == NULL) return;
//     check(root, 0, true);
//     check(root, 0, false);
//     if(root->left) dfs(root->left);
//     if(root->right) dfs(root->right);
// }
void dfs(TreeNode* root, int dp, bool left) {
    if(root == NULL) return;
    ans = max(ans, dp);
    if(left) {
        if(root->right) dfs(root->right, dp+1, !left);
        if(root->left) dfs(root->left, 1, left);
    }
    else {
        if(root->left) dfs(root->left, dp+1, !left);
        if(root->right) dfs(root->right, 1, left);
    }
}
class Solution {
public:
    int longestZigZag(TreeNode* root) {
        ans = 0; 
        dfs(root, 0, true);
        dfs(root, 0, false);
        return ans;
    }
};

zz美丽版

思路一样,不同的dfs写法而已。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    int ans = 0;
    
    pair<int, int> dfs(TreeNode *rt){
        if (rt == NULL) return make_pair(0, 0);
        
        int l = 1, r = 1;
        l = 1 + dfs(rt->left).second;
        r = 1 + dfs(rt->right).first;
        
        ans = max(ans, max(l, r));
        
        return make_pair(l, r);
        
    }
    int longestZigZag(TreeNode* root) {
        dfs(root);
        return ans - 1;
    }
};

4. 二叉搜索子树的最大键值和

给你一棵以 root 为根的 二叉树 ,请你返回 任意 二叉搜索子树的最大键值和。
二叉搜索树的定义如下:

  • 任意节点的左子树中的键值都 小于 此节点的键值。
  • 任意节点的右子树中的键值都 大于 此节点的键值。
  • 任意节点的左子树和右子树都是二叉搜索树。

样例

示例 1:

输入:root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
输出:20
解释:键值为 3 的子树是和最大的二叉搜索树。

示例 2:

输入:root = [4,3,null,1,2]
输出:2
解释:键值为 2 的单节点子树是和最大的二叉搜索树。

示例 3:

输入:root = [-4,-2,-5]
输出:0
解释:所有节点键值都为负数,和最大的二叉搜索树为空。

示例 4:

输入:root = [2,1,3]
输出:6

示例 5:

输入:root = [5,4,8,3,null,6,3]
输出:7

提示

  • 每棵树最多有 40000 个节点。
  • 每个节点的键值在 [-4 10^4 , 4 10^4] 之间。

代码

viv丑陋版

viv到最后也没有写出来,WA在一个莫名其妙的点。

zz美丽版

PIIBI代表一个(子树内节点最小值,子树内节点最大值,是否是合法的二叉搜索树,子树和)的四元组。
dfs过程中,通过判断左右子树节点的最大值、最小值和当前节点值的关系来判断搜索二叉树的合法性,并不断比较并记录子树和的最大值。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
const int INF = 4e4 + 50;
#define MP(a, b, c, d) make_pair(make_pair(a, b), make_pair(c, d))
#define PIIBI pair<pair<int, int>, pair<bool, int>>
class Solution {
public:
    int ans = 0;
    
    pair<pair<int, int>, pair<bool, int>> dfs(TreeNode * root){
        if (root == NULL) return MP(INF, -INF, true, 0);
        
        PIIBI r = dfs(root->right);
        PIIBI l = dfs(root->left);
        
        if ((l.second.first && r.second.first) == false) return MP(0, 0, false, 0);
        
        if (l.first.second < root->val && root->val < r.first.first){
            int sum = root->val + l.second.second + r.second.second;
            int mx = max(root->val, r.first.second);
            int mi = min(root->val, l.first.first);
            ans = max(ans, sum);
            return MP(mi, mx, true, sum);
        }else return MP(0, 0, false, 0);
    }
    
    int maxSumBST(TreeNode* root) {
        dfs(root);
        return ans;
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇