每日算法-250506

每日算法学习记录 - 250506

今天记录了三道算法题的解题过程和思路，分享给大家。

3192. 使二进制数组全部等于 1 的最少操作次数 II

题目

思路

贪心

解题过程

我们从左到右遍历数组。使用一个变量 ret 来记录已经执行的操作次数。
对于当前元素 nums[i]，它的实际值会受到其左边（即索引小于 i 的位置）操作的影响。

• 如果 ret 是偶数，那么 nums[i] 的实际值就是它本身 nums[i]。
• 如果 ret 是奇数，那么 nums[i] 的实际值被翻转了 (0 变为 1, 1 变为 0)，即 1 - nums[i]。

我们的目标是让 nums[i] 在考虑了之前 ret 次操作影响后的实际状态为 1。
如果 nums[i] 的当前实际状态是 0，我们就必须在 i 位置执行一次操作。这次操作会翻转从 nums[i] 到数组末尾的所有元素，从而确保 nums[i] 变为 1。同时，我们增加 ret 的计数。

判断逻辑可以总结为：

• 目标状态：1
• 当前原始值：nums[i]
• 已有翻转次数：ret
• nums[i] 受已有翻转影响后的状态：current_val = (nums[i] + ret) % 2 （或者理解为：如果 ret 是偶数，current_val = nums[i]；如果 ret 是奇数，current_val = 1 - nums[i]）。
• 如果 current_val 是 0，我们就需要执行一次操作，ret++。

代码中的 if (x == flag)，其中 x 是 nums[i]，flag 是 ret % 2：

• 如果 nums[i] == 0 且 ret % 2 == 0 (偶数次翻转，nums[i] 实际是 0)，则需要翻转，ret++。
• 如果 nums[i] == 1 且 ret % 2 == 1 (奇数次翻转，nums[i] 实际是 0)，则需要翻转，ret++。
  这两种情况恰好是 nums[i] == ret % 2。

复杂度

• 时间复杂度: $O(N)$
• 空间复杂度: $O(1)$

Code

class Solution {
    public int minOperations(int[] nums) {
        int ret = 0;
        for (int x : nums) {
            int flag = ret % 2;
            if (x == flag) {
                ret++;
            }
        }
        return ret;
    }
}

2789. 合并后数组中的最大元素

题目

思路

贪心

解题过程

这道题的关键在于从右往左遍历数组。我们维护 curSum 表示从当前位置向右合并能得到的元素值（即当前正在构建的合并块的总和），同时用 maxVal 记录遍历过程中出现过的最大的 curSum（即最大的可能合并块）。

1. 从数组的最后一个元素 nums[n-1] 开始：
   • curSum 初始化为 nums[n-1]。
   • maxVal 初始化为 nums[n-1]。
2. 然后从 nums[n-2] 向左遍历到 nums[0]：
   • 对于当前元素 nums[i]：
     • 如果 nums[i] <= curSum：说明 nums[i] 可以和右边的 curSum 代表的合并块进行合并（满足 nums[i] <= nums[i+1] 的条件，其中 nums[i+1] 实际上是 curSum）。我们将 nums[i] 加到 curSum 上，即 curSum += nums[i]。
     • 如果 nums[i] > curSum：说明 nums[i] 不能和右边的 curSum 合并，因为它比右边已经合并的块还要大。此时，nums[i] 成为一个新的、独立的合并块的起点（或者说它本身就是一个块），所以 curSum 被重置为 nums[i]。
   • 每次更新 curSum 后，都用 maxVal = Math.max(maxVal, curSum) 来更新全局记录的最大合并块值。
3. 遍历结束后，maxVal 就是数组中能合并出的最大元素。

复杂度

• 时间复杂度: $O(N)$
• 空间复杂度: $O(1)$

Code

class Solution {
    public long maxArrayValue(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        long curSum = nums[n - 1];
        long maxVal = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] <= curSum) {
                curSum += nums[i];
            } else {
                curSum = nums[i];
            }
            maxVal = Math.max(maxVal, curSum);
        }
        return maxVal;
    }
}

153. 寻找旋转排序数组中的最小值（复习）

题目

这是第二次写这道题了，写的还不错，基本上已经掌握了，就不再多说了。
详细题解见每日算法-250415

Code

class Solution {
    public int findMin(int[] nums) {
        int left = 0, rigth = nums.length - 1;
        int k = nums[rigth];
        while (left <= rigth) {
            int mid = left + (rigth - left) / 2;
            if (nums[mid] < k) {
                rigth = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left >= nums.length ? nums[rigth] : nums[left];
    }
}