力扣每日一题

该文档仅仅自用，无记录的日期原因随意^^

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

时间：2025/1/15

使用数据结构：优先队列

此题模拟即可，但要熟练掌握优先队列的使用，同时需要注意到数据范围，$1 <= nums[i] <= 10^9$，使用long接收参数。

class Solution {
    public int minOperations(int[] nums, int k) {
        int ans = 0;
        PriorityQueue<Long> pq = new PriorityQueue<>();
        for(long num : nums){
            pq.offer(num);
        }

        while(pq.peek() < k){
            long x = pq.poll(), y = pq.poll();
            pq.offer(x + x + y);
            ans++;
        }
        return ans;
    }
}

3095. 或值至少 K 的最短子数组 I

时间：2025/1/16

枚举以i为起始位置的子数组，找到最短的符合要求的长度。

class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int ans = Integer.MAX_VALUE;
        for(int i = 0; i < nums.length; i++){
            int cur = 0;
            for(int j = i; j < nums.length; j++){
                cur |= nums[j];
                if(cur >= k){
                    ans = Math.min(ans, j - i + 1);
                    break;
                }
            }
        }

        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

或者可以使用滑动窗口

class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int n = nums.length;
        int[] bits = new int[30];
        int res = Integer.MAX_VALUE;
        for (int left = 0, right = 0; right < n; right++) {
            for (int i = 0; i < 30; i++) {
                bits[i] += (nums[right] >> i) & 1;
            }
            while (left <= right && calc(bits) >= k) {
                res = Math.min(res, right - left + 1);
                for (int i = 0; i < 30; i++) {
                    bits[i] -= (nums[left] >> i) & 1;
                }
                left++;
            }
        }

        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private int calc(int[] bits) {
        int ans = 0;
        for (int i = 0; i < bits.length; i++) {
            if (bits[i] > 0) {
                ans |= 1 << i;
            }
        }
        return ans;
    }
}

3097. 或值至少为 K 的最短子数组 II

时间：2025/1/17

思路同上一道题

class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int n = nums.length;
        int[] bits = new int[30];
        int res = Integer.MAX_VALUE;
        for (int left = 0, right = 0; right < n; right++) {
            for (int i = 0; i < 30; i++) {
                bits[i] += (nums[right] >> i) & 1;
            }
            while (left <= right && calc(bits) >= k) {
                res = Math.min(res, right - left + 1);
                for (int i = 0; i < 30; i++) {
                    bits[i] -= (nums[left] >> i) & 1;
                }
                left++;
            }
        }

        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private int calc(int[] bits) {
        int ans = 0;
        for (int i = 0; i < bits.length; i++) {
            if (bits[i] > 0) {
                ans |= 1 << i;
            }
        }
        return ans;
    }
}

2239. 找到最接近 0 的数字

时间：2025/1/20

笨蛋办法，依题意遍历

但效率较差，官解大同小异，将距0的距离也记录下来。时间上有所改进。

class Solution {
    public int findClosestNumber(int[] nums) {
        int ans = nums[0];
        for(int i = 1; i < nums.length; i++){
            if (Math.abs(ans) > Math.abs(nums[i])){
                ans = nums[i];
            } else if(Math.abs(ans) == Math.abs(nums[i])){
                ans = Math.max(ans, nums[i]);
            }
        }
        return ans;
    }
}

2218. 从栈中取出 K 个硬币的最大面值和

时间：2025/1/21

前缀和、背包问题、动态规划

状态定义：f[i] 表示选择了 i 个硬币时，能得到的最大价值。

转移方程：对于每个堆，我们尝试从该堆中取出不同数量的硬币（最多取堆中所有硬币）。对于每个堆中的硬币数量 t，如果当前的选择可以满足 i 个硬币（即 i >= t），就尝试更新 f[i] 的值。

优化思路：每个堆中的硬币取出顺序是逐步累加的，依次计算从堆中取出 1、2、3...个硬币的总价值。

class Solution {
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int[] f = new int[k + 1];
        Arrays.fill(f, -1);
        f[0] = 0;
        for (List<Integer> pile : piles) {
            for (int i = k; i > 0; --i) {
                int value = 0;
                for (int t = 1; t <= pile.size(); ++t) {
                    value += pile.get(t - 1);
                    if (i >= t && f[i - t] != -1) {
                        f[i] = Math.max(f[i], f[i - t] + value);
                    }
                }
            }
        }
        return f[k];
    }
}

1561. 你可以获得的最大硬币数目

时间：2025/1/22

博弈论、贪心

$3n$堆硬币，每轮由我选出3堆且拿走其中第二多的一个，也就是说我们直接每次最小的一堆选最小值交给bob即可，剩下的，每次可以取最大的两堆，我拿稍小的一个。

class Solution {
    public int maxCoins(int[] piles) {
        Arrays.sort(piles);
        int n = piles.length / 3;
        int ans = 0;
        for(int i = 0; i < n; i++){
            ans += piles[3 * n - i * 2 - 2];
        }
        return ans;
    }
}