力扣第 277 场周赛

比赛时间 2022-01-23。本场周赛国服共 970 人 AK。被扣友们戏称为“网速场”（已经不是“手速场”了）。

T1. 元素计数（3 分）

解题思路

模拟。先找到最小值和最大值，再统计符合条件的元素数目。

时间复杂度：O(n)。

参考代码

class Solution {
    public int countElements(int[] nums) {
        int min = Arrays.stream(nums).min().getAsInt();
        int max = Arrays.stream(nums).max().getAsInt();
        int cnt = 0;
        for (int num : nums) {
            if (num > min && num < max) {
                cnt++;
            }
        }
        return cnt;
    }
}

T2. 按符号重排数组（4 分）

解题思路

模拟。先将正数负数分组，再重新组合即可。

时间复杂度：O(n)。

参考代码

class Solution {
    public int[] rearrangeArray(int[] nums) {
        List<Integer> gt0List = new ArrayList<>();
        List<Integer> lt0List = new ArrayList<>();
        for (int num : nums) {
            if (num > 0) {
                gt0List.add(num);
            } else {
                lt0List.add(num);
            }
        }

        List<Integer> resList = new ArrayList<>();
        int len = gt0List.size();
        for (int i = 0; i < len; i++) {
            resList.add(gt0List.get(i));
            resList.add(lt0List.get(i));
        }
        return resList.stream().mapToInt(i -> i).toArray();
    }
}

T3. 找出数组中的所有孤独数字（5 分）

解题思路

哈希表。HashMap 预处理之后逐个判断即可。

时间复杂度：O(n)。

参考代码

class Solution {
    public List<Integer> findLonely(int[] nums) {
        Map<Integer, Integer> cntMap = new HashMap<>();
        for (int num : nums) {
            cntMap.put(num, cntMap.getOrDefault(num, 0) + 1);
        }

        List<Integer> resList = new ArrayList<>();
        for (int num : cntMap.keySet()) {
            if (cntMap.get(num) == 1 && !cntMap.containsKey(num - 1) && !cntMap.containsKey(num + 1)) {
                resList.add(num);
            }
        }
        return resList;
    }
}

T4. 基于陈述统计最多好人数（6 分）

解题思路

状态压缩。注意到 n <= 15，可用枚举出所有组合，再从每种可行的组合中找出好人 的 最大 数目即可。

时间复杂度：O(2^n * n^2)。

参考代码

class Solution {
    public int maximumGood(int[][] statements) {
        int n = statements.length;
        int max = 0;
        // 状态压缩 2^15 = 32768
        for (int state = 0; state < (1 << n); state++) {
            // 二进制 1 的个数，1 代表选取
            int i = Integer.bitCount(state);

            if (check(statements, state)) {
                max = Math.max(max, i);
            }
        }
        return max;
    }

    private boolean check(int[][] statements, int state) {
        int n = statements.length;
        Set<Integer> goodMan = new HashSet<>();
        for (int k = 0; k < n; k++) {
            if (((state >> k) & 1) > 0) {
                goodMan.add(k);
            }
        }
        for (int good : goodMan) {
            for (int i = 0; i < n; i++) {
                int statement = statements[good][i];
                // 0 表示 i 的陈述认为 j 是 坏人 。
                if (statement == 0 && goodMan.contains(i)) {
                    return false;
                }
                // 1 表示 i 的陈述认为 j 是 好人 。
                if (statement == 1 && !goodMan.contains(i)) {
                    return false;
                }
            }
        }
        return true;
    }
}

（全文完）