每日算法 - 2025.05.02
記錄一下今天刷的幾道 LeetCode 算法題。
3191. 使二進制數組全部等于 1 的最少操作次數 I
題目
思路
貪心
解題過程
遍歷數組 nums
。當我們遇到 nums[i]
時:
- 如果
nums[i]
是 1,我們不需要進行操作,因為目標是全 1,并且之前的元素[0, i-1]
已經被處理為 1(基于貪心策略)。 - 如果
nums[i]
是 0,我們 必須 在此時進行翻轉操作。因為這是唯一一次可以影響nums[i]
的操作(操作窗口是[i, i+1, i+2]
)。任何后續的操作都無法再將nums[i]
從 0 變為 1。因此,我們翻轉nums[i]
,nums[i+1]
,nums[i+2]
,并增加操作計數。
我們只遍歷到 n-3
,因為操作需要三個連續的元素。當循環結束后,我們需要檢查最后兩個元素 nums[n-2]
和 nums[n-1]
。由于我們無法再對它們執行翻轉操作(沒有足夠的后續元素形成長度為 3 的窗口),它們必須已經是 1。如果其中任何一個是 0,則無法完成目標,返回 -1。否則,返回累計的操作次數。
復雜度
- 時間復雜度:
O(N)
,其中 N 是數組的長度,我們只需要遍歷數組一次。 - 空間復雜度:
O(1)
,我們只使用了常數級別的額外空間。
Code
class Solution {public int minOperations(int[] nums) {int n = nums.length;int ret = 0;for (int i = 0; i <= n - 3; i++) {if (nums[i] == 0) {nums[i] = 1;nums[i + 1] = 1 - nums[i + 1];nums[i + 2] = 1 - nums[i + 2];ret++;}}if (nums[n - 2] == 0 || nums[n - 1] == 0) {return -1;}return ret;}
}
1827. 最少操作使數組遞增
題目
思路
貪心
解題過程
我們要使數組嚴格遞增,并且操作次數最少。我們可以從左到右遍歷數組,比較相鄰的兩個元素 nums[i]
和 nums[i+1]
。
- 如果
nums[i] < nums[i+1]
,數組在i
和i+1
之間已經是嚴格遞增的,我們不需要做任何操作。 - 如果
nums[i] >= nums[i+1]
,為了滿足嚴格遞增的要求,nums[i+1]
必須至少增加到nums[i] + 1
。為了使操作次數最少,我們選擇將其恰好增加到nums[i] + 1
。增加的操作次數是(nums[i] + 1) - nums[i+1]
。同時,我們需要更新nums[i+1]
的值為nums[i] + 1
,以便后續的比較基于更新后的值。
累加所有操作次數即可。
復雜度
- 時間復雜度:
O(N)
,其中 N 是數組的長度,我們只需要遍歷數組一次。 - 空間復雜度:
O(1)
,我們是在原地修改數組(或者可以只用一個變量記錄前一個元素的值),只使用了常數級別的額外空間。
Code
class Solution {public int minOperations(int[] nums) {int n = nums.length;int ret = 0;for (int i = 0; i < n - 1; i++) {if (nums[i] >= nums[i + 1]) {ret += nums[i] + 1 - nums[i + 1];nums[i + 1] = nums[i] + 1;}}return ret;}
}
2027. 轉換字符串的最少操作次數
題目
思路
貪心
解題過程
我們需要將字符串中的所有 ‘X’ 轉換成 ‘O’,每次操作可以連續轉換 3 個字符。目標是使用最少的操作次數。
我們可以從左到右遍歷字符串 s
。
- 如果當前字符
s[i]
是 ‘O’,它已經滿足條件,我們不需要操作,直接看下一個字符s[i+1]
。 - 如果當前字符
s[i]
是 ‘X’,我們必須執行一次操作來轉換它。根據貪心策略,這次操作應該盡可能地覆蓋更多的 ‘X’。由于操作固定影響s[i]
,s[i+1]
,s[i+2]
這三個字符,我們執行一次操作,將這三個字符(無論它們原來是 ‘X’ 還是 ‘O’)都視為已處理(邏輯上變成 ‘O’),然后將索引i
直接增加 3(即跳過i+1
和i+2
),因為這三個位置都已經被這次操作覆蓋了。操作次數加 1。
遍歷結束后,累計的操作次數就是最少次數。
復雜度
- 時間復雜度:
O(N)
,其中 N 是字符串的長度。雖然我們可能會跳過字符 (i += 2
),但每個字符最多被訪問一次。 - 空間復雜度:
O(N)
(如果使用toCharArray()
)或O(1)
(如果直接操作字符串索引)。Java 中字符串是不可變的,toCharArray()
會創建字符數組副本,空間復雜度為O(N)
。如果語言支持原地修改或僅通過索引訪問,則可以是O(1)
。
Code
class Solution {public int minimumMoves(String ss) {char[] s = ss.toCharArray();int n = s.length;int ret = 0;for (int i = 0; i < n; /* i 在循環內部更新 */) {// 如果當前字符是 'X'if (s[i] == 'X') {// 需要一次操作ret++;// 這次操作覆蓋了 i, i+1, i+2,所以下次從 i+3 開始檢查i += 3; } else {// 如果當前字符是 'O',直接檢查下一個字符i++;}}return ret;}
}
注意:原代碼中 i += 2;
配合 for
循環的 i++
實際上是 i += 3
的效果,這里修改為在 if
塊內直接 i += 3
,else
塊內 i++
,更清晰地表達了邏輯。
3397. 執行操作后不同元素的最大數量 (復習)
題目
這是第二次做這道題了,已經算是掌握了。核心思想是貪心地調整每個數的值,以最大化不同元素的數量。
詳細題解見之前的博客:每日算法-250427,里面還有點小優化。
Code
class Solution {public int maxDistinctElements(int[] nums, int k) {Arrays.sort(nums);int ret = 1;nums[nums.length - 1] += k;for (int i = nums.length - 2; i >= 0; i--) {nums[i] = Math.max(Math.min(nums[i] + k, nums[i + 1] - 1), nums[i] - k);if (nums[i] < nums[i + 1]) {ret++;}}return ret;}
}
2476. 二叉搜索樹最近節點查詢 (復習)
題目
這道題也是復習,核心思路已經掌握。主要步驟是:
- 通過 中序遍歷 將二叉搜索樹(BST)轉換為一個 有序數組。
- 對于每個查詢值
k
,在有序數組中使用 二分查找 來找到min_i
(小于等于k
的最大值) 和max_i
(大于等于k
的最小值)。
二分查找細節:
通常使用二分查找找到第一個大于等于 k
的元素的索引 idx
。
max_i
就是nums[idx]
(如果idx
沒越界)。如果idx
越界,說明k
比所有元素都大,max_i
為 -1。min_i
:- 如果
nums[idx] == k
,則min_i = k
。 - 如果
nums[idx] > k
,則min_i
是idx
前一個元素nums[idx-1]
(如果idx > 0
)。如果idx == 0
,說明k
比所有元素都小,min_i
為 -1。 - 如果
idx
越界(即k
比所有元素都大),min_i
是數組最后一個元素nums[n-1]
。
- 如果
詳細題解見之前的博客:每日算法-250413
Code
class Solution {public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {List<Integer> arr = new ArrayList<>();rootToList(root, arr);int len = arr.size();int[] nums = new int[len];ListToArray(nums, arr);int n = queries.size();int min = 0, max = 0;List<List<Integer>> ret = new ArrayList<>(n);for (int i = 0; i < n; i++) {List<Integer> tmp = new ArrayList<>();int k = queries.get(i);int index = search(nums, k);if (index >= len) {max = -1;min = nums[len - 1];} else {min = index == 0 ? -1 : nums[index - 1];if (nums[index] == k) {min = nums[index];}max = nums[index];}tmp.add(min);tmp.add(max);ret.add(tmp);}return ret;}private void rootToList(TreeNode root, List<Integer> arr) {if (root == null) {return;}rootToList(root.left, arr);arr.add(root.val);rootToList(root.right, arr);}private void ListToArray(int[] nums, List<Integer> arr) {for (int i = 0; i < nums.length; i++) {nums[i] = arr.get(i);}}private int search(int[] nums, int k) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < k) {left = mid + 1;} else {right = mid - 1;}}return left;}
}