周赛 - 🏆 第 293 场力扣周赛 - 《学习笔记》

5234. 移除字母异位词后的结果数组
6064. 不含特殊楼层的最大连续楼层数
6065. 按位与结果大于零的最长组合
6066. 统计区间中的整数数目

泪目，刷新最好排名，第一次拿到Leetcode的奖品

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

给你一个下标从 0 开始的字符串 words ，其中 words[i] 由小写英文字符组成。
在一步操作中，需要选出任一下标 i ，从 words 中删除 words[i] 。其中下标 i 需要同时满足下述两个条件：

0 < i < words.length
words[i - 1] 和 words[i] 是 字母异位词 。

只要可以选出满足条件的下标，就一直执行这个操作。
在执行所有操作后，返回 words 。可以证明，按任意顺序为每步操作选择下标都会得到相同的结果。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。例如，”dacb” 是 “abdc” 的一个字母异位词。

示例 1：
输入：words = [“abba”,”baba”,”bbaa”,”cd”,”cd”] 输出：[“abba”,”cd”] 解释： 获取结果数组的方法之一是执行下述步骤： - 由于 words[2] = “bbaa” 和 words[1] = “baba” 是字母异位词，选择下标 2 并删除 words[2] 。现在 words = [“abba”,”baba”,”cd”,”cd”] 。 - 由于 words[1] = “baba” 和 words[0] = “abba” 是字母异位词，选择下标 1 并删除 words[1] 。现在 words = [“abba”,”cd”,”cd”] 。 - 由于 words[2] = “cd” 和 words[1] = “cd” 是字母异位词，选择下标 2 并删除 words[2] 。现在 words = [“abba”,”cd”] 。无法再执行任何操作，所以 [“abba”,”cd”] 是最终答案。
示例 2：
输入：words = [“a”,”b”,”c”,”d”,”e”] 输出：[“a”,”b”,”c”,”d”,”e”] 解释： words 中不存在互为字母异位词的两个相邻字符串，所以无需执行任何操作。

提示：

1 <= words.length <= 100
1 <= words[i].length <= 10
words[i] 由小写英文字母组成

思路：
模拟

class Solution {
    public List<String> removeAnagrams(String[] words) {
        List<String> res = new ArrayList<>();
        for (String s : words) {
            if (!res.isEmpty()) {
                String t = res.get(res.size() - 1);
                if (!check(s, t)) {
                    res.add(s);
                }
            } else {
                res.add(s);
            }
        }
        return res;
    }
    boolean check(String s, String t) {
        if (s.length() != t.length())
            return false;
        char[] c1 = s.toCharArray();
        char[] c2 = t.toCharArray();
        Arrays.sort(c1);
        Arrays.sort(c2);
        for (int i = 0; i < c1.length; i++)
            if (c1[i] != c2[i])
                return false;
        return true;
    }
}

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

Alice 管理着一家公司，并租用大楼的部分楼层作为办公空间。Alice 决定将一些楼层作为 特殊楼层 ，仅用于放松。
给你两个整数 bottom 和 top ，表示 Alice 租用了从 bottom 到 top（含 bottom 和 top 在内）的所有楼层。另给你一个整数数组 special ，其中 special[i] 表示 Alice 指定用于放松的特殊楼层。
返回不含特殊楼层的最大连续楼层数。

示例 1：
输入：bottom = 2, top = 9, special = [4,6] 输出：3 解释：下面列出的是不含特殊楼层的连续楼层范围： - (2, 3) ，楼层数为 2 。 - (5, 5) ，楼层数为 1 。 - (7, 9) ，楼层数为 3 。因此，返回最大连续楼层数 3 。
示例 2：
输入：bottom = 6, top = 8, special = [7,6,8] 输出：0 解释：每层楼都被规划为特殊楼层，所以返回 0 。

提示

1 <= special.length <= 105
1 <= bottom <= special[i] <= top <= 109
special 中的所有值 互不相同

思路：
模拟

class Solution {
    public int maxConsecutive(int bottom, int top, int[] special) {
        Arrays.sort(special);
        int pre = bottom - 1;
        int max = 0;
        for (int x : special) {
            max = Math.max(max, x - pre - 1);
            pre = x;
        }
        max = Math.max(max, top - pre);
        return max;
    }
}

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

对数组 nums 执行 按位与 相当于对数组 nums 中的所有整数执行 按位与 。

例如，对 nums = [1, 5, 3] 来说，按位与等于 1 & 5 & 3 = 1 。
同样，对 nums = [7] 而言，按位与等于 7 。

给你一个正整数数组 candidates 。计算 candidates 中的数字每种组合下 按位与 的结果。 candidates 中的每个数字在每种组合中只能使用一次。
返回按位与结果大于 0 的最长组合的长度。

示例 1：
输入：candidates = [16,17,71,62,12,24,14] 输出：4 解释：组合 [16,17,62,24] 的按位与结果是 16 & 17 & 62 & 24 = 16 > 0 。组合长度是 4 。可以证明不存在按位与结果大于 0 且长度大于 4 的组合。注意，符合长度最大的组合可能不止一种。例如，组合 [62,12,24,14] 的按位与结果是 62 & 12 & 24 & 14 = 8 > 0 。
示例 2：
输入：candidates = [8,8] 输出：2 解释：最长组合是 [8,8] ，按位与结果 8 & 8 = 8 > 0 。组合长度是 2 ，所以返回 2 。

提示：

1 <= candidates.length <= 105
1 <= candidates[i] <= 107

思路：
按位运算

class Solution {
    public int largestCombination(int[] c) {
        int max = 0;
        for (int i = 0; i < 24; i++) {
            int cnt = 0;
            for (int x : c)
                cnt += x >> i & 1;
            max = Math.max(max, cnt);
        }
        return max;
    }
}

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

给你区间的空集，请你设计并实现满足要求的数据结构：

新增：添加一个区间到这个区间集合中。
统计：计算出现在 至少一个 区间中的整数个数。

实现 CountIntervals 类：

CountIntervals() 使用区间的空集初始化对象
void add(int left, int right) 添加区间 [left, right] 到区间集合之中。
int count() 返回出现在 至少一个 区间中的整数个数。

注意：区间 [left, right] 表示满足 left <= x <= right 的所有整数 x 。

示例 1：

提示：

1 <= left <= right <= 109
最多调用 add 和 count 方法总计 105 次
调用 count 方法至少一次

思路：
区间问题
方法1：有序集和(平衡树)
分析时间复杂度：考虑每一个区间，只会被添加一次，删除一次，所以总时间复杂度为O(nlogn)
方法2：动态开点线段树

class CountIntervals {
    class Interval implements Comparable<Interval> {
        int l, r;
        Interval(int l, int r) {
            this.l = l;
            this.r = r;
        }
        public int compareTo(Interval other) {
            return this.r - other.r;
        }
    }
    TreeSet<Interval> set = new TreeSet<>();
    int cnt = 0;
    public CountIntervals() {
    }
    public void add(int left, int right) {
        var iterator = set.tailSet(new Interval(left, left)).iterator();
        while (iterator.hasNext()) {
            var t = iterator.next();
            if (t.l > right) break;
            left = Math.min(left, t.l);
            right = Math.max(right, t.r);
            cnt -= t.r - t.l + 1;
            iterator.remove();
        }
        set.add(new Interval(left, right));
        cnt += right - left + 1;
    }
    public int count() {
        return cnt;
    }
}
/**
 * Your CountIntervals object will be instantiated and called as such:
 * CountIntervals obj = new CountIntervals();
 * obj.add(left,right);
 * int param_2 = obj.count();
 */

class CountIntervals {
    class Interval {
        Interval left, right;
        int l, r;
        int sum;
        Interval(int l, int r) {
            this.l = l;
            this.r = r;
        }
        void add(int ll, int rr) {
            if (r - l + 1 == sum) return;
            if (ll <= l && rr >= r) {
                sum = r - l + 1;
            } else {
                int mid = l + r >> 1;
                if (left == null) left = new Interval(l, mid);
                if (right == null) right = new Interval(mid + 1, r);
                if (ll <= mid) left.add(ll, rr);
                if (rr > mid) right.add(ll, rr);
                sum = left.sum + right.sum;
            }
        }
    }
    Interval root = new Interval(1, (int)(1e9));
    public CountIntervals() {
    }
    public void add(int left, int right) {
        root.add(left, right);
    }
    public int count() {
        return root.sum;
    }
}
/**
 * Your CountIntervals object will be instantiated and called as such:
 * CountIntervals obj = new CountIntervals();
 * obj.add(left,right);
 * int param_2 = obj.count();
 */