算法提升——LeetCode122场双周赛总结

周赛通过情况总结

• 本次参加周赛通过2道题目，卡在第3道题目因为解题思路的原因，没能顺利通过所有的数据集。

周赛题目

将数组分成最小总代价的子数组 I

给你一个长度为 n 的整数数组nums
一个数组的代价是它的第一个元素。比方说[1,2,3]的代价是1，[3,4,1]的代价是3。
你需要将nums分成3个连续且没有交集的子数组。
请你返回这些子数组的最小代价总和

• 解题思路
  • 第一个子数组的下标一定是0，所以我们只需要剩下的两个数字的起始下标。因为需要累加和最小，所以实际上我们需要找的是除第一个数字外最小的两个数字。代码如下：

class Solution {
    public int minimumCost(int[] nums) {
        int result=nums[0];
        int idx=-1;
        int midIdx=-1;
        for(int i=1;i<nums.length;i++){
            if (idx==-1||nums[idx]>nums[i]){
                idx=i;
            }
        }
        for(int i=1;i<nums.length;i++){
            if (idx==i){
                continue;
            }
            if (midIdx==-1||nums[midIdx]>nums[i]){
                midIdx=i;
            }
        }
        result+=nums[idx]+nums[midIdx];
        return result;

    }
}

判断一个数组是否可以变为有序

给你一个下标从0开始且全是正整数的数组nums。
一次操作中，如果两个相邻元素在二进制下数位为1的数目相同，那么你可以将这两个元素交换。你可以执行这个操作任意次（也可以0次）。
如果你可以使数组变有序，请你返回 true ，否则返回 false。

• 解题思路：
  • 主要是通过多层循环遍历组的方式解决，代码如下：

class Solution {
    public boolean canSortArray(int[] nums) {
        int n=nums.length;
        int i=0,preMax=0;
        while(i<n){
            int mn=nums[i],mx=mn;
            int ones=Integer.bitCount(mn);
            for(i++;i<n&&Integer.bitCount(nums[i])==ones;i++){
                mn=Math.min(mn,nums[i]);
                mx=Math.max(mx,nums[i]);
            }
            if (mn<preMax){
                return false;
            }
            preMax=mx;
        }
        return true;
    }
}

通过操作使数组长度最小

给你一个下标从0开始的整数数组nums，它只包含正整数。
你的任务是通过进行以下操作任意次（可以是0次）最小化nums的长度：
在nums中选择两个不同的下标i和j，满足nums[i]>0且nums[j]>0。
将结果nums[i]%nums[j]插入nums的结尾。
将nums中下标为i和j的元素删除。
请你返回一个整数，它表示进行任意次操作以后nums的最小长度。

• 解题思路
  • 本题是一道脑筋急转弯题目。解题关键在于找出数组中的最小值。通过使用这个最小值对数组中的所有其他数字进行取余操作，我们可以得到答案。处理时需考虑两种情况：若最小数只出现一次，则答案为1；否则，计算该最小数出现的次数即为所求答案。代码如下：

class Solution {
    public int minimumArrayLength(int[] nums) {
        int m = Integer.MAX_VALUE;
        for (int x : nums) {
            m = Math.min(m, x);
        }

        for (int x : nums) {
            if (x % m > 0) {
                return 1;
            }
        }

        int cnt = 0;
        for (int x : nums) {
            if (x == m) {
                cnt++;
            }
        }
        return (cnt + 1) / 2;
    }
}

将数组分成最小总代价的子数组 II

给你一个下标从0开始长度为n的整数数组nums和两个正整数k和dist。
一个数组的代价是数组中的第一个元素。比方说，[1,2,3]的代价为1，[3,4,1]的代价为3。
你需要将nums分割成k个连续且互不相交的子数组，满足第二个子数组与第k个子数组中第一个元素的下标距离不超过dist。换句话说，如果你将nums分割成子数组nums[0…(i1-1)],nums[i1…(i2-1)],…,nums[ik-1…(n-1)]，那么它需要满足ik-1-i1<=dist。
请你返回这些子数组的最小总代价.

• 解题思路
  • 通过PriorityQueue大顶堆将数组分成多个小数组，外加上懒删除的方法。代码如下：

class Solution {
    int k;
    PriorityQueue<int[]> lower;
    PriorityQueue<int[]> higher;
    int lowerSize;
    int higherSize;
    Set<Integer> lowerSet;
    Set<Integer> higherSet;
    Set<Integer> removeSet;
    long totalCost;

    public long minimumCost(int[] nums, int k, int dist) {
        this.k = k;
        this.lower = new PriorityQueue<int[]>((a, b) -> b[0] - a[0]);
        this.higher = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
        this.lowerSize = 0;
        this.higherSize = 0;
        this.lowerSet = new HashSet<Integer>();
        this.higherSet = new HashSet<Integer>();
        this.removeSet = new HashSet<Integer>();
        this.totalCost = nums[0];
        int n = nums.length;
        for (int i = 1; i <= dist + 1; i++) {
            add(nums[i], i);
        }
        long minCost = totalCost;
        for (int i = dist + 2; i < n; i++) {
            remove(nums[i - dist - 1], i - dist - 1);
            add(nums[i], i);
            minCost = Math.min(minCost, totalCost);
        }
        return minCost;
    }

    public void add(int num, int index) {
        if (lowerSize < k - 1 || num <= lower.peek()[0]) {
            lower.offer(new int[]{num, index});
            lowerSet.add(index);
            lowerSize++;
            totalCost += num;
        } else {
            higher.offer(new int[]{num, index});
            higherSet.add(index);
            higherSize++;
        }
        adjustPriorityQueues();
    }

    public void remove(int num, int index) {
        removeSet.add(index);
        if (lowerSet.contains(index)) {
            lowerSize--;
            totalCost -= num;
        } else {
            higherSize--;
        }
        adjustPriorityQueues();
    }

    public void adjustPriorityQueues() {
        if (lowerSize > k - 1) {
            int[] arr = lower.poll();
            higher.offer(arr);
            lowerSize--;
            higherSize++;
            totalCost -= arr[0];
            lowerSet.remove(arr[1]);
            higherSet.add(arr[1]);
        } else if (lowerSize < k - 1 && higherSize > 0) {
            int[] arr = higher.poll();
            lower.offer(arr);
            lowerSize++;
            higherSize--;
            totalCost += arr[0];
            lowerSet.add(arr[1]);
            higherSet.remove(arr[1]);
        }
        for (PriorityQueue<int[]> pq : Arrays.asList(lower, higher)) {
            while (!pq.isEmpty() && removeSet.contains(pq.peek()[1])) {
                int[] arr = pq.poll();
                removeSet.remove(arr[1]);
            }
        }
    }
}

总结

• 在解决算法问题时，掌握Java基础提供的方法至关重要。例如，在第二题中，虽然我们构建了一个求二进制中1的个数的方法，但实际上Java已经为我们提供了相应的方法。因此，我们应该充分利用这些现有方法来提高解题效率。
• 尽管工作繁忙，仍需加强对LeetCode算法题目的熟练度，并建立自己的知识体系。为了实现这一目标，需要细化年度计划，将LeetCode算法练习具体到每日：工作日专注于解决简单题目以保持题感，而在周末，除了参加每周竞赛外，还需额外完成至少一个中等或困难难度的题目。此外，每周应选择一个特定类型的题目进行集中训练。