周赛 - 🏆 第 277 场力扣周赛 - 《学习笔记》

5989. 元素计数
5991. 按符号重排数组
5990. 找出数组中的所有孤独数字
5992. 基于陈述统计最多好人数

寄，请务必确定能过再交，如果罚时则毫无意义。
还好没掉分，掉怕了都！
手速场！离谱

5989. 元素计数

给你一个整数数组 nums ，统计并返回在 nums 中同时具有一个严格较小元素和一个严格较大元素的元素数目。

示例 1：
输入：nums = [11,7,2,15] 输出：2 解释：元素 7 ：严格较小元素是元素 2 ，严格较大元素是元素 11 。元素 11 ：严格较小元素是元素 7 ，严格较大元素是元素 15 。总计有 2 个元素都满足在 nums 中同时存在一个严格较小元素和一个严格较大元素。
示例 2：
输入：nums = [-3,3,3,90] 输出：2 解释：元素 3 ：严格较小元素是元素 -3 ，严格较大元素是元素 90 。由于有两个元素的值为 3 ，总计有 2 个元素都满足在 nums 中同时存在一个严格较小元素和一个严格较大元素。

提示：

1 <= nums.length <= 100
-105 <= nums[i] <= 105

class Solution {
    public int countElements(int[] nums) {
        Arrays.sort(nums);
        int min = nums[0], max = nums[nums.length - 1];
        int cnt = 0;
        for (int x : nums)
            if (x > min && x < max)
                    cnt++;
        return cnt;
    }
}

5991. 按符号重排数组

给你一个下标从 0 开始的整数数组 nums ，数组长度为偶数，由数目相等的正整数和负整数组成。
你需要重排 nums 中的元素，使修改后的数组满足下述条件：

任意连续的两个整数 符号相反
对于符号相同的所有整数，保留它们在 nums 中的顺序。
重排后数组以正整数开头。

重排元素满足上述条件后，返回修改后的数组。

示例 1：
输入：nums = [3,1,-2,-5,2,-4] 输出：[3,-2,1,-5,2,-4] 解释： nums 中的正整数是 [3,1,2] ，负整数是 [-2,-5,-4] 。重排的唯一可行方案是 [3,-2,1,-5,2,-4]，能满足所有条件。像 [1,-2,2,-5,3,-4]、[3,1,2,-2,-5,-4]、[-2,3,-5,1,-4,2] 这样的其他方案是不正确的，因为不满足一个或者多个条件。
示例 2：
输入：nums = [-1,1] 输出：[1,-1] 解释： 1 是 nums 中唯一一个正整数，-1 是 nums 中唯一一个负整数。所以 nums 重排为 [1,-1] 。

提示：

2 <= nums.length <= 2 * 105
nums.length 是偶数
1 <= |nums[i]| <= 105
nums 由相等数量的正整数和负整数组成

思路：
二路归并即可

class Solution {
    public int[] rearrangeArray(int[] nums) {
        int n = nums.length, m = n / 2;
        int[] b = new int[m], c = new int[m];
        int l = 0, r = 0;
        for (int x : nums) {
            if (x > 0) b[l++] = x;
            else c[r++] = x;
        }
        int idx = 0;
        for (int i = 0; i < m; i++) {
            nums[idx++] = b[i];
            nums[idx++] = c[i];
        }
        return nums;
    }
}

5990. 找出数组中的所有孤独数字

给你一个整数数组 nums 。如果数字 x 在数组中仅出现一次，且没有相邻数字（即，x + 1 和 x - 1）出现在数组中，则认为数字 x 是 孤独数字 。
返回_ _nums 中的所有孤独数字。你可以按 任何顺序 返回答案。

示例 1：
输入：nums = [10,6,5,8] 输出：[10,8] 解释： - 10 是一个孤独数字，因为它只出现一次，并且 9 和 11 没有在 nums 中出现。 - 8 是一个孤独数字，因为它只出现一次，并且 7 和 9 没有在 nums 中出现。 - 5 不是一个孤独数字，因为 6 出现在 nums 中，反之亦然。因此，nums 中的孤独数字是 [10, 8] 。注意，也可以返回 [8, 10] 。
示例 2：
输入：nums = [1,3,5,3] 输出：[1,5] 解释： - 1 是一个孤独数字，因为它只出现一次，并且 0 和 2 没有在 nums 中出现。 - 5 是一个孤独数字，因为它只出现一次，并且 4 和 6 没有在 nums 中出现。 - 3 不是一个孤独数字，因为它出现两次。因此，nums 中的孤独数字是 [1, 5] 。注意，也可以返回 [5, 1] 。

提示：

1 <= nums.length <= 105
0 <= nums[i] <= 106

思路：
哈希

class Solution {
    public List<Integer> findLonely(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums)
            map.merge(x, 1, Integer::sum);
        List<Integer> res = new ArrayList<>();
        for (int x : map.keySet()) {
            if (map.get(x) == 1) {
                if (map.getOrDefault(x - 1, 0) == 0 && map.getOrDefault(x + 1, 0) == 0)
                    res.add(x);
            }
        }
        return res;
    }
}

5992. 基于陈述统计最多好人数

游戏中存在两种角色：

好人：该角色只说真话。
坏人：该角色可能说真话，也可能说假话。

给你一个下标从 0 开始的二维整数数组 statements ，大小为 n x n ，表示 n 个玩家对彼此角色的陈述。具体来说，statements[i][j] 可以是下述值之一：

0 表示 i 的陈述认为 j 是坏人。
1 表示 i 的陈述认为 j 是好人。
2 表示 i 没有对 j 作出陈述。

另外，玩家不会对自己进行陈述。形式上，对所有 0 <= i < n ，都有 statements[i][i] = 2 。
根据这 n 个玩家的陈述，返回可以认为是好人的最大数目。

示例 1：
输入：statements = [[2,1,2],[1,2,2],[2,0,2]] 输出：2 解释：每个人都做一条陈述。 - 0 认为 1 是好人。 - 1 认为 0 是好人。 - 2 认为 1 是坏人。以 2 为突破点。 - 假设 2 是一个好人： - 基于 2 的陈述，1 是坏人。 - 那么可以确认 1 是坏人，2 是好人。 - 基于 1 的陈述，由于 1 是坏人，那么他在陈述时可能： - 说真话。在这种情况下会出现矛盾，所以假设无效。 - 说假话。在这种情况下，0 也是坏人并且在陈述时说假话。 - 在认为 2 是好人的情况下，这组玩家中只有一个好人。 - 假设 2 是一个坏人： - 基于 2 的陈述，由于 2 是坏人，那么他在陈述时可能： - 说真话。在这种情况下，0 和 1 都是坏人。 - 在认为 2 是坏人但说真话的情况下，这组玩家中没有一个好人。 - 说假话。在这种情况下，1 是好人。 - 由于 1 是好人，0 也是好人。 - 在认为 2 是坏人且说假话的情况下，这组玩家中有两个好人。 在最佳情况下，至多有两个好人，所以返回 2 。注意，能得到此结论的方法不止一种。
示例 2：
输入：statements = [[2,0],[0,2]] 输出：1 解释：每个人都做一条陈述。 - 0 认为 1 是坏人。 - 1 认为 0 是坏人。以 0 为突破点。 - 假设 0 是一个好人： - 基于与 0 的陈述，1 是坏人并说假话。 - 在认为 0 是好人的情况下，这组玩家中只有一个好人。 - 假设 0 是一个坏人： - 基于 0 的陈述，由于 0 是坏人，那么他在陈述时可能： - 说真话。在这种情况下，0 和 1 都是坏人。 - 在认为 0 是坏人但说真话的情况下，这组玩家中没有一个好人。 - 说假话。在这种情况下，1 是好人。 - 在认为 0 是坏人且说假话的情况下，这组玩家中只有一个好人。 在最佳情况下，至多有一个好人，所以返回 1 。注意，能得到此结论的方法不止一种。

提示：

n == statements.length == statements[i].length
2 <= n <= 15
statements[i][j] 的值为 0、1 或 2
statements[i][i] == 2

思路：
数据范围很小，直接二进制枚举好人即可
时间复杂度：O(N2^N)

class Solution {
    public int maximumGood(int[][] s) {
        int max = 0, n = s.length;
        label: for(int i = 0; i < 1 << n; i++) {
            int t = 0;
            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) == 1) {
                    for (int k = 0; k < n; k++) {
                        if (s[j][k] == 1) {
                            if ((i >> k & 1) != 1) continue label;
                        } else if (s[j][k] == 0) {
                            if ((i >> k & 1) == 1) continue label;
                        }
                    }
                    t++;
                }
            }
            max = Math.max(max, t);
        }
        return max;
    }
}