🏆 第 257 场力扣周赛

很久以前的了，补一下题。
当时的我好菜啊！！！

1995. 统计特殊四元组

过

1996. 游戏中弱角色的数量

你正在参加一个多角色游戏，每个角色都有两个主要属性：攻击 和 防御 。给你一个二维整数数组 properties ，其中 properties[i] = [attacki, defensei] 表示游戏中第 i 个角色的属性。
如果存在一个其他角色的攻击和防御等级 都严格高于 该角色的攻击和防御等级，则认为该角色为 弱角色 。更正式地，如果认为角色 i 弱于 存在的另一个角色 j ，那么 attackj > attacki 且 defensej > defensei 。
返回 弱角色 的数量。

示例 1：
输入：properties = [[5,5],[6,3],[3,6]] 输出：0 解释：不存在攻击和防御都严格高于其他角色的角色。
示例 2：
输入：properties = [[2,2],[3,3]] 输出：1 解释：第一个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。
示例 3：
输入：properties = [[1,5],[10,4],[4,3]] 输出：1 解释：第三个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。

提示：

• 2 <= properties.length <= 105
• properties[i].length == 2
• 1 <= attacki, defensei <= 105

思路：
方法1：我自己的复杂方法，
排序 + 树状数组
方法2：双关键字排序
问题是如何排？按攻击力从大到小，按防御从小到大。并记录一个当前已经遍历过的所有元素中的最大防御值。

// 方法1
class Solution {
    public int numberOfWeakCharacters(int[][] properties) {
        Arrays.sort(properties, (o1, o2) -> (o2[0] - o1[0]));
        int res = 0;
        int n = properties.length;
        BIT bit = new BIT();
        // System.out.println(Arrays.deepToString(properties));
        for (int i = 0; i < n; i++) {
            int j = i;
            while (j < n && properties[j][0] == properties[i][0]) {
                if (bit.getLarge(properties[j][1]) > 0)
                    res++;
                j++;
            }
            for (int k = i; k < j; k++) {
                bit.add(properties[k][1], 1);
            }
            i = j - 1;
        }
        return res;
    }
}
class BIT {
    int[] a = new int[100010];
    int n = 100010;
    int lowbit(int x) {
        return x & (-x);
    }
    void add(int idx, int x) {
        for (int i = idx; i < n; i += lowbit(i))
            a[i] += x;
    }
    int getLarge(int x) {
        return get(n - 1) - get(x);
    }
    int get(int idx) {
        int res = 0;
        for (int i = idx; i > 0; i -= lowbit(i)) {
            res += a[i];
        }
        return res;
    }
}

//方法2
class Solution {
    public int numberOfWeakCharacters(int[][] properties) {
        Arrays.sort(properties, (o1, o2) -> (o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]));
        int max = 0;
        int cnt = 0;
        for (int[] p : properties) {
            if (max > p[1])
                cnt++;
            else
                max = p[1];
        }
        return cnt;
    }
}

1997. 访问完所有房间的第一天

你需要访问 n 个房间，房间从 0 到 n - 1 编号。同时，每一天都有一个日期编号，从 0 开始，依天数递增。你每天都会访问一个房间。
最开始的第 0 天，你访问 0 号房间。给你一个长度为 n 且 下标从 0 开始 的数组 nextVisit 。在接下来的几天中，你访问房间的 次序 将根据下面的 规则 决定：

• 假设某一天，你访问 i 号房间。
• 如果算上本次访问，访问 i 号房间的次数为 奇数 ，那么 第二天 需要访问 nextVisit[i] 所指定的房间，其中 0 <= nextVisit[i] <= i 。
• 如果算上本次访问，访问 i 号房间的次数为 偶数 ，那么 第二天 需要访问 (i + 1) mod n 号房间。

请返回你访问完所有房间的第一天的日期编号。题目数据保证总是存在这样的一天。由于答案可能很大，返回对 109 + 7 取余后的结果。

示例 1：
输入：nextVisit = [0,0] 输出：2 解释： - 第 0 天，你访问房间 0 。访问 0 号房间的总次数为 1 ，次数为奇数。 下一天你需要访问房间的编号是 nextVisit[0] = 0 - 第 1 天，你访问房间 0 。访问 0 号房间的总次数为 2 ，次数为偶数。 下一天你需要访问房间的编号是 (0 + 1) mod 2 = 1 - 第 2 天，你访问房间 1 。这是你第一次完成访问所有房间的那天。
示例 2：
输入：nextVisit = [0,0,2] 输出：6 解释： 你每天访问房间的次序是 [0,0,1,0,0,1,2,…] 。 第 6 天是你访问完所有房间的第一天。
示例 3：
输入：nextVisit = [0,1,2,0] 输出：6 解释： 你每天访问房间的次序是 [0,0,1,1,2,2,3,…] 。 第 6 天是你访问完所有房间的第一天。

提示：

• n == nextVisit.length
• 2 <= n <= 105
• 0 <= nextVisit[i] <= i

思路：
DP问题，暴力不行，得用前缀和做优化

class Solution {
    public int firstDayBeenInAllRooms(int[] nextVisit) {
        int n = nextVisit.length;
        final int MOD = (int)(1e9 + 7);
        int[] f = new int[n]; //f[i] 表示当前下标为i，跳转到i + 1所需的天数
        f[0] = 2;
        int[] pre = new int[n]; //pre[i] 表示从起点跳到i + 1共需的天数
        pre[0] = 2;
        for (int i = 1; i < n - 1; i++) {
            int left = nextVisit[i] > 0 ? pre[nextVisit[i] - 1] : 0;
            f[i] = (pre[i - 1] - left + MOD + 2) % MOD;
            pre[i] = (pre[i - 1] + f[i]) % MOD;
        }
        // System.out.println(f[0] + " " + (n - 1));
        return pre[n - 2];
    }
}

1998. 数组的最大公因数排序

给你一个整数数组 nums ，你可以在 nums 上执行下述操作 任意次 ：

• 如果 gcd(nums[i], nums[j]) > 1 ，交换 nums[i] 和 nums[j] 的位置。其中 gcd(nums[i], nums[j]) 是 nums[i] 和 nums[j] 的最大公因数。

如果能使用上述交换方式将 nums 按 非递减顺序 排列，返回 true ；否则，返回 false 。

示例 1：
输入：nums = [7,21,3] 输出：true 解释：可以执行下述操作完成对 [7,21,3] 的排序： - 交换 7 和 21 因为 gcd(7,21) = 7 。nums = [21,7,3] - 交换 21 和 3 因为 gcd(21,3) = 3 。nums = [3,7,21]
示例 2：
输入：nums = [5,2,6,2] 输出：false 解释：无法完成排序，因为 5 不能与其他元素交换。
示例 3：
输入：nums = [10,5,9,3,15] 输出：true 解释： 可以执行下述操作完成对 [10,5,9,3,15] 的排序： - 交换 10 和 15 因为 gcd(10,15) = 5 。nums = [15,5,9,3,10] - 交换 15 和 3 因为 gcd(15,3) = 3 。nums = [3,5,9,15,10] - 交换 10 和 15 因为 gcd(10,15) = 5 。nums = [3,5,9,10,15]

提示：

• 1 <= nums.length <= 3 * 104
• 2 <= nums[i] <= 105

思路：
并查集 + 数论
关键结论：将所有不互质的数连边，同一连通块内的数一定可以通过交换变成任意顺序（当然也可以变成从小到大）。
故考虑每个数，将其所有公因子放在一个连通块内(1除外)
拷贝一份原数组并排序
遍历数组，比较每个位置上的新旧数组中的数字是否位于同一连通块内，是则继续，否则返回false。

class Solution {
    int[] fa = new int[100010];
    public boolean gcdSort(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < fa.length; i++)
            fa[i] = i;
        for (int x : nums) {
            int d = x;
            for (int i = 2; i <= d / i; i++) {
                boolean flag = false;
                while (x % i == 0) {
                    flag = true;
                    x /= i;
                }
                if (flag)
                    merge(i, d);
            }
            if (x > 1)
                merge(d, x);
        }
        int[] back = new int[n];
        System.arraycopy(nums, 0, back, 0, n);
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            int x = nums[i], y = back[i];
            if (find(x) != find(y))
                return false;
        }
        return true;
    }
    void merge(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa != pb)
            fa[pa] = pb;
    }
    int find(int x) {
        return x == fa[x] ? x : (fa[x] = find(fa[x]));
    }
}

类似于本题的还有：