LeetCode第293场周赛

• 5234. 移除字母异位词后的结果数组
• • 题目描述
  • 方法一：模拟
  • 方法二：模拟+字符串排序
• 6064. 不含特殊楼层的最大连续楼层数
• • 题目描述
  • 方法：排序后计算间隔
• 6065. 按位与结果大于零的最长组合
• • 题目描述
  • 方法一：DFS（超时）
  • 方法二：脑筋急转弯
• 6066. 统计区间中的整数数目

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

class Solution {
    public List removeAnagrams(String[] words) {
        int n = words.length;
        // 保存删去的word的下标
        Set set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (set.contains(i)) {
                continue ;
            }
            // 将当前word的字母放入哈希表中
            int[] freq = new int[26];
            for (int j = 0; j < words[i].length(); j++) {
                char c = words[i].charAt(j);
                freq[c - 'a']++;
            }
			// 与相邻word比较       
            int j = i + 1;
            // 寻找下一个word
            while (j < words.length && set.contains(j)) {
                j++;
            }
            if (j >= words.length) {
                continue;
            }
			// 统计相邻word里的字母
            for (int t = 0; t < words[j].length(); t++) {
                char c = words[j].charAt(t);
                freq[c - 'a']--;
            }
            boolean flag = false;
            for (int f : freq) {
                if (f != 0) {
                    flag = true;
                }
            }
            // 属于当前word的字母异位词
            if (!flag) {
                set.add(j);
                i--;
            }
        }
        // 统计结果
        List res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!set.contains(i)) {
                res.add(words[i]);
            }
        }
        return res;
    }
}

• 字符排序后依次比较

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

• 首先对special数组从小到大进行排序
• 随后计算数列{ bottom special[0] special[1]...special[n-1] top }相邻间隔，取最大值即可

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

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

采用LeetCode 78. 子集的思路，求出所有子集，执行 按位与 ，找出结果大于0的最长子集

public class Solution {
    int maxLen = 0;
    public int largestCombination(int[] candidates) {
		dfs(candidates, 0, 0xFFFF, 0);
        return maxLen;
    }

    private void dfs(int[] candidates, int idx, int res, int len) {
		if (idx == candidates.length) {
            if (res > 0) {
                maxLen = Math.max(maxLen, len);
            }
            return ;
        }

        if (res <= 0) {
            return ;
        }

        // xuan
        dfs(candidates, idx + 1, res & candidates[idx], len + 1);
        // bu xuan
        dfs(candidates, idx + 1, res, len);

    }
}

• 时间复杂度： O ( 2 n ) O(2^n) O(2n)。一共 2 n 2^n 2n 个状态

• 空间复杂度： O ( 1 ) O(1) O(1)

两个数做与运算，只有当它们存在共同的二进制位都是 1 时，结果才不是 0

找按位与运算结果不为0的最大长度，可以转换为有多少个数有共同的二进制位都是 1。

遍历数组，统计32位上哪一位1出现的个数最多即可，该位为1的这几个数 按位与 一定大于0且长度最长。

class Solution {
    public int largestCombination(int[] candidates) {        
        int maxLen = 0;
        int[] freq = new int[32];
        for (int num : candidates) {
            for (int i = 0; i < 32; i++) {
                if (((num >> i) & 1) == 1) {
                    freq[i]++;
                }
            }
        }
        for (int i = 0; i < 32; i++) {
            maxLen = Math.max(maxLen, freq[i]);
        }
        return maxLen;
    }
}

• 时间复杂度： O ( C × n ) O(Ctimes n) O(C×n)， C = 32 C = 32 C=32
• 空间复杂度： O ( C ) O(C) O(C)