每日算法-250328

记录今天学习和解决的LeetCode算法题。

---

92. 反转链表 II

题目

思路

本题要求反转链表中从 left 到 right 位置的节点。我们可以采用 头插法 的思路来反转指定区间的链表。

具体来说，我们首先定位到 left 位置节点的前一个节点 prev。然后，从 left 位置开始，依次将 left + 1 到 right 位置的节点移动到 prev 节点的后面，也就是反转区间的“头部”。

解题过程

1. 虚拟头节点 (Dummy Node): 为了方便处理 left = 1 的情况（即反转从头节点开始），我们创建一个虚拟头节点 dummy，并让 dummy.next 指向原始链表的头节点 head。最终返回结果时返回 dummy.next。

2. 定位 prev 节点: 我们需要找到反转区间的前一个节点，记为 prev。通过一个循环，将 prev 指针从 dummy 开始向后移动 left - 1 步，使其指向第 left - 1 个节点。

3. 定位 cur 节点: cur 指针初始化为 prev.next，即反转区间的第一个节点（第 left 个节点）。

4. 执行反转 (头插法): 进行 right - left 次操作。在每次操作中：

   • 记录 cur 的下一个节点，记为 curNext。这curNext 就是本次需要移动到反转区间头部的节点。
   • 让 cur 的 next 指针指向 curNext 的下一个节点，即将 curNext 从链表中暂时断开。 (cur.next = curNext.next;)
   • 将 curNext 插入到 prev 节点的后面：让 curNext 的 next 指针指向当前反转区间的第一个节点 (prev.next)。 (curNext.next = prev.next;)
   • 更新 prev 的 next 指针，使其指向新插入的 curNext，这样 curNext 就成为了新的反转区间的第一个节点。 (prev.next = curNext;)
   • 注意：在这个过程中，cur 指针始终指向原来的第 left 个节点，它在反转后会成为反转区间的最后一个节点。 prev 指针始终不变，指向反转区间的前一个节点。

5. 返回结果: 所有操作完成后，dummy.next 指向的就是新链表的头节点，返回 dummy.next。

复杂度

• 时间复杂度: $O(n)$，其中 $n$ 是链表的长度。需要遍历链表找到 prev 节点，然后进行 right - left 次节点移动操作。
• 空间复杂度: $O(1)$，只使用了常数级别的额外空间（几个指针变量）。

Code

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {// 创建虚拟头节点，简化边界处理（如 left=1）ListNode dummy = new ListNode(0);dummy.next = head;// 1. 移动 prev 指针到第 left-1 个节点ListNode prev = dummy;for (int i = 1; i < left; i++) {prev = prev.next;}// 2. cur 指针指向第 left 个节点，即反转区间的起始节点ListNode cur = prev.next;// 3. 执行头插法反转 [left, right] 区间// 进行 right - left 次操作for (int i = left; i < right; i++) {// a. 记录待移动的节点 curNextListNode curNext = cur.next;// b. cur 指向 curNext 的下一个节点，将 curNext 从链表中断开cur.next = curNext.next;// c. 将 curNext 插入到 prev 之后（成为反转区间的新头部）curNext.next = prev.next;// d. 更新 prev 的 next 指针prev.next = curNext;}// 4. 返回新链表的头节点return dummy.next;}
}

---

1004. 最大连续1的个数 III

题目

思路

本题可以使用 滑动窗口 的方法解决。

核心思想是维护一个窗口 [left, right]，使得这个窗口内包含的 0 的数量不超过 k。在窗口滑动过程中，不断更新窗口的最大长度。

解题过程

1. 初始化: 设置窗口左右边界 left = 0, right = 0，当前窗口内 0 的计数 count = 0，以及最大窗口长度 maxLen = 0。
2. 扩展窗口: 移动 right 指针向右扩展窗口。
   • 如果 nums[right] 是 0，则 count 加 1。
3. 收缩窗口: 当窗口内 0 的数量 count 超过 k 时，需要收缩窗口。
   • 移动 left 指针向右收缩窗口。
   • 如果移出窗口的元素 nums[left] 是 0，则 count 减 1。
   • 持续收缩直到 count <= k。
4. 更新结果: 在每次窗口调整（扩展或收缩）后，当前窗口 [left, right] 都是一个合法的窗口（0 的数量不超过 k）。计算当前窗口长度 right - left + 1，并更新 maxLen = Math.max(maxLen, right - left + 1)。
5. 遍历结束: 当 right 指针到达数组末尾时，maxLen 即为所求的最大连续1的个数（允许翻转 k 个0）。
6. 返回结果: 返回 maxLen。

复杂度

• 时间复杂度: $O(n)$，其中 $n$ 是数组 nums 的长度。每个元素最多被 left 和 right 指针访问一次。
• 空间复杂度: $O(1)$，只使用了常数级别的额外空间。

Code

class Solution {public int longestOnes(int[] nums, int k) {int maxLen = 0; // 记录最大窗口长度int zeroCount = 0; // 记录当前窗口内 0 的个数int left = 0; // 窗口左边界// right 指针负责扩展窗口for (int right = 0; right < nums.length; right++) {// 如果新进入窗口的元素是 0，增加 zeroCountif (nums[right] == 0) {zeroCount++;}// 当窗口内 0 的数量超过 k 时，收缩窗口while (zeroCount > k) {// 如果移出窗口的元素是 0，减少 zeroCountif (nums[left] == 0) {zeroCount--;}// 移动左边界left++;}// 此时窗口 [left, right] 是合法的，更新最大长度maxLen = Math.max(maxLen, right - left + 1);}return maxLen;}
}

---

1658. 将 x 减到 0 的最小操作数

题目

思路

逆向思维 + 滑动窗口

题目要求从数组两端移除元素，使得移除元素的和等于 x，并求最小的操作次数（即移除元素的最少数量）。

我们可以反向思考：从两端移除元素，等价于在数组中间保留一段 连续 的子数组，使得这段子数组的和等于 totalSum - x。

那么问题就转化为：找到数组 nums 中和为 target = totalSum - x 的 最长 连续子数组的长度 maxLen。如果找到了这样的子数组，则最小操作数就是 n - maxLen（其中 n 是数组总长度）。如果找不到，则说明无法通过移除操作使和为 x，返回 -1。

我们可以使用滑动窗口来寻找和为 target 的最长连续子数组。

解题过程

1. 计算总和: 计算数组 nums 的总和 totalSum。
2. 计算目标和: 计算目标子数组的和 target = totalSum - x。
3. 处理边界情况:
   • 如果 target < 0，说明 x 比 totalSum 还大，不可能通过移除元素得到 x，直接返回 -1。
   • 如果 target == 0，说明需要移除所有元素，其和才等于 x (x == totalSum)。此时最长子数组长度为 0，操作数为 n - 0 = n。
4. 滑动窗口: 使用滑动窗口寻找和为 target 的最长连续子数组。
   • 初始化 left = 0, currentSum = 0, maxLen = -1 (-1 表示尚未找到满足条件的子数组)。
   • 用 right 指针遍历数组，扩展窗口，将 nums[right] 加入 currentSum。
   • 当 currentSum > target 时，收缩窗口：从 currentSum 中减去 nums[left]，并向右移动 left 指针，直到 currentSum <= target。
   • 如果 currentSum == target，说明找到了一个和为 target 的子数组 [left, right]。更新 maxLen = Math.max(maxLen, right - left + 1)。
5. 返回结果:
   • 如果 maxLen 仍然是 -1，说明没有找到和为 target 的子数组，返回 -1。
   • 否则，返回 n - maxLen。

复杂度

• 时间复杂度: $O(n)$，其中 $n$ 是数组 nums 的长度。计算总和需要 $O(n)$，滑动窗口也需要 $O(n)$。
• 空间复杂度: $O(1)$，只使用了常数级别的额外空间。

Code

class Solution {public int minOperations(int[] nums, int x) {int n = nums.length;long totalSum = 0; // 使用 long 防止整数溢出for (int num : nums) {totalSum += num;}// 计算目标子数组的和long target = totalSum - x;// 边界情况：x 比总和还大，无解if (target < 0) {return -1;}// 边界情况：x 等于总和，需要移除所有元素if (target == 0) {return n;}int maxLen = -1; // 记录和为 target 的最长子数组长度，初始化为 -1 表示未找到long currentSum = 0;int left = 0;// 滑动窗口寻找和为 target 的最长子数组for (int right = 0; right < n; right++) {currentSum += nums[right];// 当窗口和大于 target 时，收缩窗口while (currentSum > target && left <= right) {currentSum -= nums[left];left++;}// 如果窗口和等于 target，更新 maxLenif (currentSum == target) {maxLen = Math.max(maxLen, right - left + 1);}}// 如果 maxLen 仍为 -1，说明找不到和为 target 的子数组，返回 -1// 否则，返回 n - maxLenreturn maxLen == -1 ? -1 : n - maxLen;}
}