复盘|第293场周赛
移除字母异位词后的结果数组
【栈模拟】根据相邻元素性质删除元素的题可以用栈来思考,从左往右遍历,每次和栈顶比较,如果不是字母异位词就入栈,遍历结束后,栈中所有相邻元素进步时字母异位词,栈即为答案。
不含特殊楼层的最大连续楼层数
【排序 + 枚举】可以把bottom - 1和top + 1视为两个特殊楼层,相当于special数组有len(special)个分割点,问哪段最长。
本题也可参照164. 最大间距,用桶排序或基数排序,达到时空复杂度O(n)。
按位与结果大于零的最长组合
【枚举二进制位】candidates[i] ≤ 10^7,2^23 < 10^7 < 2^24,所以每个数至多24个二进制位,对于每个二进制位而言,只要不与到0结果都大于零,所以,哪个二进制位上,这些数字里1的最多,1的数量就是答案。
统计区间中的整数数目
【珂朵莉树】有序集合 / 有序映射,用一颗平衡树维护若干个不相交的区间,每次add(left, right)时,删除被该区间覆盖到的区间(部分覆盖也算),然后将这些区间与[left, right]合并到一个新的大区间,插入平衡树中,代码中为方便找到第一个被[left, right]覆盖到的区间,可以用平衡树的key存区间右端点,value存区间左端点,要找到就是第一个key≥left的区间。
【动态开点线段树】线段树每个节点保存对应范围的做右端点l和r,及范围内add过的整数个数cnt,无需记录lazy tag。