上岸算法 LeetCode Weekly Contest 293解题报告

[是无为青年]

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

可以排序来判断是否字母异位词。

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;
    }
}