9-周赛335总结-阿里云开发者社区

9-周赛335总结

其实没有很难，都有思路，卡在了写代码上。最后有点贪心，第三题做做超时了，然后去做第四题，然后又去做第三题，最后越做越紧张，都没做出来。第四题今天花了十几分钟做出来了，第三题还是超时，没有想到优化方法，，但是前两题就花了十分钟，棒棒的，继续努力。下周早起来实验室做了，肯定是宿舍风水不好，影响我发挥。

递枕头【LC2582】

n 个人站成一排，按从 1 到 n 编号。

最初，排在队首的第一个人拿着一个枕头。每秒钟，拿着枕头的人会将枕头传递给队伍中的下一个人。一旦枕头到达队首或队尾，传递方向就会改变，队伍会继续沿相反方向传递枕头。

例如，当枕头到达第 n 个人时，TA 会将枕头传递给第 n - 1 个人，然后传递给第 n - 2 个人，依此类推。

给你两个正整数 n 和 time ，返回 time 秒后拿着枕头的人的编号。

class Solution {
    public int passThePillow(int n, int time) {
        int c = time / (n - 1);// 轮回次数 偶 1->2 奇数n-> n-1 -> n -2
        int left = time % (n - 1);
        return c % 2 == 0 ? 1 + left : n - left;
    }
}

二叉树中的第 K 大层和【LC2583】

思路：BFS+优先队列
要求第K大的层的和，因此可以使用BFS求每层的和，然后使用小顶堆找到第K大层的和
实现
返回值是long！！

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public long kthLargestLevelSum(TreeNode root, int k) {
        // BFS + 小顶堆
        Deque<TreeNode> queue = new LinkedList<>();
        PriorityQueue<Long> pq = new PriorityQueue<>();
        queue.addLast(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            long sum = 0L;
            for (int i = 0; i < size; i++){
                TreeNode node = queue.pollFirst();
                sum += node.val;
                if (node.left != null){
                    queue.addLast(node.left);
                }
                if (node.right != null){
                    queue.addLast(node.right);
                }
            }
            if (pq.size() < k){
                pq.add(sum);
            }else if (sum > pq.peek()){
                pq.poll();
                pq.add(sum);
            }
        }
        return pq.size() == k ? pq.peek() : -1;
    }
}

分割数组使乘积互质【LC2584】

给你一个长度为 n 的整数数组 nums ，下标从 0 开始。

如果在下标 i 处分割数组，其中 0 <= i <= n - 2 ，使前 i + 1 个元素的乘积和剩余元素的乘积互质，则认为该分割有效。

例如，如果 nums = [2, 3, 3] ，那么在下标 i = 0 处的分割有效，因为 2 和 9 互质，而在下标 i = 1 处的分割无效，因为 6 和 3 不互质。在下标 i = 2 处的分割也无效，因

为 i == n - 1 。

返回可以有效分割数组的最小下标 i ，如果不存在有效分割，则返回 -1 。

当且仅当 gcd(val1, val2) == 1 成立时，val1 和 val2 这两个值才是互质的，其中 gcd(val1, val2) 表示 val1 和 val2 的最大公约数。

思路【超时】

如果能够在下标 i 处分割数组，那么左边的所有元素和右边的所有元素的最大公约数为1，两个最大公约数不为1的元素必须在同一组
因此可以使用数组idx记录每个元素nums[i]在nums[i,n-1]中最右边的最大公约数不为1的元素位置，即为对于nums[i]而言，分割线需要位于的最小位置

然后遍历idx，使用max记录目前最大的分割线，如果max与i相等，那么该分割线是最小分割线

实现

class Solution {
    public int findValidSplit(int[] nums) {
        int n = nums.length;
        if (gcd(nums[0], nums[n - 1]) != 1) return -1;
        int[] idx = new int[n];
        for (int i = 0; i < n; i++){
            for (int j = n - 1; j >= i; j--){
                if (gcd(nums[i], nums[j]) != 1){
                    idx[i] = j;
                    break;
                }
            }
        }
        int max = idx[0];
        for (int i = 0; i <= n - 2; i++){
            max = Math.max(max, idx[i]);
            if (i == max){
                return i;
            }
        }
        return -1;
    }
    public int gcd (int x, int y){
        return y == 0 ? x : gcd(y, x % y);
    }
}

优化

其实我们可以不求取的idx数组，如果前面元素的最右边界为max，那么下一个元素为和nums[max,n-1]的最大公约数为1即可，不需要求它的分割线，如果它的分割线是其自身，max远大于i时，就做了无用
因此可以使用双指针，使用right记录当前的最远右边界，

然后枚举每个左端点left，查看是否有更远的分割线，直至左端点大于右端点时退出循环，right即为答案
如果right大于n-2，那么不存在有效分割，返回-1

实现

class Solution {
    public int findValidSplit(int[] nums) {
        int n = nums.length;
        int left = 0, right = 0;
        while (left <= right){
            for (int i = right + 1; i < n; i++){
                if (gcd(nums[i], nums[left]) != 1){
                    right = i;
                }
            }
            left++;
        }
        return right <= n - 2 ? right : -1;
    }
    public int gcd (int x, int y){
        return y == 0 ? x : gcd(y, x % y);
    }
}

获得分数的方法数【LC2585】

考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ，其中 types[i] = [counti, marksi] 表示第 i 种类型的题目有counti 道，每道题目对应 marksi 分。

返回你在考试中恰好得到 target 分的方法数。由于答案可能很大，结果需要对 109 +7 取余。

注意，同类型题目无法区分。

比如说，如果有 3 道同类型题目，那么解答第 1 和第 2 道题目与解答第 1 和第 3 道题目或者第 2 和第 3 道题目是相同的。

思路：

将题意转化为不能重复的x数之和，使用哈希表记录小于等于target的分数的方法数，重点在如何避免重复情况：使用额外哈希表记录该类型的题目对整体结果的贡献

，统计完毕后，再记录到整体的哈希表中
实现

class Solution {
    public int waysToReachTarget(int target, int[][] types) {
        int[] count = new int[target + 1];
        int MOD = (int)(1e9 + 7);
        count[0] = 1;
        for (int[] type :types){
            int num = type[0], mark = type[1];
            int[] tmp = new int[target + 1];
            for (int i = 1; i <= num; i++){
                int s = i * mark;
                if (s > target) break;
                for (int j = 0; j <= target - s; j++){
                    if (count[j] == 0) continue;
                    tmp[j + s] = (tmp[j + s] + count[j]) % MOD; 
                }
            }
            for (int i = 0; i <= target; i++){
                count[i] = (count[i] + tmp[i]) % MOD;
            }
        }
        return count[target];
    }
}

复杂度

时间复杂度：O(n∗C)

空间复杂度：O(C)

分组背包

倒序处理

原来是分组背包啊，没看出来hhh，还是不够熟练

class Solution {
    private static final int MOD = (int) 1e9 + 7;
    public int waysToReachTarget(int target, int[][] types) {
        var f = new int[target + 1];
        f[0] = 1;
        for (var p : types) {
            int count = p[0], marks = p[1];
            for (int j = target; j > 0; --j)
                for (int k = 1; k <= count && k <= j / marks; ++k)
                    f[j] = (f[j] + f[j - k * marks]) % MOD;
        }
        return f[target];
    }
}
作者：灵茶山艾府
链接：https://leetcode.cn/problems/number-of-ways-to-earn-points/solutions/2148313/fen-zu-bei-bao-pythonjavacgo-by-endlessc-ludl/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

9-周赛335总结