Leetcode之第293场周赛小记_java

小记

本篇博客主要记录第二次参加leetcode周赛（293场次）的成绩，以及对题目的总结，以便鞭策自己不断前进。

这次周赛是我第二次参加，相比于第一次，第一道题目做的更加快了。但是这一次卡在第二题中，思路正确但是老是有些隐藏案例会超时，修改多次没有思路。时间不足，就跳过坐后面的题，但是脑袋里还是想着第题，导致没有任何思路。之后卡着竞赛结束的时间，把第二题调试成功。以下是我这次的成绩：

这一部分主要是对题目进行总结，记录题目的思路以及解答代码，也是为之后面试做准备。

题目一：移除字母异位词后的结果数组

思路：这道题可以理解为字符串去重，将由同样数量字母组成的字符串去掉，需要注意的是只比较数组中相邻的字符串：

1，首先，将第一个数组中的第一个字符串放进结果列表中，然后遍历数组中的剩余字符串。

2，统计两个字符串中各个字母的数量，如果不同则将该字符串放入结果集中。

3，每次比较的两个字符串为：结果集中最后一个字符串，以及String数组中的字符串。

4，比较字符串中各个字母的数量的方法：创建大小26的数组，遍历字符串，将的字母位置对应的数组值加一。

解决代码：

class Solution {
    public  List<String> removeAnagrams(String[] words) {
        if (words==null ||words.length==0) return null;
        List<String> result = new ArrayList<>();
        result.add(words[0]);
        for (int i = 1; i <words.length ; i++) {
             if (getCommon(result.get(result.size()-1),words[i])){
                 result.add(words[i]);
             }
        }
        return result;
    }
    public  boolean getCommon(String a,String b){
        int[] arr = new int[26];
        if (a.length()!=b.length()) return true;
        for (int i = 0; i < a.length(); i++) {
            arr[a.charAt(i)-'a']+=1;
            arr[b.charAt(i)-'a']-=1;
        }
        for (int i = 0; i <26 ; i++) {
            if (arr[i]!=0){
                return true;
            }
        }
        return false;
    }
}

题目二：不含特殊楼层的最大连续楼层数

思路：本题是统计数组[bottom,top]中，被special数组中数分割后的最大连续数量：

1，本题思路很简单：首先，将special数组进行排序，那么被特殊楼层分割后的各个连续数组为，[special数组中最小值即special[0]-bottom]，[special[i+1]-special[i]-1]，[top-special[n-1]]。

2，遍历这些连续区间，求出其中的最大值。

解决代码：

class Solution {
    public static int maxConsecutive(int bottom, int top, int[] special) {
        Arrays.sort(special);
        int n =special.length;
        int result = Integer.MIN_VALUE;
        for (int i = 0; i

 
题目三： 按位与结果大于零的最长组合 
 
思路： 首先，要明白按位与的结果 0&0=0，0&1=0，1&0= 0，1 & 1= 1。因此只要每一位都为1，那么按位与的结果必为1，只要有一位为1，那么结果必大于0。 
因此，只要统计数组中的数，32位上哪一位为1的数的个数最多，那么这就是按位与结果大于 0 的 最长 组合的长度。 
解决代码： 
class Solution {
  public int largestCombination(int[] candidates) {
    int[] cnt = new int[32];
    int max = 0;
    for (int c : candidates) {
      for (int i = 0; i < 32; i++) {
        if (((1 << i) & c) > 0) cnt[i]++;
      }
    }
    for (int i = 0; i < 32; i++) {
      max = Math.max(max, cnt[i]);
    }
    return max;
  }
}
 
题目四：统计区间中的整数数目 
 
思路： 思路提供者leetcode上的大佬灵茶山艾府。珂朵莉树 
用一颗平衡树维护若干个不相交的区间，每次 add(left,right) 时，删除被该区间覆盖到的区间（部分覆盖也算），然后将这些区间与
    
     
      
       
        [
       
       
        l
       
       
        e
       
       
        f
       
       
        t
       
       
        ,
       
       
        r
       
       
        i
       
       
        g
       
       
        h
       
       
        t
       
       
        ]
       
       
        ]
       
      
      
       [left,right]]
      
     
    [left,right]]合并成一个新的大区间，插入平衡树中。 
代码实现时，为方便找到第一个被
    
     
      
       
        [
       
       
        l
       
       
        e
       
       
        f
       
       
        t
       
       
        ,
       
       
        r
       
       
        i
       
       
        g
       
       
        h
       
       
        t
       
       
        ]
       
       
        ]
       
      
      
       [left,right]]
      
     
    [left,right]]覆盖到的区间，我们可以用平衡树的key存区间右端，value 存区间左端点。我们要找的就是第一个 key≥left 的区间。 
解决代码： 时间复杂度：0(logn);空间复杂度：O(n) 
class CountIntervals {
    TreeMap<Integer, Integer> m = new TreeMap<>();
    int cnt;

    public CountIntervals() {}

    public void add(int left, int right) {
        // 遍历所有被 [left,right] 覆盖到的区间（部分覆盖也算）
        for (var e = m.ceilingEntry(left); e != null && e.getValue() <= right; e = m.ceilingEntry(left)) {
            int l = e.getValue(), r = e.getKey();
            left = Math.min(left, l);   // 合并后的新区间，其左端点为所有被覆盖的区间的左端点的最小值
            right = Math.max(right, r); // 合并后的新区间，其右端点为所有被覆盖的区间的右端点的最大值
            cnt -= r - l + 1;
            m.remove(r);
        }
        cnt += right - left + 1;
        m.put(right, left); // 所有被覆盖到的区间与 [left,right] 合并成一个新区间
    }

    public int count() { return cnt; }
}
 
总结：以上就是LeetCode第293场周赛题目，这次又是只做出了两道题，第三道题思路很简单易懂，而第四道题是毫无思路，完全看答案学习的。还是要继续加油，保二争三（四）。					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/langs/941917.html

Leetcode之第293场周赛小记

发表评论

评论列表（0条）