移除字母异位词后的结果数组
可以排序来判断是否字母异位词。
class Solution {
public List<String> removeAnagrams(String[] words) {
List<String> result = new ArrayList<>();
result.add(words[0]);
for (int i = 1; i < words.length; i++) {
if (!isAnagram(words[i], words[i - 1])) {
result.add(words[i]);
}
}
return result;
}
private boolean isAnagram(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
char[] chars1 = s1.toCharArray();
char[] chars2 = s2.toCharArray();
Arrays.sort(chars1);
Arrays.sort(chars2);
return Arrays.equals(chars1, chars2);
}
}
不含特殊楼层的最大连续楼层数
把 bottom - 1 和 top + 1 也看作特殊楼层,排序即可。
class Solution {
public int maxConsecutive(int bottom, int top, int[] special) {
List<Integer> list = new ArrayList<>();
for (int s : special) {
list.add(s);
}
list.add(bottom - 1);
list.add(top + 1);
Collections.sort(list);
int max = 0;
for (int i = 1; i < list.size(); i++) {
max = Math.max(max, list.get(i) - list.get(i - 1) - 1);
}
return max;
}
}
按位与结果大于零的最长组合
枚举最终结果是哪一位不为 0 即可,相当于统计每一位的 1 的个数。
class Solution {
public int largestCombination(int[] candidates) {
int res = 0;
for (int i = 0; i <= 31; i++) {
int n = 0; // n 表示第 i 位为 1 的数字的个数
for (int cand : candidates) {
if (((cand >> i) & 1) > 0) {
n++;
}
}
res = Math.max(res, n);
}
return res;
}
}
统计区间中的整数数目
维护有序、不相交的集合,按照左端点排序。
每次加入新集合时,直接查找到可能有相交的集合,进行合并。
class CountIntervals {
TreeSet<Integer> left;
Map<Integer, Integer> right;
int count;
public CountIntervals() {
left = new TreeSet<>();
right = new HashMap<>();
count = 0;
}
private boolean hasInc(int l1, int r1, int l2, int r2) {
// 判断 [l1, r1] 和 [l2, r2] 是否有交集
if (l1 < l2 && r1 < l2) {
return false;
}
if (l1 > r2 && r1 > r2) {
return false;
}
return true;
}
public void add(int left, int right) {
List<Integer> toRemove = new ArrayList<>();
Integer lower = this.left.floor(left);
if (lower == null) {
lower = left;
}
for (int l : this.left.tailSet(lower, true)) {
if (l > right) {
break;
}
int r = this.right.get(l);
if (hasInc(left, right, l, r)) {
toRemove.add(l);
count -= r - l + 1;
left = Math.min(left, l);
right = Math.max(right, r);
}
}
for (int l : toRemove) {
this.left.remove(l);
this.right.remove(l);
}
this.left.add(left);
this.right.put(left, right);
count += right - left + 1;
}
public int count() {
return count;
}
}