力扣周赛293题解

第一题

力扣原题链接：

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

单个题解：

力扣2273. 移除字母异位词后的结果数组

题目：

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

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

1. 0 < i < words.length
2. 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] 由小写英文字母组成

Related Topics

• 数组
• 哈希表
• 字符串
• 排序

思路：

遍历字符串数组，分别将每一个字符串装换成字符数组，字符数组排序，如果排序后转成的字符串一样，则说明是字母异位词

代码：

java：

class Solution {
    
    public List<String> removeAnagrams(String[] words) {
    
        char[] strs = words[0].toCharArray();
        Arrays.sort(strs);
        List<String> list = new ArrayList<>();
        int index = 0;
        for (int i = 1; i < words.length; i++) {
    
            char[] strs1 = words[i].toCharArray();
            Arrays.sort(strs1);
            if (!String.valueOf(strs).equals(String.valueOf(strs1))) {
    
                list.add(words[index]);
                strs = strs1;
                index = i;
            }
        }
        list.add(words[index]);
        return list;
    }
}

第二题

力扣原题链接：

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

单个题解：

力扣2274. 不含特殊楼层的最大连续楼层数

题目：

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 <= 105
• 1 <= bottom <= special[i] <= top <= 109
• special 中的所有值 互不相同

Related Topics

• 数组
• 排序

思路：

这题相当于在bottom到top的范围内，被special的数分割了，我们需要找到分割后最长的一段

步骤：

1. 为了保证数据的顺序进行，对special进行排序
2. 遍历special对bottom~top进行分割，当bottom<=special[i]时，
   连续楼层数为special[i]-bottom，与之前的最大连续层数对比，得到当前的最大连续层数，
   同时更新bottom = special[i] + 1
3. 遍历完，还有最后一段的连续层数top - special[special.length - 1]
4. 至此，不包含特殊层的最大的连续层数就出来了

代码：

java：

class Solution {
    
    public int maxConsecutive(int bottom, int top, int[] special) {
    
        Arrays.sort(special);
        int max = 0;
        for (int j : special) {
    
            if (bottom <= j) {
    
                max = Math.max(max, j - bottom);
                bottom = j + 1;
            }
        }
        max = Math.max(max, top - special[special.length - 1]);
        return max;
    }
}

第三题

力扣原题链接：

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

单个题解：

力扣2275. 按位与结果大于零的最长组合

题目：

对数组 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 <= 105
• 1 <= candidates[i] <= 107

Related Topics

• 位运算
• 数组
• 哈希表
• 计数

思路：

这题需要找出按位与结果大于0的最长组合的长度，按位与结果大于0，
说明这个数组中的每一个二进制数都有相同的一位是1，根据这题给的数组值的范围，
可以确定最多有24位，那么我们可以循环24次数组，每一次循环统计出第i位位数为1的个数，
然后将每一次的个数做比较，得出最长组合的长度

代码：

java：

class Solution {
    
    public int largestCombination(int[] candidates) {
    
        int max = 0;
        for (int i = 0; i < 25; i++) {
    
            int cnt = 0;
            for (int j = 0; j < candidates.length; j++) {
    
                if ((candidates[j] & (1 << i)) > 0) {
    
                    cnt++;
                }
            }
            max = Math.max(max, cnt);
        }
        return max;
    }
}

第四题

力扣原题链接：

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

单个题解：

力扣2276. 统计区间中的整数数目

题目：

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

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

实现 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 <= 109
• 最多调用 add 和 count 方法 总计105 次
• 调用 count 方法至少一次

思路：

这题我的思路是添加一次整理一次并同时计数，利用java的TreeSet结构，可以快速的定位数据。
典型的模板题

代码：

java：

class CountIntervals {
    
    TreeSet<Interval> ranges;
    int cnt;
    public CountIntervals() {
    
        ranges = new TreeSet();
        cnt = 0;
    }
    public void add(int left, int right) {
    
        Iterator<Interval> itr = ranges.tailSet(new Interval(0, left - 1)).iterator();
        while (itr.hasNext()) {
    
            Interval iv = itr.next();
            if (right < iv.left) {
    
                break;
            }
            left = Math.min(left, iv.left);
            right = Math.max(right, iv.right);
            cnt -= iv.right - iv.left + 1;
            itr.remove();
        }
        ranges.add(new Interval(left, right));
        cnt += right - left + 1;
    }
    public int count() {
    
        return cnt;
    }
}
public class Interval implements Comparable<Interval> {
    
    int left;
    int right;
    public Interval(int left, int right) {
    
        this.left = left;
        this.right = right;
    }
    public int compareTo(Interval that) {
    
        if (this.right == that.right) return this.left - that.left;
        return this.right - that.right;
    }
}