LeetCode 第 293 场周赛 题解

首先，一定要读对题，不然就寄了。只有相邻两个的单词是字母异位词，才删除。

我们可以通过排序两个单词，判断相等来判断字母异位词。

代码：

class Solution {
public:
    vector removeAnagrams(vector& w) {
        set st;
        vector ans;
        ans.push_back(w[0]);
        for(int i=1;i
            string tmp=w[i];
            sort(tmp.begin(),tmp.end());
            string s=w[i-1];
            sort(s.begin(),s.end());
            if(tmp==s) continue;
            else ans.push_back(w[i]);
        }
        return ans;
    }
};

首先我们肯定要找到一头一尾的位置，判断特殊楼层的和一头一尾的大小。

代码：

class Solution {
public:
    int maxConsecutive(int b, int t, vector& s) {
        int n=s.size();
        int ans=0;
        int pos1=0,pos2=0;
        sort(s.begin(),s.end());
        for(int i=0;i
            if(b>=s[i]) pos1=i;
            if(t>=s[i]) pos2=i;
        }
        if(pos1==0) ans=max(ans,s[0]-b);
        if(pos2==n-1) ans=max(t-s[n-1],ans);
        // cout<
            ans=max(ans,s[i]-s[i-1]-1);
        }
        return ans;
    }
};

题目要求的是最长的一个组合相与大于0，换句话就是说，最长的一个组合，在这个组合里，至少有一位二进制全是1。所以我们枚举每一位二进制，取一个最大值。

代码：

class Solution {
public:
    int largestCombination(vector& c) {
        int ans=0;
        int n=c.size();
        for(int i=0;i<30;i++){
            int cnt=0;
            int num=(1<
                if(c[j]&num) cnt++;
            }
            ans=max(ans,cnt);
        }
        return ans;
    }
};

这很像一个树状数组或者权值线段树的题目，但是看数据量，这开不下数组，所以树状数组和权值线段树不行。

这里就需要用线段树动态开点。

但其实这就是一个区间合并的问题。(赛时我以为会超时，根本就往下写，所以研究线段树去了)

思路：将所有不相交的区间放到一个set里面，按右端点排序，当要加入一个新的区间时 [ l , r ] [l,r] [l,r]，二分找到第一个右端点大于等于 l-1的区间,然后不断往后合并，直到区间的左端点大于 r+1 。

代码：

class CountIntervals {
    set > st; //按右端点排序，pair默认第一关键字排序，所以第一个关键字存右端点，第二个关键字存右端点
    int ans=0;

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()){
            if(it->second>right+1) break;//后面没有和给定区间相交的区间了，就结束
            L=min(it->second,L);//合并
            R=max(it->first,R);
            ans-=it->first-it->second+1;//把当前这个区间删掉
            st.erase(it++);
        }
        ans+=R-L+1;
        st.insert({R,L});
    }
    int count() {
        return ans;
    }
};