Leetcode 第 293 场周赛

Posted on | Edited on | In ,
| 5.7k | 47 mins.

又是之前的周赛~

2273. Find Resultant Array After Removing Anagrams

Analysis

不知道为什么简单题的题目都好长啊...题意就是删除连续出现的字母异位词，只保留最开始的哪一个。但是要注意，如果是相隔的字母异位词，是不用删除的。

Code

这是当时提交通过的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<string> removeAnagrams(vector<string>& words) {
        int size = words.size();
        vector<string> ret;
        int i = 0;
        while(i < size) {
            string s1 = words[i];
            ret.push_back(words[i]);
            sort(s1.begin(), s1.end());
            int j = i + 1;
            while(j < size) {
                string s2 = words[j];
                sort(s2.begin(), s2.end());
                if(s2 != s1) break;
                j++;
            }
            i = j;
        }
        return ret;
    }
};

当时 WA 了一次的原因是，一次性把所有的字母异位词都删除了，没有注意只删除相邻的。判断是否是异位词，可以统计也可以排序，直接排序会比较方便，但统计的时间复杂度更低。既然使简单题，那就怎么方便怎么来好了。

2274. Maximum Consecutive Floors Without Special Floors

Analysis

这个题跟上一次周赛的题目很像，一样跟区间有关，所以这个题实际上就是在求分割后的最大区间。

Code

一开始使用的暴力模拟 + hash 的思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxConsecutive(int bottom, int top, vector<int>& special) {
        int size = special.size();
        unordered_set<int> ht;
        for(int &i: special) {
            ht.insert(i);
        }
        int maxstairs = 0;
        while(bottom <= top) {
            while(ht.count(bottom) && bottom < top) bottom++;
            if(bottom == top) break;
            int i = bottom + 1;
            while(i <= top && !ht.count(i)) i++;
            maxstairs = max(maxstairs, i - bottom);
            bottom = i;
        }
        return maxstairs;
    }
};

因为 special 中的值范围是 $[1, 10^9]$，所以超时了。
后面仔细一想，其实只需要把每个区间的间隔算出来，其中的最大值就是需要的结果了。但这种做法需要提前对 special 排序，并且要额外考虑最后的 top。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int maxConsecutive(int bottom, int top, vector<int>& special) {
        int size = special.size();
        vector<int> tmp = special;
        sort(tmp.begin(), tmp.end());
        if(tmp[size - 1] != top) {
            tmp.push_back(top + 1);
            size++;
        }
        int maxstairs = 0;
        for(int i = 0; i < size && bottom < top; i++) {
            int end = tmp[i];
            if(end == bottom) {
                bottom++;
                continue;
            }
            maxstairs = max(maxstairs, end - bottom);
            bottom = ++end;
        }
        return maxstairs;
    }
};

当时莫名其妙的不想对 special 这个数组做修改，就另外拷贝了一个，现在删掉拷贝：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxConsecutive(int bottom, int top, vector<int>& special) {
        int size = special.size();
        sort(special.begin(), special.end());
        if(special[size - 1] != top) {
            special.push_back(top + 1);
            size++;
        }
        int maxstairs = 0;
        for(int i = 0; i < size && bottom < top; i++) {
            int end = special[i];
            if(end == bottom) {
                bottom++;
                continue;
            }
            maxstairs = max(maxstairs, end - bottom);
            bottom = ++end;
        }
        return maxstairs;
    }
};

实际上，可以将 bottom - 1 和 top + 1 也放在数组内，一起进行排序，这样就不用单独考虑 top 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxConsecutive(int bottom, int top, vector<int>& special) {
        special.push_back(bottom - 1);
        special.push_back(top + 1);
        sort(special.begin(), special.end());
        int n = special.size();
        int maxstairs = 0;
        for(int i = 0; i < n - 1; i++) {
            maxstairs = max(maxstairs, special[i + 1] - special[i] - 1);
        }
        return maxstairs;
    }
};

2275. Largest Combination With Bitwise AND Greater Than Zero

Analysis

题意是选取给定数组中的数，要求这些数按位与后的结果大于 0，返回最长组合的长度。
实际上，要想按位与的结果不为 0，那么只需要保证最后的结果某一位不为 0 即可。换句话说，最长组合的中的所有数字肯定在某个 bit 上都是 1，这样才能保证最后的结果不为 0。
按照这个思路，分别统计每一位上不为 0 的数字个数，个数最多的就是需要返回的结果。
可惜这个题，当时没做出来，可能是想太多了，或者还是对位运算的理解不够深刻。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int largestCombination(vector<int>& candidates) {
        int cnt[24] = {0};
        int n = candidates.size();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < 24; j++) {
                if((1 << j) & candidates[i]) cnt[j]++;
            }
        }
        int ret = 0;
        for(int i = 0; i < 24; i++) {w reerv
            ret = max(ret, cnt[i]);
        }
        return ret;
    }
};

2276. Count Integers in Intervals

Analysis

这个题还是跟区间相关的题目，不过比第二个题复杂了一些。
当时读题的时候，没搞懂count这个函数到底是什么意思，主要是没读懂Returns the number of integers that are present in at least one interval。
事后看了题解才发现，就是当前区间内数的个数。所以这个值可以单独用一个变量来进行记录，并在每次调用add函数的时候，更新这个值。
不过，思考这个题确实需要线段树的相关知识。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class CountIntervals {
    int cnt = 0;
    set<pair<int, int>> st;
public:
    CountIntervals() {

    }
    
    void add(int left, int right) {
        int l = left, r = right;
        auto it = st.lower_bound({left - 1, -2e9});
        while(it != st.end() && it->second <= right) {
            l = min(l, it->second);
            r = max(r, it->first);
            cnt -= it->first - it->second + 1;
            st.erase(it++);
        }
        cnt += r - l + 1;
        st.insert({r, l});
    }
    
    int count() {
        return cnt;
    }
};

姑且算是理解了这种做法了，得在做几个类似的题加深一下印象。

Summary

得再开一个学习计划了~

Buy me a coffee ? :)
0%