每日算法 - 250511

記錄一下今天刷的幾道LeetCode題目，主要是關于貪心算法和數組處理。

1221. 分割平衡字符串

題目

思路

貪心

解題過程

我們可以遍歷一次字符串，維護一個計數器 balance。當遇到字符 'L' 時，balance 增加；當遇到字符 'R' 時，balance 減少。當 balance 的值回到 0 時，說明從上一個平衡點（或字符串開頭）到當前位置的 'L' 和 'R' 字符數量相等，即找到了一個平衡字符串，此時結果 ret 加一。

復雜度

• 時間復雜度: $O(N)$, N為字符串長度。
• 空間復雜度: $O(N)$, 因為 ss.toCharArray() 創建了一個新的字符數組。如果只考慮額外空間（不包括輸入轉換），則為 $O(1)$。

Code

class Solution {public int balancedStringSplit(String ss) {int ret = 0;char[] s = ss.toCharArray();int balance = 0; // Renamed sum to balance for clarityfor (int i = 0; i < s.length; i++) {if (s[i] == 'L') {balance++;} else { // s[i] == 'R'balance--;}if (balance == 0) {ret++;}}return ret;}
}

2405. 子字符串的最優劃分

題目

思路

貪心

解題過程

我們遍歷字符串，目標是讓每個子字符串盡可能長，同時確保其中沒有重復字符。
使用一個頻率數組 map (或哈希集合) 來追蹤當前子字符串中已出現的字符。
遍歷字符串中的每個字符：

1. 如果當前字符在 map 中已標記為出現過，則表示當前子字符串到此為止（不包括當前字符）是一個有效的劃分。我們讓結果 ret 增加，并重置 map (清空頻率記錄)，然后將當前字符加入新的子字符串（即標記其在 map 中出現）。
2. 如果當前字符未在 map 中出現過，則將其加入當前子字符串（標記其在 map 中出現），并繼續擴展。
   初始時，ret 為 1，因為至少會有一個子字符串。

復雜度

• 時間復雜度: $O(N)$, N為字符串長度。遍歷字符串一次，Arrays.fill 操作作用于固定大小 (26) 的數組，是 $O(1)$ 操作。
• 空間復雜度: $O(N)$

Code

class Solution {public int partitionString(String ss) {char[] s = ss.toCharArray();int[] map = new int[26];int ret = 1;for (char c : s) {if (++map[c - 'a'] > 1) {ret++;Arrays.fill(map, 0);map[c - 'a']++;}}return ret;}
}

2294. 劃分數組使最大差為 K

題目

思路

貪心

解題過程

想要獲得最少的子序列（子數組在題目中指子序列，因為元素順序可以打亂后分組），我們就希望每個子序列盡可能包含更多的元素，同時滿足最大差不超過 K 的條件。

1. 對數組 nums進行排序。這樣，具有相似數值的元素會聚集在一起。
2. 初始化子序列數量 ret = 1（因為至少有一個子序列）。
3. 將排序后數組的第一個元素設為當前子序列的最小值 minVal。
4. 遍歷排序后的數組，從第二個元素開始。對于每個元素 x：
   • 如果 x - minVal > k，則當前元素 x 不能包含在當前子序列中。因此，我們必須開始一個新的子序列。讓 ret 增加，并將 minVal 更新為當前元素 x（它將是新子序列的第一個也是最小的元素）。
   • 如果 x - minVal <= k，則當前元素 x 可以包含在當前子序列中，我們繼續。minVal 保持不變，因為它是當前子序列的固定最小值。
     為什么可以排序？我們關心的是子序列里的最大值和最小值的差值，這和原始順序無關。題目要求返回的是最少子序列的個數，而不是子序列本身。所以可以排序。

復雜度

• 時間復雜度: $O(N\log N)$, 主要由排序決定。遍歷是 $O(N)$。
• 空間復雜度: $O(\log N)$ or $O(1)$, 取決于排序算法實現所使用的棧空間或是否為原地排序。Java的Arrays.sort()對于基本類型數組通常是快速排序的變體，會使用 $O(\log N)$ 的棧空間。

Code

class Solution {public int partitionArray(int[] nums, int k) {if (nums == null || nums.length == 0) {return 0;}Arrays.sort(nums);int ret = 1;int minVal = nums[0]; for (int x : nums) {if (x - minVal > k) {ret++;minVal = x; }}return ret;}
}

154. 尋找旋轉排序數組中的最小值 II

題目

這是第二次寫這道題，這次寫的還不錯，就不再多說了，詳細題解見每日算法-250415

Code

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