双周赛114

双周赛114

本次双周赛没参加，刚好碰上中秋国庆双假期，出去玩了一趟。今天写点博客，把本次周赛的题目研究研究。

T1.收集元素的最少操作次数

1.1 题目说明

给你一个正整数数组 nums 和一个整数 k 。

一次操作中，你可以将数组的最后一个元素删除，将该元素添加到一个集合中。

请你返回收集元素 1, 2, ..., k 需要的 最少操作次数 。

示例 1：

输入：nums = [3,1,5,4,2], k = 2
输出：4
解释：4 次操作后，集合中的元素依次添加了 2 ，4 ，5 和 1 。此时集合中包含元素 1 和 2 ，所以答案为 4 。

提示：

• 1 <= nums.length <= 50

• 1 <= nums[i] <= nums.length

• 1 <= k <= nums.length

• 输入保证你可以收集到元素 1, 2, ..., k 。

  ​

---

1.2 解答分析

• 需要找到最小的操作次数，从后向前遍历数组中的元素即可

• 注意需要记录两部分

  • 遍历过的元素。设置flag进行记录
  • 元素值不超过k的元素，如k==3,则需要记录1,2,3

  ​

---

1.3 具体代码

class Solution {
    public int minOperations(List<Integer> nums, int k) {
        int n=nums.size();
        int[] arr=new int[n];
        int offset=0;
        for(int p :nums){
            arr[offset++]=p;//将num中的每个元素进行遍历记录
        }
        boolean[] isUsed=new boolean[k+1];//判断当前的元素是否被遍历到了，长度是k+1,包含值为k的元素
        int time=0;//判断需要遍历的次数
        for(int i=n-1;i>=0;i--){
            time++;
            if(arr[i]<isUsed.length && !isUsed[arr[i]]){//如果当前的元素没有被遍历过，并且值小于等于k
                isUsed[arr[i]]=true;//标记
                k--;
                if(k==0){//说明已经对k操作完成了
                    return time;//返回需要这样操作的次数
                }
            }
        }
        return -1;//否则返回错误值：-1
    }
}

• 复杂度分析：
  • 时间复杂度： $O(n)$，仅遍历了nums数组，为其长度
  • 空间复杂度：$O(k)$，其中k为给定的参数。主要占用空间的是两个数组：arr和isUsed。数组arr的长度为n，而数组isUsed的长度为k+1。因此，整体空间复杂度可以视为O(k)。

​

---

T2.将数组分割成最多数目的子数组

2.1 题目说明

给你一个只包含 非负 整数的数组 nums 。

我们定义满足 l <= r 的子数组 nums[l..r] 的分数为 nums[l] AND nums[l + 1] AND ... AND nums[r] ，其中 AND 是按位与运算。

请你将数组分割成一个或者更多子数组，满足：

• 每个 元素都 只 属于一个子数组。
• 子数组分数之和尽可能 小 。

请你在满足以上要求的条件下，返回 最多 可以得到多少个子数组。

一个 子数组 是一个数组中一段连续的元素。

​

示例 1：

输入：nums = [1,0,2,0,1,2]
输出：3
解释：我们可以将数组分割成以下子数组：
- [1,0] 。子数组分数为 1 AND 0 = 0 。
- [2,0] 。子数组分数为 2 AND 0 = 0 。
- [1,2] 。子数组分数为 1 AND 2 = 0 。
分数之和为 0 + 0 + 0 = 0 ，是我们可以得到的最小分数之和。
在分数之和为 0 的前提下，最多可以将数组分割成 3 个子数组。所以返回 3 。

示例 2：

输入：nums = [5,7,1,3]
输出：1
解释：我们可以将数组分割成一个子数组：[5,7,1,3] ，分数为 1 ，这是可以得到的最小总分数。
在总分数为 1 的前提下，最多可以将数组分割成 1 个子数组。所以返回 1 。

提示：

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

​

---

2.2 分析解答

• 显然需要利用到贪心算法操作，由于是与的操作，所以一方面是要找到0,另外一方面是需要尽可能地延长子数组的长度，子数组越长，取到AND为0的概率就会越大。

  • 如果整个数组取AND结果不为0，那么返回1 （按照AND的要求，更短的子数组是没办法获取比最后结果更小的结果）。
  • 如果是0，那么从队尾开始遍历数组，寻找到第一个能使得后缀数组取AND为0的位置。
  • 最后从头开始遍历数组，并且贪婪地（AND性质，子数组越长，那么取AND结果是0的可能越大。）寻找最大可能情况。

• 注意需要返回的是子数组的个数

  ​

---

2.3 具体代码

class Solution {
    public int maxSubarrays(int[] nums) {
        int sumAnd=nums[0];
        for(int n:nums){
            sumAnd &=n;//计算全部元素相与的结果
        }
        if(sumAnd!=0){//如果此时全部元素相与都不为0，那么说明此时只能分为1个子数组
            return 1;
        }
        //如果说存在0的情况
        int m=nums.length;
        sumAnd=nums[m-1];//sumAnd为最后一个元素值
        int LastZero=m-1;//最后一个元素的位置
        for(int i=m-1;i>=0;i--){
            sumAnd&=nums[i];
            if(sumAnd==0){
                LastZero=i;//更新，找到最后的0的位置
                break;
            }
        }
        //从数组头元素重新开始
        sumAnd=nums[0];
        int res=0;
        for(int i=0;i<nums.length;i++){//注意需要讨论最后一个元素，每次循环都要将当前元素与sumAnd进行按位与操作。
            sumAnd&=nums[i];
            if(sumAnd==0){
                res++;
                if(i+1<=LastZero){//此时i不大于LastZero前一个位置时，继续更新sumAnd
                    sumAnd=nums[i+1];
                }else{
                    break;
                }
            }
        }
        return res;
    }
}

• 复杂度分析：

  • 时间复杂度：$O(n)$，都是遍历数组，进行循环的操作，自然是数组的长度n。

  • 空间复杂度：$O(1)$，并没有引入额外的存储空间。

    ​

---

T3. 使数组为空的最少操作次数

3.1 题目说明

给你一个下标从 0 开始的正整数数组 nums 。

你可以对数组执行以下两种操作 任意次 ：

• 从数组中选择 两个 值 相等 的元素，并将它们从数组中 删除 。
• 从数组中选择 三个 值 相等 的元素，并将它们从数组中 删除 。

请你返回使数组为空的 最少 操作次数，如果无法达成，请返回 -1 。

示例 1：

输入：nums = [2,3,3,2,2,4,2,3,4]
输出：4
解释：我们可以执行以下操作使数组为空：
- 对下标为 0 和 3 的元素执行第一种操作，得到 nums = [3,3,2,4,2,3,4] 。
- 对下标为 2 和 4 的元素执行第一种操作，得到 nums = [3,3,4,3,4] 。
- 对下标为 0 ，1 和 3 的元素执行第二种操作，得到 nums = [4,4] 。
- 对下标为 0 和 1 的元素执行第一种操作，得到 nums = [] 。
至少需要 4 步操作使数组为空。

示例 2：

输入：nums = [2,1,2,2,3,3]
输出：-1
解释：无法使数组为空。

提示：

• 2 <= nums.length <= 105

• 1 <= nums[i] <= 106

  ​

---

3.2 分析解答

• 想法是先统计每个元素的值出现的次数，此时需要用到的是HashMap的数据结构。

• 再通过遍历每个元素值出现的次数进行讨论，如果为1则直接返回-1，如果不是1，根据贪心思想，最后求出结果。（从3开始，2即可）

  ​

---

3.3 具体代码

class Solution {
    public int minOperations(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int ans = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {//返回一个Set集合，其中包含了Map中所有的键值对。每个键值对都是一个Map.Entry对象
            int num = entry.getValue();//可以获取到该值
            if (num == 1) {//出现1次
                return -1;
            } else {
                while (num % 3 != 0) {
                    num -= 2;
                    ans++;
                }
                ans += num / 3;
            }
        }
        return ans;
    }
}

• 复杂度分析：

  • 时间复杂度： $O(m+n)$

    1. 遍历nums数组并构建HashMap：O(n)，其中n为数组的长度。
    2. 遍历map.entrySet()，即遍历map中的键值对：O(m)，其中m为map中不同元素的个数，最坏情况下为n（每个元素都不同）。
    3. 在循环体内执行一些常数时间的操作，包括判断、减法、除法等：O(1)。
    4. 总体时间复杂度为O(n + m)。

  • 空间复杂度：$O(n)$

    1. 使用了一个HashMap存储元素出现次数：最坏情况下空间复杂度为O(n)，即所有元素都不同。
    2. 使用了常数级别的额外空间：O(1)。
    3. 总体空间复杂度为O(n)。

    ​

---

T4. 可以被 K 整除连通块的最大数目

4.1 题目说明

给你一棵 n 个节点的无向树，节点编号为 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 有一条边。

同时给你一个下标从 0 开始长度为 n 的整数数组 values ，其中 values[i] 是第 i 个节点的 值 。再给你一个整数 k 。

你可以从树中删除一些边，也可以一条边也不删，得到若干连通块。一个 连通块的值 定义为连通块中所有节点值之和。如果所有连通块的值都可以被 k 整除，那么我们说这是一个 合法分割 。

请你返回所有合法分割中，连通块数目的最大值 。

示例 1：

输入：n = 5, edges = [[0,2],[1,2],[1,3],[2,4]], values = [1,8,1,4,4], k = 6
输出：2
解释：我们删除节点 1 和 2 之间的边。这是一个合法分割，因为：
- 节点 1 和 3 所在连通块的值为 values[1] + values[3] = 12 。
- 节点 0 ，2 和 4 所在连通块的值为 values[0] + values[2] + values[4] = 6 。
最多可以得到 2 个连通块的合法分割。

​

---

4.2 解答分析

• 我们其实需要寻找的是一些边，去除这些边之后，分裂的左右两侧子树仍然被k整除。

  • n：表示树的大小；
  • _edges：表示树中的边，其中_edges[i] = [u, v]表示树中存在一条连接u和v的边；
  • values：一个长度为n的数组，values[i]表示第i个节点的整数值；
  • k：一个整数，表示需要被整除的值。

  ​

---

4.3 具体代码

class Solution {
    private List<Integer>[] edges;
    private int[] values;
    private int k;

    public int maxKDivisibleComponents(int n, int[][] _edges, int[] values, int k) {
        edges = new List[n];
        for (int i = 0; i < n; ++i) {
            edges[i] = new ArrayList<>();
        }
        for (int[] e : _edges) {
            edges[e[0]].add(e[1]);
            edges[e[1]].add(e[0]);
        }

        this.values = values;
        this.k = k;
        int[] res = {0};
        dfs(0, -1, res);
        return res[0];
    }
	
    //该函数的实现使用了DFS搜索，定义了一个辅助函数dfs，dfs(cur, pre, res)表示在以cur为根节点、pre为cur的父节点时，子树中所有节点值之和对k取余数的结果。在dfs遍历时，若当前节点的值可以和子树中某个节点值之和整除k，则累加答案res[0]。
    private int dfs(int cur, int pre, int[] res) {
        int sum = values[cur] % k;
        for (int n : edges[cur]) {
            if (n != pre) {
                sum = (sum + dfs(n, cur, res)) % k;
            }
        }
        if (sum == 0) {
            res[0] += 1;
        }
        return sum;
    }
}

• 复杂度分析：

  • 时间复杂度： $O(n)$，其中n为树的大小

  • 空间复杂度：$O(n)$，我们需要存储整棵树的边和每个节点的值

    ​

后续需要继续加强算法思想的体会。当前的主要任务还是把常见的算法都多熟悉，如dfs、bfs、dp、贪心等，这些都是解题思路的关键。

加油！奥力给😘~