本次周赛不负众望的菜，写出三题（应该能上分），第四题在最后十几分钟想到一点思路了，但是对于合并区间还没有很明确的想法，码了一会感觉有点麻烦就没继续写了没吃早饭，当时肚子好饿。

战局详情：

排名用户名得分完成时间题目1（3）题目2（4）题目3（5）题目4（7）
1930/7356Juruoer120:54:040:14:170:20:470:54:04

题目及解答

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

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

给你一个下标从 0 开始的字符串 words ，其中 words[i] 由小写英文字符组成。

在一步操作中，需要选出任一下标 i ，从 words 中 删除 words[i] 。其中下标 i 需要同时满足下述两个条件：

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

只要可以选出满足条件的下标，就一直执行这个操作。

在执行所有操作后，返回 words 。可以证明，按任意顺序为每步操作选择下标都会得到相同的结果。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。例如，"dacb" 是 "abdc" 的一个字母异位词。

提示：

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

示例一：
输入：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”] 是最终答案。

示例二：
输入：words = [“a”,“b”,“c”,“d”,“e”]
输出：[“a”,“b”,“c”,“d”,“e”]
解释：
words 中不存在互为字母异位词的两个相邻字符串，所以无需执行任何操作。

解决方案：

既然已经证明：按任意顺序为每步操作选择下标都会得到相同的结果，那么只需要自左向右遍历一遍数组，对于一个新的元素，比较其和结果集中的当前最后一个元素是否是字母异位词，若是，则跳过该元素，否则加入结果集。

如何判断两字符串是否为字母异位词？

  • 方法一：统计字符串的每个字符个数，若两字符串每个字符的个数都相等，则为字母异位词，即我下面最终代码使用的方法
  • 方法二：将每个字符串的字符按字母序排序，形成一个新的字符串数组，新的字符串数组中相同的两个字符串，其原字符串即为字母异位词：
    1
    2
    3
    4
    vector<string> _words = words;
    for(int i = 0; i < _words.size(); ++i)
        sort(_words[i].begin(), _words[i].end());
    // 此时若 _words[i] == _words[j], 则 words[i] 和 words[j] 互为字母异位词

最终代码为：

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
class Solution
{
public:
    vector<string> removeAnagrams(vector<string> &words)
    {
        vector<string> rst; // 结果集
        vector<vector<int>> cnts(words.size(), vector<int>(26, 0));
        int i, j;
        for (i = 0; i < words.size(); ++i) // 统计字符串的每个字符个数
        {
            for (j = 0; j < words[i].length(); ++j)
                ++cnts[i][words[i][j] - 'a'];
        }
        rst.emplace_back(words[0]);
        j = 0;
        for (int i = 1; i < words.size(); ++i)
        { // i 为当前遍历到的元素在words中的下标，j为结果集的当前最后一个元素在words中的下标
            if(cnts[i] == cnts[j]) // 两字符串的每个字符个数相等，为字母异位词，跳过
                continue;
            rst.emplace_back(words[i]); // 否则加入结果集
            j = i; // 更新结果集的当前最后一个元素在words中的下标
        }
        return rst;
    }
};
不含特殊楼层的最大连续楼层数

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

Alice 管理着一家公司，并租用大楼的部分楼层作为办公空间。Alice 决定将一些楼层作为 特殊楼层 ，仅用于放松。

给你两个整数 bottom 和 top ，表示 Alice 租用了从 bottom 到 top（含 bottom 和 top 在内）的所有楼层。另给你一个整数数组 special ，其中 special[i] 表示 Alice 指定用于放松的特殊楼层。

返回不含特殊楼层的 最大 连续楼层数。

提示：

  1. 1 <= special.length <= 1e5
  2. 1 <= bottom <= special[i] <= top <= 1e9
  3. special[i] 中的所有值 互不相同

示例一：
输入：bottom = 2, top = 9, special = [4,6]
输出：3
解释：下面列出的是不含特殊楼层的连续楼层范围：

  • (2, 3) ，楼层数为 2 。
  • (5, 5) ，楼层数为 1 。
  • (7, 9) ，楼层数为 3 。

因此，返回最大连续楼层数 3 。

示例二：
输入：bottom = 6, top = 8, special = [7,6,8]
输出：0
解释：每层楼都被规划为特殊楼层，所以返回 0 。

解决方案：

先对 special 排序，然后求出 special 中相邻两个元素的差值最大值即可。

对 bottom 和 top 进行特殊处理，以计算出 第一个连续不含特殊楼层和最后一个连续不含特殊楼层楼的层数：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution
{
public:
    int maxConsecutive(int bottom, int top, vector<int> &special)
    {
        int n = special.size();
        sort(special.begin(), special.end());
        int rst = max(special[0] - bottom, top - special[n - 1]); // 第一个连续不含特殊楼层和最后一个连续不含特殊楼层楼层数的最大值
        for (int i = 1; i < n; ++i) // 计算其他连续不含特殊楼层层数，求出最大值
            rst = max(rst, special[i] - special[i - 1] - 1); // 两特殊楼层之间的楼层数
        return rst;
    }
};

或者假设存在 bottom - 1 层和 top + 1 层，并且都是特殊楼层，则无需对 bottom 和 top 特殊处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution
{
public:
    int maxConsecutive(int bottom, int top, vector<int> &special)
    {
        special.emplace_back(bottom - 1); // 假设bottom - 1 层和 top + 1 层为特殊楼层
        special.emplace_back(top + 1);
        int n = special.size();
        sort(special.begin(), special.end());
        int rst = 0;
        for (int i = 1; i < n; ++i)
            rst = max(rst, special[i] - special[i - 1] - 1);
        return rst;
    }
};
按位与结果大于零的最长组合

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

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

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

给你一个正整数数组 candidates 。计算 candidates 中的数字每种组合下 按位与 的结果。 candidates 中的每个数字在每种组合中只能使用 一次 。

返回按位与结果大于 0 的 最长 组合的长度。

提示：

  1. 1 <= candidates.length <= 1e5
  2. 1 <= candidates[i] <= 1e7

示例一：
输入：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 。

示例二：
输入：candidates = [8,8]
输出：2
解释：最长组合是 [8,8] ，按位与结果 8 & 8 = 8 > 0 。
组合长度是 2 ，所以返回 2 。

解决方案：

由按位与的特性，可以知道，若 数集{x} 所有数按位与的结果大于 0 ，则至少存在一个下标 i ，该 数集{x} 的所有数字的二进制在此下标处均为 1 。则只需要找出数组 candidates 中所有数的二进制为 1 的位，并找出含 1 的数字最多的位（表达能力不太好，写的有点绕，看下面表格即可明白）。

例如对示例一所有数有：

十进制二进制（此处仅展示后8位）
160001 0000
170001 0001
710100 0111
620011 1110
120000 1100
240001 1000
140000 1110
总计各位为1的数字个数0114 4432

可知 1 的个数最多的位（自右向左，自0开始）有第2位、第3位、第4位，均含有4个此位为1的数字，分别为：

  • 第2为为1的数：71、62、12、14
  • 第3为为1的数：62、12、24、14
  • 第4为为1的数：16、17、62、24

故只需要定义一个数组 cnts ，cnts[i] 表示 candidates 中二进制第 i 位为 1 的数字个数，则 cnts 的最大值即为所求答案。

定义一个整数数组 t ，且 t[i] 的二进制仅在第 i 位为 1 ，其他位为 0，随后遍历数组 candidates，若 candidates[i] & t[j] == 1 ，则说明 candidates[i] 的二进制在第 j 位为 1，需要 ++cnts[j]; 。

可以写出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution
{
public:
    int largestCombination(vector<int> &candidates)
    {
        vector<int> cnts(24); // 1 <= candidates[i] <= 1e7，此范围内所有数的二进制只可能后 24 个位为 1。
        vector<int> t(24); // 上述整数数组 t
        int i, j, n = candidates.size();
        t[0] = 1;
        for(i = 1; i < 24; ++i)
            t[i] = t[i - 1] << 1;

        for (i = 0; i < n; ++i)
        {
            for (j = 0; j < 24; ++j)
            {
                if(candidates[i] & t[j])
                    ++cnts[j];
            }
        }
        return *max_element(cnts.begin(), cnts.end());
    }
};
统计区间中的整数数目

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

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

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

实现 CountIntervals 类：

  • CountIntervals() 使用区间的空集初始化对象
  • void add(int left, int right) 添加区间 [left, right] 到区间集合之中。
  • int count() 返回出现在 至少一个 区间中的整数个数。
    注意：区间 [left, right] 表示满足 left <= x <= right 的所有整数 x 。

提示：

  1. 1 <= left <= right <= 1e9
  2. 最多调用 add 和 count 方法 总计 1e5 次
  3. 调用 count 方法至少一次

示例一：
输入
[“CountIntervals”, “add”, “add”, “count”, “add”, “count”]
[[], [2, 3], [7, 10], [], [5, 8], []]
输出
[null, null, null, 6, null, 8]
解释：

1
2
3
4
5
6
7
8
9
10
11
12
CountIntervals countIntervals = new CountIntervals(); // 用一个区间空集初始化对象
countIntervals.add(2, 3);  // 将 [2, 3] 添加到区间集合中
countIntervals.add(7, 10); // 将 [7, 10] 添加到区间集合中
countIntervals.count();    // 返回 6
                           // 整数 2 和 3 出现在区间 [2, 3] 中
                           // 整数 7、8、9、10 出现在区间 [7, 10] 中
countIntervals.add(5, 8);  // 将 [5, 8] 添加到区间集合中
countIntervals.count();    // 返回 8
                           // 整数 2 和 3 出现在区间 [2, 3] 中
                           // 整数 5 和 6 出现在区间 [5, 8] 中
                           // 整数 7 和 8 出现在区间 [5, 8] 和区间 [7, 10] 中
                           // 整数 9 和 10 出现在区间 [7, 10] 中

解决方案：

使用 pair<int, int> 来表示一个区间，first 为区间的右边界，second 为左边界。

使用一个集合 set 存储所有合并后的区间集。

使用 cnt 表示区间集 s 包含的所有整数个数。

对于一个新的区间 [left, right] ，作如下操作：

  • 在 s 中找到所有右边界大于等于 left - 1 ， 左边界小于等于 right + 1 的区间集 to_sease 。
  • 设区间集合 to_sease 的第一个区间为 a = [a1, a2]，最后一个区间为 b = [b1, b2] 。
  • 将 to_sease 中所有区间从 s 中删除，且 cnt 减去这些区间包含的整数个数。
  • 插入 to_sease 和 [left, right] 合并后的区间 [L, R] ，其中 L = min(left, a1); R = max(right, b2) ，形成新的区间集 s ，且 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class CountIntervals
{
public:
    typedef pair<int, int> pii; // pii 表示一个区间，first为区间的右边界，second为左边界

    set<pii> s; // 存储所有合并后的区间
    int cnt; // 区间集 s 包含的所有整数个数

    CountIntervals()
    {
        cnt = 0;
    }

    // 对于一个新的区间[left, right]
    // 在 s 中找到 所有 右边界 大于等于 left - 1 ， 左边界 小于等于 right + 1 的区间集 to_sease
    // 设该区间集合的第一个区间为 a = [a1, a2]，最后一个区间为 b = [b1, b2]
   	// 将 to_sease 中所有区间从 s 中删除，并插入一个合并后的区间 [L, R]
    // 其中 L = min(left, a1), R = max(right, b2)
    void add(int left, int right)
    {
        int L = left, R = right;
        auto it = s.lower_bound(pii(left - 1, 0)); // 找到 第一个 右边界 大于等于 left - 1 的区间 it
        vector<pair<int, int>> to_erase; // 需要删除的区间，即与区间[left, right]相连或有交集的区间
        while(it != s.end())
        {
            if (it->second > right + 1)
                break;
            // 左边界 小于等于 right + 1 ，右边界大于等于left - 1 的所有区间，即与区间[left, right]相连或有交集，需要删除
            to_erase.emplace_back(*it);
            ++it;
        }
        if(to_erase.size())
        {
            L = min(L, to_erase.front().second);
            R = max(R, to_erase.back().first);
            for(auto &x : to_erase) // 删除区间，除去这些区间所包含的整数个数
            {
                cnt -= x.first - x.second + 1;
                s.erase(x);
            }
        }
        s.insert(pii(R, L)); // 插入合并后的区间
        cnt += (R - L + 1); // 加上这个区间所包含的整数个数
    }

    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();
 */