讨论/题目交流/🐱 第 21 场夜喵双周赛/
🐱 第 21 场夜喵双周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

4 分 - 上升下降字符串
4 分 - 每个元音包含偶数次的最长子字符串
5 分 - 二叉树中的最长交错路径
6 分 - 二叉搜索子树的最大键值和

展开讨论
力扣 (LeetCode)发起于 2020-03-07
共 21 个讨论

@and1p1
@kardosrambo
@phoenix-13
@Faber99

四个作弊的,比赛提交的代码一模一样,建议永封。

10

还好果断放弃第二题 保住了15分。。
教会了我们应该学会放手?

5

关于第二题的 O(N)O(N) 解法:

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        keys = ['a', 'e', 'i', 'o', 'u']
        count = { k: 0 for k in keys }

        state = {}
        for i in range(32):
            k = ''.join(str(i >> j & 1) for j in range(5))
            state[k] = -1

        ret = 0
        for i in range(len(s)):
            if s[i] in count: count[s[i]] += 1
            key = ''.join([str(count[k] % 2) for k in keys])
            if key == '00000': ret = max(ret, i + 1)
            elif state[key] < 0: state[key] = i
            else: ret = max(ret, i - state[key])
        return ret

遍历字符串 SS 中的每一个字符,同时统计已遍历部分各个元音字母的数目,那么 a, e, i, o, u 五个字母的奇偶性,可以组成 32 个状态,当五个字符全为偶数时,证明已遍历的字符数就是最大长度;当五个字符中存在奇数个时,只需要根据状态键,找到第一次变成该状态时的索引即可,然后记录最大长度,就能得到最终解。

类似题目:第 20 场双周赛第三题:1358. 包含所有三种字符的子字符串数目

以后遇到这种 substring 长度最大化的题目,都按照这种套路解就行了。

2

第二题跟第四题出反了吧……

2

晚上有些困....
就做了1, 2两题...
第三题会做,没时间了...悲催...
做不快的感觉,还是因为太菜了,练习不够多~
第一题:模拟,排序,走到底,再往回走...
第二题:正反方向深搜.
第三题:逐步下传当前的深度和来自父节点的左/右子树标记. 左左/右右->len = 1, 左右/右左-> len+1.
第四题:看都还没去看.....
小白还是要多练-,-!

1

第二题,我的代码哪里错呢? 第一个用例过不了eleetminicoworoep 输出14,预期13;

class Solution {
public:
    int findTheLongestSubstring(string s) {
        int len = s.size();
        vector<int>cntA(len, 0);
        vector<int>cntE(len, 0);
        vector<int>cntI(len, 0);
        vector<int>cntO(len, 0);
        vector<int>cntU(len, 0);
        
        cntA[0] =  (s[0] == 'a');
        cntE[0] =  (s[0] == 'e');
        cntI[0] =  (s[0] == 'i');
        cntO[0] =  (s[0] == 'o');
        cntU[0] =  (s[0] == 'u');
        
        for(int i = 1; i < len; i++)
        {
            cntA[i] = cntA[i-1] + (s[i] == 'a');
            cntE[i] = cntE[i-1] + (s[i] == 'e');
            cntI[i] = cntI[i-1] + (s[i] == 'i');
            cntO[i] = cntO[i-1] + (s[i] == 'o');
            cntU[i] = cntU[i-1] + (s[i] == 'u');
        }
        int res = 0;
        for(int i = len-1; i >= 0; i--)
        {
            for(int j = 0; j < i; j++)
            {
                if(i - j + 1 < res)
                {
                    break;
                }
                if((cntA[i] - cntA[j]) % 2 == 0 && 
                   (cntE[i] - cntE[j]) % 2 == 0 && 
                   (cntI[i] - cntI[j]) % 2 == 0 && 
                   (cntO[i] - cntO[j]) % 2 == 0 && 
                   (cntU[i] - cntU[j]) % 2 == 0   )
                {

                    res = i - j + 1;
                }
            }
        }
        return res;
    }
};

==========2020-3-8 0:22 更新

class Solution {
public:
    int findTheLongestSubstring(string s) {
        int len = s.size();
        vector<int>cntA(len+1, 0);
        vector<int>cntE(len+1, 0);
        vector<int>cntI(len+1, 0);
        vector<int>cntO(len+1, 0);
        vector<int>cntU(len+1, 0);
                
        for(int i = 1; i <= len; i++)
        {
            cntA[i] = cntA[i-1] + (s[i-1] == 'a');
            cntE[i] = cntE[i-1] + (s[i-1] == 'e');
            cntI[i] = cntI[i-1] + (s[i-1] == 'i');
            cntO[i] = cntO[i-1] + (s[i-1] == 'o');
            cntU[i] = cntU[i-1] + (s[i-1] == 'u');
        }
        int res = 0;
        for(int i = len; i > 0; i--)
        {
            for(int j = 0; j < i; j++)
            {
                if(i - j  < res)
                {
                    break;
                }
                if((cntA[i] - cntA[j]) % 2 == 0 && 
                   (cntE[i] - cntE[j]) % 2 == 0 && 
                   (cntI[i] - cntI[j]) % 2 == 0 && 
                   (cntO[i] - cntO[j]) % 2 == 0 && 
                   (cntU[i] - cntU[j]) % 2 == 0   )
                {
                    // cout<<"----------"<<endl;
                    // cout<<i<<" "<<j<<endl;
                    // cout<<cntA[i]<<" "<<cntA[j]<<endl;
                    // cout<<cntE[i]<<" "<<cntE[j]<<endl;
                    // cout<<cntI[i]<<" "<<cntI[j]<<endl;
                    // cout<<cntO[i]<<" "<<cntO[j]<<endl;
                    // cout<<cntU[i]<<" "<<cntU[j]<<endl;
                    res = i - j;
                    // cout<<res<<endl;
                }
            }
        }
        return res;
    }
};

过了
睡觉

1

第2题难道不是最难的吗

1

只写出了1,3题,第2题暴力超时,写到现在终于放弃... 话说这个比赛比赛多久啊?我怎么能看到排行榜的人的答案了?

1

明天再好好写写第二题,写了很久没时间看第四题了,最后还是错了,想法就是记录aeiou第一次的奇数位置,遍历整个数组,后面的奇数位置减去第一个奇数位置,偶数位置就记录全长,最后对比5个取最小值,再和答案取最大值。

1

恶心,做吐了

1