A.
双指针数组去重问题,区别在于仅删除原本数组中连续重复元素
class Solution {
public:
bool check(string A, string B) {
sort(A.begin(), A.end());
sort(B.begin(), B.end());
return A == B;
}
vector<string> removeAnagrams(vector<string>& words) {
int g = 0;
for(int i = 0; i < words.size(); ++i) {
words[g++] = words[i];
int j = i + 1;
while(j < words.size() && check(words[i], words[j])) j += 1;
i = j - 1;
}
while(words.size() > g) words.pop_back();
return words;
}
};
B.
考虑放松楼层之间不包括边界,如果
b
o
t
t
o
m
bottom
bottom和
t
o
p
top
top不是边界,则需要包括进来。
class Solution {
public:
int maxConsecutive(int bottom, int top, vector<int>& sp) {
sort(sp.begin(), sp.end());
int res = sp.front() - bottom;
int pre = sp.front();
for(auto u : sp) res = max(res, u - pre - 1), pre = u;
res = max(res, top - pre);
return res;
}
};
C.
计算二进制每位的数的最多个数
class Solution {
public:
int largestCombination(vector<int>& candidates) {
int res = 0;
for(int i = 30; i >= 0; --i) {
int temp = 0;
for(auto u : candidates)
if(u >> i & 1) temp += 1;
res = max(res, temp);
}
return res;
}
};
D.
维护一个set<pair<int, int>> ,每次add(left, right) 时,考虑从右端点大于等于left-1 的区间开始合并,直到区间左端点大于right + 1 停止。 这里有一个维护技巧是pair.first 保存区间右端点,pair.second 保存区间左端点,这样可以借set.lower_bound 二分出第一个大于等于left-1 的区间。因为所有的区间一定是不交叉的,所以按pair.first=右端点 来使得set 有序依旧是正确的区间顺序。
class CountIntervals {
public:
set<pair<int, int>> S;
int len;
CountIntervals() {
S.clear();
len = 0;
}
void add(int left, int right) {
int L = left, R = right;
auto it = S.lower_bound({left - 1, -1});
while(it != S.end()) {
if(it->second > right + 1) break;
L = min(L, it->second);
R = max(R, it->first);
len -= it->first - it->second + 1;
it = S.erase(it);
}
len += R - L + 1;
S.insert({R, L});
}
int count() {
return len;
}
};
|