周赛 Leetcode

力扣125场双周赛

1、3065. 超过阈值的最少操作数 I

3065. 超过阈值的最少操作数 I - 力扣（LeetCode）

//给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 // // 一次操作中，你可以删除 nums 中的最小元素。 // // 你需要使数组中的所有元素都大于或等于 k ，请你返回需要的 最少 操作次数。 // // // // 示例 1： // // //输入：nums = [2,11,10,1,3], k = 10 //输出：3 //解释：第一次操作后，nums 变为 [2, 11, 10, 3] 。 //第二次操作后，nums 变为 [11, 10, 3] 。 //第三次操作后，nums 变为 [11, 10] 。 //此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。 //使数组中所有元素都大于等于 10 需要的最少操作次数为 3 。 // // // 示例 2： // // //输入：nums = [1,1,2,4,9], k = 1 //输出：0 //解释：数组中的所有元素都大于等于 1 ，所以不需要对 nums 做任何操作。 // // 示例 3： // // //输入：nums = [1,1,2,4,9], k = 9 //输出：4 //解释：nums 中只有一个元素大于等于 9 ，所以需要执行 4 次操作。 // // // // // 提示： // // // 1 <= nums.length <= 50 // 1 <= nums[i] <= 10⁹ // 1 <= k <= 10⁹ // 输入保证至少有一个满足 nums[i] >= k 的下标 i 存在。 // // // Related Topics 数组 👍 1 👎 0

就是统计数组中小于k的数有多少

1
2
3
4
5
6
7
8
9

class Solution {
    public int minOperations(int[] nums, int k) {
        int res=0;
        for(int num:nums){
            if(num<k) res++;
        }
        return res;
    }
}

2、3066. 超过阈值的最少操作数 II

//给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 // // 一次操作中，你将执行： // // // 选择 nums 中最小的两个整数 x 和 y 。 // 将 x 和 y 从 nums 中删除。 // 将 min(x, y) * 2 + max(x, y) 添加到数组中的任意位置。 // // // 注意，只有当 nums 至少包含两个元素时，你才可以执行以上操作。 // // 你需要使数组中的所有元素都大于或等于 k ，请你返回需要的 最少 操作次数。 // // // // 示例 1： // // //输入：nums = [2,11,10,1,3], k = 10 //输出：2 //解释：第一次操作中，我们删除元素 1 和 2 ，然后添加 1 * 2 + 2 到 nums 中，nums 变为 [4, 11, 10, 3] 。 //第二次操作中，我们删除元素 3 和 4 ，然后添加 3 * 2 + 4 到 nums 中，nums 变为 [10, 11, 10] 。 //此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。 //使数组中所有元素都大于等于 10 需要的最少操作次数为 2 。 // // // 示例 2： // // //输入：nums = [1,1,2,4,9], k = 20 //输出：4 //解释：第一次操作后，nums 变为 [2, 4, 9, 3] 。 //第二次操作后，nums 变为 [7, 4, 9] 。 //第三次操作后，nums 变为 [15, 9] 。 //第四次操作后，nums 变为 [33] 。 //此时，数组中的所有元素都大于等于 20 ，所以我们停止操作。 //使数组中所有元素都大于等于 20 需要的最少操作次数为 4 。 // // // // 提示： // // // 2 <= nums.length <= 2 * 10⁵ // 1 <= nums[i] <= 10⁹ // 1 <= k <= 10⁹ // 输入保证答案一定存在，也就是说一定存在一个操作序列使数组中所有元素都大于等于 k 。 // // // Related Topics 数组 模拟 堆（优先队列） 👍 2 👎 0

题目说一定可以操作，表示不会存在只剩下一个小于k的元素的情况，优先队列就可以

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int minOperations(int[] nums, int k) {
        int res=0;
        PriorityQueue<Long> priorityQueue=new PriorityQueue<>();
        for(int num:nums){
            priorityQueue.offer((long) num);
        }
        while(!priorityQueue.isEmpty()&&priorityQueue.peek()<k){
            long a=priorityQueue.poll();
            long b=priorityQueue.poll();
            long t=a*2+b;
            priorityQueue.offer(t);
            res++;
        }
        return res;
    }
}

3、3067. 在带权树网络中统计可连接服务器对数目

//给你一棵无根带权树，树中总共有 n 个节点，分别表示 n 个服务器，服务器从 0 到 n - 1 编号。同时给你一个数组 edges ，其中 edges[ //i] = [ai, bi, weighti] 表示节点 ai 和 bi 之间有一条双向边，边的权值为 weighti 。再给你一个整数 signalSpeed 。 // // // 如果两个服务器 a ，b 和 c 满足以下条件，那么我们称服务器 a 和 b 是通过服务器 c 可连接的 ： // // // a < b ，a != c 且 b != c 。 // 从 c 到 a 的距离是可以被 signalSpeed 整除的。 // 从 c 到 b 的距离是可以被 signalSpeed 整除的。 // 从 c 到 b 的路径与从 c 到 a 的路径没有任何公共边。 // // // 请你返回一个长度为 n 的整数数组 count ，其中 count[i] 表示通过服务器 i 可连接 的服务器对的 数目 。 // // // // 示例 1： // // // // //输入：edges = [[0,1,1],[1,2,5],[2,3,13],[3,4,9],[4,5,2]], signalSpeed = 1 //输出：[0,4,6,6,4,0] //解释：由于 signalSpeed 等于 1 ，count[c] 等于所有从 c 开始且没有公共边的路径对数目。 //在输入图中，count[c] 等于服务器 c 左边服务器数目乘以右边服务器数目。 // // // 示例 2： // // // // //输入：edges = [[0,6,3],[6,5,3],[0,3,1],[3,2,7],[3,1,6],[3,4,2]], signalSpeed = 3 //输出：[2,0,0,0,0,0,2] //解释：通过服务器 0 ，有 2 个可连接服务器对(4, 5) 和 (4, 6) 。 //通过服务器 6 ，有 2 个可连接服务器对 (4, 5) 和 (0, 5) 。 //所有服务器对都必须通过服务器 0 或 6 才可连接，所以其他服务器对应的可连接服务器对数目都为 0 。 // // // // // 提示： // // // 2 <= n <= 1000 // edges.length == n - 1 // edges[i].length == 3 // 0 <= ai, bi < n // edges[i] = [ai, bi, weighti] // // 1 <= weighti <= 10⁶ // 1 <= signalSpeed <= 10⁶ // 输入保证 edges 构成一棵合法的树。 // // // Related Topics 树 深度优先搜索 数组 👍 5 👎 0

抄的茶神的解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

class Solution {
    public int[] countPairsOfConnectableServers(int[][] edges, int signalSpeed) {
//        一共有n个点
        int n = edges.length + 1;
//        每个点分别可以到哪个点
        List<int[]>[] g = new ArrayList[n];
//        初始化
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0];
            int y = e[1];
            int wt = e[2];
            g[x].add(new int[]{y, wt});
            g[y].add(new int[]{x, wt});
        }

//        返回的答案
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
//            每个点的和
            int sum = 0;
            for (int[] e : g[i]) {
//               从i点触发，向e方向走有多少个满足条件的点
                int cnt = dfs(e[0], i, e[1], g, signalSpeed);
//                到目前方向为止一共有多少满足条件的点等于=当前方向满足条件的点*之前扫描过的所有方向的和
                ans[i] += cnt * sum;
//                上面一行更新答案，下面一行记录当前所有方向的和
                sum += cnt;
            }
        }
        return ans;
    }

    /**
     *
     * @param x 要到达的点
     * @param fa   起点
     * @param sum 从起点走到这里一共耗时多少
     * @param g
     * @param signalSpeed
     * @return
     */
    private int dfs(int x, int fa, int sum, List<int[]>[] g, int signalSpeed) {
//        如果当前累计的耗时满足条件，当前点记1，否则当前点记0
        int cnt = sum % signalSpeed == 0 ? 1 : 0;
        for (int[] e : g[x]) {
            int y = e[0];
//            避免出现向回走的情况
            if (y != fa) {
//                现在计算当前点又有多少满足条件的情况
                cnt += dfs(y, x, sum + e[1], g, signalSpeed);
            }
        }
        return cnt;
    }
}

4、3068. 最大节点价值之和

//给你一棵 n 个节点的 无向 树，节点从 0 到 n - 1 编号。树以长度为 n - 1 下标从 0 开始的二维整数数组 edges 的形式给你，其中 //edges[i] = [ui, vi] 表示树中节点 ui 和 vi 之间有一条边。同时给你一个 正 整数 k 和一个长度为 n 下标从 0 开始的 非负 整数数 //组 nums ，其中 nums[i] 表示节点 i 的 价值 。 // // 日增哥哥想 最大化 树中所有节点价值之和。为了实现这一目标，日增哥哥可以执行以下操作 任意 次（包括 0 次）： // // // 选择连接节点 u 和 v 的边 [u, v] ，并将它们的值更新为： // // // // nums[u] = nums[u] XOR k // nums[v] = nums[v] XOR k // // // // // 请你返回日增哥哥通过执行以上操作 任意次 后，可以得到所有节点 价值之和 的 最大值 。 // // // // 示例 1： // // // // //输入：nums = [1,2,1], k = 3, edges = [[0,1],[0,2]] //输出：6 //解释：日增哥哥可以通过一次操作得到最大价值和 6 ： //- 选择边 [0,2] 。nums[0] 和 nums[2] 都变为：1 XOR 3 = 2 ，数组 nums 变为：[1,2,1] -> [2,2,2] //。 //所有节点价值之和为 2 + 2 + 2 = 6 。 //6 是可以得到最大的价值之和。 // // // 示例 2： // // // // //输入：nums = [2,3], k = 7, edges = [[0,1]] //输出：9 //解释：日增哥哥可以通过一次操作得到最大和 9 ： //- 选择边 [0,1] 。nums[0] 变为：2 XOR 7 = 5 ，nums[1] 变为：3 XOR 7 = 4 ，数组 nums 变为：[2,3] //-> [5,4] 。 //所有节点价值之和为 5 + 4 = 9 。 //9 是可以得到最大的价值之和。 // // // 示例 3： // // // // //输入：nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]] //输出：42 //解释：日增哥哥不需要执行任何操作，就可以得到最大价值之和 42 。 // // // // // 提示： // // // 2 <= n == nums.length <= 2 * 10⁴ // 1 <= k <= 10⁹ // 0 <= nums[i] <= 10⁹ // edges.length == n - 1 // edges[i].length == 2 // 0 <= edges[i][0], edges[i][1] <= n - 1 // 输入保证 edges 构成一棵合法的树。 // // // Related Topics 贪心 位运算 树 数组 动态规划 排序 👍 14 👎 0

抄的茶神的解法，后面更新思路

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public long maximumValueSum(int[] nums, int k, int[][] edges) {
        int n = nums.length;
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0];
            int y = e[1];
            g[x].add(y);
            g[y].add(x);
        }
        return dfs(0, -1, g, nums, k)[0];
    }

    private long[] dfs(int x, int fa, List<Integer>[] g, int[] nums, int k) {
        long f0 = 0, f1 = Long.MIN_VALUE; // f[x][0] 和 f[x][1]
        for (int y : g[x]) {
            if (y != fa) {
                long[] r = dfs(y, x, g, nums, k);
                long t = Math.max(f1 + r[0], f0 + r[1]);
                f0 = Math.max(f0 + r[0], f1 + r[1]);
                f1 = t;
            }
        }
        return new long[]{Math.max(f0 + nums[x], f1 + (nums[x] ^ k)),
                Math.max(f1 + nums[x], f0 + (nums[x] ^ k))};
    }
}
comments powered by Disqus
© 2020 - 2025 韩永发的博客
使用 Hugo 构建
主题 Stack 由 Jimmy 设计