力扣第257场周赛

题一 统计特殊四元组

描述

给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目 ：

nums[a] + nums[b] + nums[c] == nums[d] ，且 a < b < c < d

示例 1：

输入：nums = [1,2,3,6] 输出：1 解释：满足要求的唯一一个四元组是 (0, 1, 2, 3) 因为 1 + 2 + 3 == 6 。 示例 2：

输入：nums = [3,3,6,4,5] 输出：0 解释：[3,3,6,4,5] 中不存在满足要求的四元组。 示例 3：

输入：nums = [1,1,1,3,5] 输出：4 解释：满足要求的 4 个四元组如下： - (0, 1, 2, 3): 1 + 1 + 1 == 3 - (0, 1, 3, 4): 1 + 1 + 3 == 5 - (0, 2, 3, 4): 1 + 1 + 3 == 5 - (1, 2, 3, 4): 1 + 1 + 3 == 5

思路

暴力。

代码

/**
 * @author mikusugar
 */
public class N1 {
    public int countQuadruplets(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    int tar = nums[i] + nums[k] + nums[j];
                    for (int m = nums.length - 1; m > k; m--) {
                        if (tar == nums[m]) res++;
                    }
                }
            }
        }
        return res;
    }
}

题二 游戏中弱角色的数量

描述

你正在参加一个多角色游戏，每个角色都有两个主要属性：攻击 和 防御 。给你一个二维整数数组 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 解释：第三个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。

思路

• 攻击力按大到小排序
• 攻击力相同防御力按小到大排序

这样遍历的同时维护一个最大的防御力，只要最大的防御力比当前的防御力大，当前的角色激素弱角色。

攻击力相同的情况，防御力大的再后面，所以最大防御力大于当前防御力的情况，攻击力一定大于当前攻击力。

代码

/**
 * @author mikusugar
 */
public class N2 {
    public int numberOfWeakCharacters(int[][] properties) {

        Arrays.sort(properties, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return Integer.compare(o1[1], o2[1]);
            }
            return Integer.compare(o2[0], o1[0]);
        });

        int max = -1;
        int res = 0;
        for (int[] p : properties) {
            if (p[1] < max) res++;
            else max = p[1];
        }

        return res;
    }
}

题三 访问完所有房间的第一天

描述

你需要访问 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[i][0] 表示奇数次到达i需要的天数

• dp[i][1] 表示偶数次到达i需要的天数

• 提示里面的0 <= nextVisit[i] <= i很重要，意味着dp[i][0]=(dp[i-1][1]+1)

• 对于偶数次dp[i][1]
• dp[i][0]+1天时位置处于nextVisit[i],也就是dp[nextVisit][0]
• 此时想要到达i需要先偶数次到达i-1, dp[i-1][1]-dp[nextVisit[i]][0]+1
• 加上MOD防止出现负数
• dp[i][1]=(dp[i][0]+1+(MOD+dp[i-1][1]-dp[nextVisit[i]][0]+1))%MOD

这题比赛的期间想到了 通过奇偶来动态规划，可是没有推出公式来，太菜了。。。

代码

/**
 * @author mikusugar
 */
public class N3 {

    private final static int MOD = (int) (1e9+7);
    public int firstDayBeenInAllRooms(int[] nextVisit) {
        //dp[i][0] 表示奇数次到达i需要的天数
        //dp[i][1] 表示偶数次到达i需要的天数
        long[][] dp = new long[nextVisit.length][2];
        dp[0][1] = 1L;
        for (int i=1;i< nextVisit.length;i++){
            dp[i][0]=(dp[i-1][1]+1)%MOD;
            dp[i][1]=(dp[i][0]+1+(MOD+dp[i-1][1]-dp[nextVisit[i]][0]+1))%MOD;
        }
        return (int) dp[dp.length-1][0];
    }

}

题四 数组的最大公因数排序

描述

给你一个整数数组 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]

思路

代码