Problem List
- [1] 移除字母异位词后的结果数组
- [2] 不含特殊楼层的最大连续楼层数
- [3] 按位与结果大于零的最长组合
- [4] 统计区间中的整数数目
1 移除字母异位词后的结果数组
1.1 题目描述
- 题目链接：2273. 移除字母异位词后的结果数组
1.1 题目描述
给你一个下标从 0 开始的字符串 words ，其中 words[i] 由小写英文字符组成。
在一步操作中，需要选出任一下标 i ，从 words 中 删除 words[i] 。其中下标 i 需要同时满足下述两个条件：
0 < i < words.lengthwords[i - 1]和words[i]是 字母异位词 。
只要可以选出满足条件的下标，就一直执行这个操作。
在执行所有操作后，返回 words 。可以证明，按任意顺序为每步操作选择下标都会得到相同的结果。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。例如，"dacb" 是 "abdc" 的一个字母异位词。
示例1：
输入: words = [“abba”,”baba”,”bbaa”,”cd”,”cd”]
输出: [“abba”,”cd”]
示例2：
输入: words = [“a”,”b”,”c”,”d”,”e”]
输出: [“a”,”b”,”c”,”d”,”e”]
1.2 思路
也就是如果相邻两个 word 为 字母异位词 ，则保留前边一个单词，删去后一个单词直至相邻两个单词不为 字母异位词 。因此，可以遍历整个 words, 并用两个哈希表分别记录前一个单词的每个字母出现的次数以及后一个单词的字母次数，然后进行对比，如果二者的每个字母出现的次数均一致，说明二者互为字母异位词，进而不跳过当前单词(前一个单词插入答案中，后一个不插入)。
class Solution {
public:
vector<string> removeAnagrams(vector<string>& words) {
int n = words.size();
int last_hash[26] = {0};
for(auto c: words[0]){
last_hash[c - 'a']++;
}
vector<string> res;
res.emplace_back(words[0]);
for(int i = 1; i < n; ++i){
int hash[26] = {0};
for(auto ch: words[i]){
hash[ch - 'a']++;
}
int cnt = 0;
for(int i = 0; i < 26; ++i){
if(hash[i] == last_hash[i]){
cnt++;
}
}
if(cnt == 26){
continue;
}else{
res.emplace_back(words[i]);
for(int i = 0; i< 26; ++i){
last_hash[i] = hash[i];
}
}
}
return res;
}
}; 2 不含特殊楼层的最大连续楼层数
2.1 题目描述
- 题目链接：2274. 不含特殊楼层的最大连续楼层数
2.1 题目描述
Alice 管理着一家公司，并租用大楼的部分楼层作为办公空间。Alice 决定将一些楼层作为 特殊楼层 ，仅用于放松。
给你两个整数 bottom 和 top ，表示 Alice 租用了从 bottom 到 top（含 bottom 和 top 在内）的所有楼层。另给你一个整数数组 special ，其中 special[i] 表示? Alice 指定用于放松的特殊楼层。
返回不含特殊楼层的 最大 连续楼层数。
示例1：
输入: bottom = 2, top = 9, special = [4,6]
输出: 3
示例2：
输入: bottom = 6, top = 8, special = [7,6,8]
输出: 0
2.2 思路
找不含特殊楼层的 最大 连续楼层数，实际上就是找bottom 到特殊楼层中的最低层之间的层数、特殊楼层最顶层到 top 之间的层数和特殊楼层中的间隔层数三者中的最大值。因而直接对特殊楼层数组special进行排序，然后m1 = max(special[0]-bottom, top - special[special.size()-1])即为前二者的最大值，然后遍历整个special数组来求取特殊楼层间最大间隔层数m2 = max(m, special[i]-special[i-1]-1), 最后max(m1, m2)即为答案。
注意：特殊楼层间隔层数要在
special[i]-special[i-1]的基础上再减去1，因为不包括两端的边界。
class Solution {
public:
int maxConsecutive(int bottom, int top, vector<int>& special) {
sort(special.begin(), special.end());
int res = 0, n = special.size();
for(int i = 1; i < n; i++){
res = max(res, special[i]- special[i-1] - 1);
}
return max(max(special[0] - bottom, top - special[n-1]), res);
}
}; 3 按位与结果大于零的最长组合
3.1 题目描述
- 题目链接：2275. 按位与结果大于零的最长组合
3.1 题目描述
对数组?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
示例2：
输入: candidates = [8,8]
输出: 2
3.2 思路
自己的思路是两个for循环逐位遍历整个数组，当当前结果和当前遍历的数组按位与后为0则不选取该数字，否则则选取当前数字。但实际上这种做法并不能求得最长长度。
大佬的想法是统计数组中32个bit上每个元素上为1的数量，某一个bit为1最多的即为按位与后结果大于0的最长组合长度。
class Solution {
public:
int largestCombination(vector<int>& candidates) {
int n = candidates.size();
int res = 0;
for(int i = 24; i >= 0; --i){
int cnt = 0;
for(int j: candidates){
if(j>>i & 1){
cnt++;
}
}
res = max(res, cnt);
}
return res;
}
}; 4 统计区间中的整数数目
4.1 题目描述
- 题目链接：2276. 统计区间中的整数数目
4.1 题目描述
给你区间的 空 集，请你设计并实现满足要求的数据结构：
- 新增：添加一个区间到这个区间集合中。
- 统计：计算出现在 至少一个 区间中的整数个数。
实现 CountIntervals 类：
CountIntervals()使用区间的空集初始化对象void add(int left, int right)添加区间[left, right]到区间集合之中。int count()返回出现在 至少一个 区间中的整数个数。
注意：区间 [left, right] 表示满足 left <= x <= right 的所有整数 x 。
示例1：
输入: [“CountIntervals”, “add”, “add”, “count”, “add”, “count”]
[[], [2, 3], [7, 10], [], [5, 8], []]
输出: [null, null, null, 6, null, 8]
示例2：
输入: words = [“a”,”b”,”c”,”d”,”e”]
输出: 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] 中
4.2 思路
其实就是 区间合并，用一个哈希表来存储当前的区间，然后查找待插入区间的位置，这里用set.lower_bound来找待插入区间左端点位于当前区间集的位置(当前区间集为有序集合), 然后再考虑待插入区间的右端点。循环遍历区间集，当当前遍历到的区间的左端点大于待插入区间的右端点时说明右端点的位置已经找到，进而插入待插入区间，并从区间集中删去重叠部分。
class CountIntervals {
set<pair<int, int>> s;
int cnt;
public:
CountIntervals() {
cnt = 0;
}
void add(int left, int right) {
auto iter = s.lower_bound(make_pair(left, 0)); //找左端点
if(iter != s.begin()){
iter--;
}
int l = left, r = right;
vector<pair<int, int>> to_erase;
while(iter != s.end() && iter->first <= right){ //找右端点
if(iter->second < left - 1){
iter++;
continue;
}
to_erase.emplace_back(*iter); //记录待删去的区间
l = min(iter->first, l);
r = max(r, iter->second);
iter++;
}
//必须要先删去区间后再将待插入区间插入
for(auto& i: to_erase){ //删去区间
cnt -= i.second - i.first + 1;
s.erase(i);
}
cnt += (r - l + 1);
s.insert(make_pair(l, r));
}
int count() {
return cnt;
}
};注意：必须要删去重叠部分的区间之后再进行待插入区间的插入。如果先插入后删除，可能会出现待插入区间本身就存在于区间集，此时这个区间集是需要被删去的，那么先插入该区间，而set不允许同个key的插入，因而会插入失败，然后删除时会把该区间删去，导致区间插入失败，即如果区间集中存在待插入区间时，实际上是先删去该区间再重新插入该区间。
