# Leetcode 第293场周赛题解

# Problem A - 移除字母异位词后的结果数组 (opens new window)

# 方法一:栈

  • 时间复杂度 O(SilogSi)\mathcal{O}(\sum|S_i|\log|S_i|)
  • 空间复杂度 O(Si)\mathcal{O}(\sum |S_i|)
参考代码(Python 3)
class Solution:
    def removeAnagrams(self, words: List[str]) -> List[str]:
        ans = []
        for word in words:
            if len(ans) == 0 or sorted(word) != sorted(ans[-1]):
                ans.append(word)
        return ans
1
2
3
4
5
6
7

# Problem B - 不含特殊楼层的最大连续楼层数 (opens new window)

# 方法一:排序

  • 时间复杂度 O(NlogN)\mathcal{O}(N\log N)
  • 空间复杂度 O(N)\mathcal{O}(N)
参考代码(Python 3)
class Solution:
    def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
        floors = [bottom - 1] + sorted(special) + [top + 1]
        return max(u - d - 1 for u, d in zip(floors[1:], floors[:-1]))
1
2
3
4

# Problem C - 按位与结果大于零的最长组合 (opens new window)

# 方法一:逐位考虑

  • 时间复杂度 O(NK)\mathcal{O}(NK)
  • 空间复杂度 O(N)\mathcal{O}(N),可以进一步优化到 O(1)\mathcal{O}(1)
参考代码(Python 3)
class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        return max(len([c for c in candidates if (c & (1 << i)) > 0]) for i in range(30))
1
2
3

# Problem D - 统计区间中的整数数目 (opens new window)

# 方法一:维护有序区间集合

  • 添加一个新区间的均摊时间复杂度为 O(logN)\mathcal{O}(\log N),查询时间复杂度为 O(1)\mathcal{O}(1)
  • 空间复杂度 O(N)\mathcal{O}(N)
参考代码(C++)
class CountIntervals {
    set<pair<int, int>> s;
    int cnt;
public:
    CountIntervals() {
        cnt = 0;
    }
    
    void add(int left, int right) {
        auto it = s.lower_bound(make_pair(left, left));
        if (it != s.begin())
            it--;
        
        vector<pair<int, int>> to_erase;
        for (; it != s.end(); ++it) {
            auto [l, r] = *it;
            if (l > right + 1) break;
            if (r < left - 1) continue;
            left = min(left, l);
            right = max(right, r);
            to_erase.push_back(*it);
        }
        
        for (auto &p : to_erase) {
            cnt -= p.second - p.first + 1;
            s.erase(p);
        }
        
        s.emplace(left, right);
        cnt += right - left + 1;
    }
    
    int count() {
        return cnt;
    }
};
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
26
27
28
29
30
31
32
33
34
35
36