Leetcode 第 293 场周赛 题解

Leetcode 第 293 场周赛 题解

1. 移除字母异位词后的结果数组

手速题，手速要快~

class Solution {
public:
    vector<string> removeAnagrams(vector<string>& words) {
        auto is_equal = [](auto x, auto y){
            sort(x.begin(), x.end());
            sort(y.begin(), y.end());
            return x == y;
        };

        words.erase(unique(words.begin(), words.end(), is_equal), words.end());
        return words;
    }
};

2. 不含特殊楼层的最大连续楼层数

手速题，相邻特殊楼层间连续层数为: $special[i + 1] - special[i] - 1$, $bottom$ 和 $top$ 特判即可。

class Solution {
public:
    int maxConsecutive(int bottom, int top, vector<int>& special) {
        sort(special.begin(), special.end());
        
        int ans = 0;
        int n = special.size();

        ans = max(ans, special[0] - bottom);
        for (int i = 1; i < n; ++i) {
            ans = max(ans, special[i] - special[i - 1] - 1);
        }
        ans = max(ans, top - special.back());
        return ans;
    }
};

3. 按位与结果大于零的最长组合

按位与大于等于 0，意味着有一位不为 0。统计每一位的最长组合，选最长的一位即可。

class Solution {
public:
    int largestCombination(vector<int>& candidates) {
        int ans = 0;
        for (int i = 0; i < 30; ++i) {
            int cnt = 0;
            for (int x: candidates) {
                if ((x >> i) & 1) ++cnt;
            }
            ans = max(ans, cnt);
        }
        return ans;
    }
};

4. 统计区间中的整数数目

比赛的时候想到合并，结果写歪了，原因是想的太复杂导致写的有偏差，实际题目很简单。思路是：每当遇到一个区间，合并所有相交的区间。通过 map 加速查找相交区间。时间复杂度 $O(nlogn)$。

需要注意的点是，可以通过合并 相交 或 相邻 的区间，来优化速度。

class CountIntervals {
    // [right, left]
    map<int, int> ranges;

    // answer
    int counts = 0;
public:
    CountIntervals() {

    }
    
    void add(int left, int right) {
        int l = left, r = right;

        for (auto it = ranges.lower_bound(left - 1); it != ranges.end(); ++it) {
            if (it->second > right + 1) break;

            l = min(l, it->second);
            r = max(r, it->first);
            counts -= (it->first - it->second + 1);
        }
        counts += r - l + 1;
        ranges[r] = l;
    }
    
    int count() {
        return counts;
    }
};

还有一种做法是用动态开点线段树来维护 $[1, 10^9]$ 中元素的个数，相当于区间修改和区间查询问题，时间复杂度同样是 $O(nlogn)$。