- 1、移除字母异位词后的结果数组
- 2、不含特殊楼层的最大连续楼层数
- 3、按位与结果大于零的最长组合
- 4、统计区间中的整数数目
题目描述
给你一个下标从 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] 由小写英文字母组成
这题一开始我又在想怎么用哈希表去统计每个单词出现的次数之类的，但之前几次做题让我觉得这个思路可能很复杂，于是我踌躇了一会，最后还是偷懒，用python过了。
class Solution:
def removeAnagrams(self, words: List[str]) -> List[str]:
def isSimilar(w1,w2):
ls1 = list(w1)
ls1.sort()
ls2 = list(w2)
ls2.sort()
return ls1==ls2
ans = [words[0]]
for i in range(1,len(words)):
if not isSimilar(words[i],words[i-1]):
ans.append(words[i])
return ans
当然这段代码冗余度还是太高了，可以省略成一行代码：
class Solution:
def removeAnagrams(self, words: List[str]) -> List[str]:
return [w for i, w in enumerate(words) if i == 0 or sorted(words[i - 1]) != sorted(words[i])]
所以用 Java怎么写呢？都说评论区往往能让迷茫的程序员恍然大悟，找到答案。问题其实很简单，没必要一直用哈希表，字母都是有顺序的，什么顺序？ASCII码的值啊！所以26个字母只需要一个长度为26的int[]数组存储即可。比较两个字符串包含的字母是否相等就相当于比较它们对应int[]数组是否相等。
class Solution {
public List removeAnagrams(String[] words) {
int n = words.length;
List ans = new ArrayList();
ans.add(words[0]);
for(int i=1;i
if(!isSimilar(words[i],words[i-1])){
ans.add(words[i]);
}
}
return ans;
}
//判断两个字符串是否为字母异位词
public boolean isSimilar(String w1,String w2){
int[] ch1 = new int[26], ch2 = new int[26];
for(char c : w1.toCharArray()) ch1[c-'a']++;
for(char c : w2.toCharArray()) ch2[c-'a']++;
for(int k=0;k<26;k++){
if(ch1[k]!=ch2[k]) return false;
}
return true;
}
}
2、不含特殊楼层的最大连续楼层数
题目描述
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 <= 10^5
- 1 <= bottom <= special[i] <= top <= 10^9
- special 中的所有值 互不相同
第二题我纠结了一会，决定还是先用python过了再说。正向排序，先把顶和底单独处理了，然后对列表中的相邻元素依次作差，取最大值。
class Solution:
def maxConsecutive(self, bottom: int, top: int, special: List[int]) -> int:
special.sort()
btm = special[0]-bottom
t = top-special[-1]
maxFloors = max(btm,t)
for i in range(1,len(special)):
maxFloors = max(maxFloors,special[i]-special[i-1]-1) # 注意这里由于楼层本身不算，还要再减1
return maxFloors
当然用Java思路也是一样
class Solution {
public int maxConsecutive(int bottom, int top, int[] special) {
Arrays.sort(special);
int max = -1;
int n = special.length;
max = Math.max(max,special[0]-bottom);
max = Math.max(max,top-special[n-1]);
for(int i=1;i
max = Math.max(max,special[i]-special[i-1]-1);
}
return max;
}
}
3、按位与结果大于零的最长组合
题目描述
对数组 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 <= 10^5
- 1 <= candidates[i] <= 10^7
遇到了不太常见但很基础的位运算。按位与：同1才1，有0则0。所以按位与的结果要么大于0，要么等于0；关键就在于什么情况会让这个结果等于0；这，当时的我是不知道的，
所以第三题我就直接摆烂了。
学习完其他大佬的解法后，思路大概是这样的：按位与，如果想结果不为0，那么参与运算的所有数的二进制表示，至少有一位全都是1，因为只要出现一次0，那么结果就为0了。所以我们要统计，哪个位的1最多，这个数量就是答案。
具体统计过程，我们可以运用位运算的特点，将1依次左移，相当于二进制表示一直在右边加0，然后与每一个candidate做按位与运算，如果结果不为0，则说明当前位的数为1，统计数组中的该位置就加1。
最后返回1的数量最多的位置。
class Solution {
public int largestCombination(int[] candidates) {
int n = candidates.length;
//由于candidate的范围在10^7，小于2^24,所以cnt的长度只要为24即可
int[] cnt = new int[24];
for(int c:candidates){
for(int i=0;i<24;i++){
//依次左移，判断candidate每一位是否为1
if(( (1< 0) cnt[i]++;
}
}
int maxComb = 0;
for(int c:cnt){
maxComb = Math.max(maxComb,c);
}
return maxComb;
}
}
4、统计区间中的整数数目
题目描述
给你区间的 空 集，请你设计并实现满足要求的数据结构：
- 新增： 添加一个区间到这个区间集合中。
- 统计： 计算出现在 至少一个 区间中的整数个数。
实现 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]
解释
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] 中
提示：
- 1 <= left <= right <= 10^9
- 最多调用 add 和 count 方法 总计 10^5 次
- 调用 count 方法至少一次
这道困难题，我一开始以为我能做出来，结果提交的时候直接超出内存限制，简单暴力的集合去重法必然是不能通过的。而且这道题看似描述得很简单，但做出来的人很少，有必要来研究一下。
看了评论区的解法，发现有点看不懂。。。关键出现了我没见过的数据结构——TreeMap。
看来要先了解一下相关知识。
class CountIntervals {
int sum;
TreeMap map;
public CountIntervals() {
sum = 0;
map = new TreeMap<>();
}
public void add(int left, int right) {
Map.Entry l = map.floorEntry(right);
// lt， rt分别记录此次操作后最终的区间的 左边值、右边值
int lt = left;
int rt = right;
while(l != null && l.getValue()[1] >= lt){
// 删除区间，同时对sum做减法
sum -= l.getValue()[1] - l.getValue()[0]+1;
lt = Math.min(lt , l.getValue()[0]);
rt = Math.max(rt , l.getValue()[1]);
map.remove(l.getKey());
l = map.floorEntry(right);
}
// 一次操作过后，添加最终的区间，对sum做加法
map.put(lt , new int[]{lt , rt});
sum += rt-lt+1;
}
public int count() {
return sum;
}
}
OK，以上就是本周的周赛题目，总结一下：
-
对字母统计时，能用一个int[26]的数组就别用哈希表，不要把简单题过分复杂化。
-
位运算要深入了解，如何判断一个数num的第i位是不是1？用(1<
是0。
-
了解TreeMap及其相关操作。
本次周赛表现一般，仍需继续努力。
