記錄今天學習和解決的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;}
}