每日算法-250326

83. 删除排序链表中的重复元素

题目描述

思路

使用快慢指针遍历排序链表。slow 指针指向当前不重复序列的最后一个节点，fast 指针用于向前遍历探索。当 fast 找到一个与 slow 指向的节点值不同的新节点时，就将 slow 的 next 指向 fast，然后 slow 前进。

解题过程

1. 处理边界情况：如果链表为空 (head == null)，直接返回 null。
2. 初始化指针：定义 slow 和 fast 指针，都初始化为 head。
3. 遍历链表：使用 while 循环，条件是 fast != null（slow 不会是 null 因为它总是在 fast 或其之前）。
   • 在循环中，移动 fast 指针向前探索。
   • 判断重复：如果 fast.val != slow.val，说明 fast 指向的节点是一个新的不重复元素。
   • 更新链表：此时，将 slow 的 next 指针指向 fast (slow.next = fast)，然后将 slow 指针也向前移动一步 (slow = slow.next)。
   • 无论是否找到不重复元素，fast 指针都需要在每次迭代中向前移动 (fast = fast.next)。
4. 断开尾部链接：循环结束后，slow 指向的是新链表的最后一个节点。为了确保链表正确终止，需要将 slow 的 next 设置为 null (slow.next = null)。这会断开与后面可能存在的重复元素的连接。
5. 返回结果：返回原始的 head，因为头节点可能没变，或者即使变了，head 变量仍然指向修改后链表的起始位置。

复杂度

• 时间复杂度: $O(n)$，其中 $n$ 是链表的节点数。因为 fast 指针遍历整个链表一次。
• 空间复杂度: $O(1)$，只使用了常数级别的额外空间（两个指针）。

Code (Java)

/*** 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 deleteDuplicates(ListNode head) {if (head == null) {return head; // 或者 return null，效果一样}ListNode slow = head, fast = head;// fast 指针用于遍历while (fast != null) {// 当 fast 遇到与 slow 不同的值时if (fast.val != slow.val) {// slow 的下一个节点指向 fast 这个不重复的节点slow.next = fast;// slow 移动到新的不重复节点位置slow = slow.next;}// fast 继续向后遍历fast = fast.next;}// 循环结束后，slow 是最后一个不重复节点，断开其后的链接slow.next = null;return head;}
}

---

904. 水果成篮

题目描述

思路

这是一道典型的滑动窗口问题。目标是找到一个最长的子数组，其中最多包含两种不同的元素。

我们可以使用一个哈希表（或者利用题目 0 <= fruits[i] < fruits.length 的条件，使用一个数组 hash）来记录窗口内每种水果出现的次数。同时，用一个变量 count 记录窗口内不同水果的种类数量。

解题过程

1. 初始化：
   • ret = 0: 用于存储最长子数组的长度（即最多能收集的水果数）。
   • count = 0: 记录当前窗口内不同水果的种类数。
   • n = fruits.length: 数组长度。
   • hash = new int[n]: 使用数组作为哈希表，hash[i] 存储水果 i 在当前窗口内的数量。
   • left = 0, right = 0: 滑动窗口的左右边界。
2. 扩展窗口（右移 right）：
   • right 指针向右移动，考察 fruits[right] 这个水果，令 in = fruits[right]。
   • 更新计数：如果 hash[in] == 0，说明这是窗口内第一次遇到这种水果，因此不同水果种类数 count 增加 1。
   • 将 in 水果的计数加 1：hash[in]++。
3. 收缩窗口（右移 left）：
   • 判断条件：当 count > 2 时，表示窗口内的水果种类超过了 2 种，此时窗口不满足条件，需要收缩。
   • 处理出窗口元素：令 out = fruits[left]。
   • 将 out 水果的计数减 1：hash[out]--。
   • 更新计数：如果 hash[out] == 0，说明移除这个水果后，窗口内不再有这种类型的水果了，因此不同水果种类数 count 减少 1。
   • 左边界 left 向右移动：left++。
   • 这个收缩过程（while (count > 2)）会持续进行，直到窗口重新满足 count <= 2 的条件。
4. 更新结果：在每次移动 right 之后（并且窗口调整为合法状态后），当前窗口 [left, right] 是合法的（最多包含两种水果）。计算当前窗口的长度 right - left + 1，并更新 ret = Math.max(ret, right - left + 1)。
5. 循环结束：当 right 到达数组末尾时，循环结束。
6. 返回结果：返回 ret。

复杂度

• 时间复杂度: $O(n)$，其中 $n$ 是数组 fruits 的长度。左右指针 left 和 right 都最多遍历数组一次。
• 空间复杂度: $O(n)$，在最坏情况下（例如所有水果种类都不同，但这里水果种类数受限于数组长度 n），用于存储水果计数的 hash 数组需要 $O(n)$ 的空间。如果水果种类数远小于 n，可以认为是 $O(C)$，其中 $C$ 是水果种类的数量上限。

Code (Java)

class Solution {public int totalFruit(int[] fruits) {int ret = 0, count = 0;int n = fruits.length;// 利用题目条件，可以使用数组代替 HashMapint[] hash = new int[n];for (int left = 0, right = 0; right < n; right++) {// 元素进入窗口int in = fruits[right];// 如果是新水果种类，count增加if (hash[in] == 0) {count++;}// 该水果数量增加hash[in]++;// 如果水果种类超过2种，需要收缩窗口while (count > 2) {// 元素离开窗口int out = fruits[left];// 该水果数量减少hash[out]--;// 如果移除后该水果数量为0，说明少了一种水果if (hash[out] == 0) {count--;}// 左指针右移left++;}// 窗口调整完毕后，更新最大长度ret = Math.max(ret, right - left + 1);}return ret;}
}

---

1695. 删除子数组的最大得分

题目描述

思路

这个问题要求找到一个元素唯一的子数组，使其元素和最大。这同样可以用滑动窗口解决。

我们需要维护一个窗口，确保窗口内的所有元素都是唯一的。可以使用一个哈希表 (HashMap) 来记录窗口内每个数字出现的次数。同时，维护一个变量 sum 记录当前窗口内元素的和。

解题过程

1. 初始化：
   • ret = 0: 用于存储最大得分（即元素唯一的子数组的最大和）。
   • sum = 0: 当前窗口内元素的和。
   • hash = new HashMap<>(): 记录窗口内数字及其出现次数。
   • left = 0, right = 0: 滑动窗口的左右边界。
2. 扩展窗口（右移 right）：
   • right 指针向右移动，考察 nums[right]，令 in = nums[right]。
   • 更新窗口和：sum += in。
   • 更新哈希表：将 in 的计数加 1。hash.put(in, hash.getOrDefault(in, 0) + 1)。
3. 收缩窗口（右移 left）：
   • 判断条件：当 hash.get(in) > 1 时，表示新加入的元素 in 在窗口内出现了重复，窗口不再满足“元素唯一”的条件，需要收缩。
   • 处理出窗口元素：令 out = nums[left]。
   • 更新窗口和：sum -= out。
   • 更新哈希表：将 out 的计数减 1。hash.put(out, hash.get(out) - 1)。
   • 左边界 left 向右移动：left++。
   • 这个收缩过程 (while (hash.get(in) > 1)) 会持续进行，直到窗口内 in 的计数变回 1（即窗口内不再有重复的 in）。
4. 更新结果：在每次移动 right 之后，窗口 [left, right] 必然是元素唯一的（因为收缩步骤保证了这一点）。此时，当前窗口的和 sum 是一个有效的得分。更新 ret = Math.max(ret, sum)。
5. 循环结束：当 right 到达数组末尾时，循环结束。
6. 返回结果：返回 ret。

复杂度

• 时间复杂度: $O(n)$，其中 $n$ 是数组 nums 的长度。左右指针 left 和 right 都最多遍历数组一次。哈希表操作平均时间复杂度为 $O(1)$。
• 空间复杂度: $O(n)$，在最坏情况下（例如数组中所有元素都不同），哈希表需要存储 $O(n)$ 个元素。如果数组中不同元素的数量上限为 $U$，则空间复杂度为 $O(\min (n,U))$。

Code (Java)

import java.util.HashMap;
import java.util.Map;class Solution {public int maximumUniqueSubarray(int[] nums) {int ret = 0, sum = 0;Map<Integer, Integer> hash = new HashMap<>();for (int left = 0, right = 0; right < nums.length; right++) {// 元素进入窗口int in = nums[right];// 更新窗口和sum += in;// 更新元素计数hash.put(in, hash.getOrDefault(in, 0) + 1);// 如果窗口内出现重复元素 (刚加入的 in 导致重复)while (hash.get(in) > 1) {// 元素离开窗口int out = nums[left];// 更新窗口和sum -= out;// 更新元素计数hash.put(out, hash.get(out) - 1);// 左指针右移left++;}// 此时窗口内元素唯一，更新最大得分ret = Math.max(ret, sum);}return ret;}
}

---

1423. 可获得的最大点数（复习）

题目描述

复习思路

这道题要求从数组两端取走总共 k 张牌，使得分数总和最大。

这个问题可以转化为：找到数组中间连续 n - k 个元素，使其和最小。因为数组总和是固定的，要让两端 k 个元素的和最大，等价于让中间 n - k 个元素的和最小。

因此，我们可以使用滑动窗口来找到长度为 m = n - k 的子数组的最小和。

解题过程（滑动窗口找最小和）

1. 计算窗口大小：计算中间部分的长度 m = n - k。
2. 处理特殊情况：如果 m == 0（即 n == k），说明需要取走所有卡牌，直接计算并返回整个数组的总和。
3. 初始化：
   • totalSum = 0: 整个数组的总和。
   • windowSum = 0: 当前滑动窗口（长度为 m）的和。
   • minWindowSum = Integer.MAX_VALUE: 用于记录所有长度为 m 的窗口中，和的最小值。
   • left = 0: 窗口左边界。
4. 遍历数组与滑动窗口：
   • 使用 right 指针从 0 遍历到 n-1。
   • 累加总和：totalSum += cardPoints[right]。
   • 累加窗口和：windowSum += cardPoints[right]。
   • 维护窗口大小：当窗口达到大小 m 时（即 right - left + 1 == m 或 right >= m - 1），开始执行以下操作：
     • 更新最小窗口和：minWindowSum = Math.min(minWindowSum, windowSum)。
     • 收缩窗口：从 windowSum 中减去最左边的元素 cardPoints[left]。
     • 移动左边界：left++。
5. 计算结果：遍历结束后，minWindowSum 存储了长度为 n - k 的子数组的最小和。最终结果为 totalSum - minWindowSum。

复杂度

• 时间复杂度: $O(n)$，其中 $n$ 是数组 cardPoints 的长度。只需要遍历数组一次。
• 空间复杂度: $O(1)$，只使用了常数级别的额外空间。

Code (Java)

class Solution {public int maxScore(int[] cardPoints, int k) {int n = cardPoints.length;int m = n - k; // 中间要保留的元素个数 (窗口大小)int totalSum = 0; // 数组总和int windowSum = 0; // 当前窗口的和// ret 在这里用来存储长度为 m 的窗口的最小和int minWindowSum = Integer.MAX_VALUE;// 特殊情况：k == n, m == 0if (m == 0) {for (int point : cardPoints) {totalSum += point;}return totalSum;}for (int left = 0, right = 0; right < n; right++) {// 累加当前元素到窗口和windowSum += cardPoints[right];// 同时累加到总和 (只需计算一次)totalSum += cardPoints[right];// 当窗口大小达到 m 时if (right - left + 1 >= m) {// 更新最小窗口和minWindowSum = Math.min(minWindowSum, windowSum);// 从窗口和中移除最左边的元素windowSum -= cardPoints[left];// 左指针右移，保持窗口大小left++;}}// 最大得分 = 总和 - 中间 m 个元素的最小和// 注意: 如果 m > n (k < 0) 或 m < 0 (k > n) 是无效输入, 但题目保证 1 <= k <= cardPoints.length// 如果 m=n (k=0), minWindowSum 应该等于 totalSum，结果是 0 (逻辑上正确，但未覆盖 m=0 的代码路径)// minWindowSum 如果没被更新过(例如 m > n), 结果会出错, 但题目约束避免了此情况。// 在 m > 0 时，minWindowSum 一定会被更新。return totalSum - minWindowSum;}
}