On the shoulders of giants.

biweekly-contest-21

上升下降字符串

给你一个字符串 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 只包含小写英文字母。
题解

直接模拟这个过程。

时间复杂度:\(O(kn)\)

class Solution {
public:
    string sortString(string s) {
        int n = s.length(), count = 0;
        vector<bool> vis(n, 0);
        string result = "";
        while(count != n) 
        {
            char lim = 'a' - 1;
            while(true) {
                int p = -1;
                char tmp = 'z' + 1;
                for(int i = 0; i < n; i++) {
                    if(vis[i]) continue;
                    if(lim < s[i] && s[i] < tmp) 
                        tmp = s[p = i];
                }
                if(p == -1) break;
                vis[p] = 1;
                result += (lim = tmp);
                count++;
            }
            lim = 'z' + 1;
            while(true) {
                int p = -1;
                char tmp = 'a' - 1;
                for(int i = 0; i < n; i++) {
                    if(vis[i]) continue;
                    if(s[i] < lim && tmp < s[i]) 
                        tmp = s[p = i];
                }
                if(p == -1) break;
                vis[p] = 1;
                result += (lim = tmp);
                count++;
            }            
        }
        return result;
    }
};

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

我们记录每个字符奇偶次状态的最小位置,我们有:

如果字符串 \(s_{0,n}\) 出现奇偶关系为 \((0,1,0,1,0)\) ,

0 代表偶次,1 代表奇次,那我们应该找到之前出现过的这种状态,两者相减就可以保证都出现偶数次。

其次要保证状态的位置最小,相减后可能得到最大长度。

时间复杂度:\(O(n)\)

class Solution {
public:
    int findTheLongestSubstring(string s) {
        int n = s.length();
        vector<int> state(1 << 5, n);
        map<char, int> h;
        int result = 0, now = 0;
        state[0] = -1;
        h.insert(make_pair('a', 0));
        h.insert(make_pair('e', 1));
        h.insert(make_pair('i', 2));
        h.insert(make_pair('o', 3));
        h.insert(make_pair('u', 4));
        for(int i = 0; i < n; i++) {
            if(h.find(s[i]) != h.end())
                now ^= (1 << h[s[i]]);
            if(state[now] == n) state[now] = i;
            result = max(result, i - state[now]);
        }
        return result;
    }
};

二叉树中的最长交错路径

给你一棵以 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] 之间。
题解

遍历这棵树,记录每次是往左还是往右走。

可以拐就拐,还可以重新走一条,最后更新答案。

时间复杂度:\(O(n)\)

/**
 * 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 result = 0;
    void search(TreeNode* root, int p, int dep) {
        if(root == NULL) return;
        result = max(result, dep);
        if(p == -1) {
            search(root->left, 0, 1);
            search(root->right, 1, 1);
        } else {
            search(root->left, 0, (p == 1 ? dep + 1 : 1));
            search(root->right, 1, (p == 0 ? dep + 1 : 1));
        }
    }
    int longestZigZag(TreeNode* root) {
        search(root, -1, 0);
        return result;
    }
};

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

给你一棵以 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] 之间。
题解

如果左子树是有序的,右子树也是有序的,然后左子树根节点值小于当前节点值,右子树根节点值大于当前节点值,那么这颗树就是有序的。

我们可以从小到上判断一棵树否非为有序的,然后更新答案即可。

时间复杂度:\(O(n)\)

/**
 * 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 result = 0;
    vector<int> search(TreeNode* root) {
        if(root == NULL) return vector<int> {1, 0};
        vector<int> flag1 = search(root->left);
        vector<int> flag2 = search(root->right);
        int sum = flag1[1] + flag2[1] + root->val;
        if(flag1[0] && flag2[0]) {
            if(root->left != NULL) {
                if(root->val <= root->left->val) return vector<int> {0, sum};
            }   
            if(root->right != NULL) {
                if(root->right->val <= root->val) return vector<int> {0, sum};
            }
            result = max(result, sum);
            return vector<int> {1, sum};
        } else return vector<int> {0, sum};
    }
    int maxSumBST(TreeNode* root) {
        search(root);
        return result;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注