接下來會以刷常規(guī)題為主?，周賽的難題想要獨立做出來還是有一定難度的，需要消耗大量時間

比賽地址?

3011. 判斷一個數(shù)組是否可以變?yōu)橛行?/h2>

public class Solution {public int minimumCost(int[] nums) {if (nums.length < 3) {// 數(shù)組長度小于3時，無法分割成3個子數(shù)組return -1;}int minCost = Integer.MAX_VALUE;int n = nums.length;// 第一個分割點至少在索引1，第二個分割點至少在索引2for (int i = 1; i < n - 1; i++) {for (int j = i + 1; j < n; j++) {int cost = nums[0] + nums[i] + nums[j];minCost = Math.min(minCost, cost);}}return minCost;}
}

100164. 通過操作使數(shù)組長度最小

冒泡排序

class Solution {public boolean canSortArray(int[] nums) {int n = nums.length;for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (Integer.bitCount(nums[j]) == Integer.bitCount(nums[j + 1]) && nums[j]>nums[j + 1]) {// 如果前一個元素的1的數(shù)量大于后一個元素的1的數(shù)量，交換它們int temp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = temp;}}}// 遍歷完后，檢查數(shù)組是否有序for (int i = 0; i < n - 1; i++) {if (nums[i] > nums[i + 1]) {return false;}}return true;}
}

100181. 將數(shù)組分成最小總代價的子數(shù)組 I

當(dāng) x<y 時，x? mod ?y=x 因此如果選擇數(shù)組中的兩個不相等的元素，則可以刪除較大元素，保留較小元素。

用 minNum表示數(shù)組 nums 中的最小元素

用 minCount 表示數(shù)組 nums 中的 minNum 的出現(xiàn)次數(shù)

分別考慮 minCount=1 和 minCount>1 的情況。

• 如果 minCount=1

則可以每次選擇 minNum? 和另一個元素，由于 minNum?一定小于另一個元素，因此總是可以刪除另一個元素，保留 minNum，直到數(shù)組 nums? 中只有一個元素 minNum，數(shù)組 nums的最小長度是 1。

• 如果 minCount>1?

1. 如果數(shù)組 nums 中存在一個元素 num 滿足 num?mod?minNum≠0 ，記 newNum= (num? mod ?minNu)
2. 則必有 0<newNum<minNum 可以在一次操作中選擇 num 和 minNum ，刪除這兩個元素并添加元素newNum。
3. 由于 newNum < minNum ，因此 newNum 成為數(shù)組 nums 中的新的最小元素且最小元素唯一，之后可以每次選擇 newNum 和另一個元素，其效果是刪除另一個元素，保留 newNum ，直到數(shù)組 nums 中只有一個元素 newNum ，數(shù)組 nums 的最小長度是 1
4. 如果數(shù)組 nums 中不存在元素 num 滿足 num? mod? minNum ≠ 0 ，則無法通過操作得到小于 minNum 的元素，因此在將所有大于 minNu 的元素刪除之后，剩余 minCount 個元素 minNum 。由于每次可以選擇 2 個元素 minNum 執(zhí)行操作得到元素 0 無法繼續(xù)操作，因此 minCount 個元素 minNum 的最多操作次數(shù)可以根據(jù)count_min的奇偶性判斷

class Solution:def minimumArrayLength(self, nums: List[int]) -> int:min_val = min(nums)count_min = nums.count(min_val)for num in nums:if num % min_val != 0:return 1  # 產(chǎn)生了新的更小值# 沒有產(chǎn)生新的最小值，計算最小值的數(shù)量return (count_min ) // 2 +1 if count_min % 2 != 0 else count_min // 2

100178. 將數(shù)組分成最小總代價的子數(shù)組 II

一、直接用滑動窗口求解

這種方法會超時

class Solution:def minimumCost(self, nums: List[int], k: int, dist: int) -> int:first = nums[0]  # 初始元素的代價window_size = dist + 1  # 窗口大小minimumCost = float('inf')  # 初始化最小代價為無窮大# 遍歷數(shù)組，尋找除第一個和最后一個元素之外的最小的 k-1 個元素for start in range(1, len(nums) - window_size + 1):window = nums[start:start + window_size]sorted_window = sorted(window)# 獲取除第一個的 k-1 個最小元素的和window_cost = sum(sorted_window[:k-1])# 更新最小代價minimumCost = min(minimumCost, window_cost)# 最終的最小總代價是第一個元素的代價加上最小窗口代價return first + minimumCost 

二、引入堆的代碼實現(xiàn)

效率和之前的方法相差無幾

class Solution:def minimumCost(self, nums: List[int], k: int, dist: int) -> int:first = nums[0]n = len(nums)minimumCost = float('inf')for start in range(1, n - dist):# 維護一個大小為 dist + 1 的最小堆min_heap = nums[start:start + dist + 1]heapq.heapify(min_heap)window_cost = 0# 彈出最小的 k-1 個元素并計算它們的和for _ in range(k-1):if min_heap:window_cost += heapq.heappop(min_heap)minimumCost = min(minimumCost, window_cost)return first + minimumCost

三、大小頂堆、延遲刪除、滑動窗口

這道題目的思路是利用滑動窗口結(jié)合兩個堆（優(yōu)先隊列）來找出序列中指定數(shù)量(`k-1`)的最小數(shù)的和，它們是從序列的某個區(qū)間（該區(qū)間長度由`dist`決定）中選擇出來的。這個序列中的第一個數(shù) (`nums[0]`) 是固定的，所以總是被包含在結(jié)果中。

下面是詳細(xì)的解題步驟：

1. 初始化兩個堆：一個小頂堆?small?來保存當(dāng)前窗口中的最小的?k-2?個數(shù)，以及一個大頂堆?big?來保存窗口內(nèi)剩余的數(shù)。

2. 使用 HashMap 進行延遲刪除：為了實現(xiàn)有效地從堆中刪除特定的非堆頂元素，創(chuàng)建兩個?HashMap?(smallMark?和?bigMark) 來標(biāo)記堆中元素是否已經(jīng)被 "刪除"。該刪除實際上是延遲執(zhí)行的，即直到這個元素出現(xiàn)在堆頂時才真正被排除。

3. 填充初始窗口：從?nums?數(shù)組的第二個元素開始，將?dist+1?長度內(nèi)的元素放入?big?堆。

4. 從?big?中取出?k-2?個最小元素：這?k-2?個元素是將要加入?small?的，記錄這?k-2?個數(shù)的和作為窗口的當(dāng)前總和。

5. 滑動窗口：在數(shù)組中滑動窗口，并動態(tài)維護這兩個堆以保持正確的最小?k-2?個數(shù)的總和。

6. 調(diào)整堆：當(dāng)窗口滑動導(dǎo)致元素移出窗口時，更新?small?堆以保持其有效性，并進行相應(yīng)的調(diào)整。如果移出的元素當(dāng)前在?small?中，則它需要被標(biāo)記為已刪除；如果它在?big?中，則直接標(biāo)記為已刪除。

7. 處理新進入窗口的元素：窗口滑動時，可能會有新的元素進入。這些新元素需要加入到?big?堆中。從?big?中取出的最小元素會放入?small?堆，并更新當(dāng)前窗口總和（sum）。

8. 求解最終結(jié)果：在滑動窗口過程中，每次窗口更新后，計算此時的窗口總和加上?nums[0]（固定加入）。所有窗口中總和的最小值即為所求問題的答案。

class Solution {// small是小頂堆 維護前k-2小的數(shù)// big是大頂堆 維護窗口內(nèi)剩下的數(shù)PriorityQueue<Integer> small, big;// 標(biāo)記當(dāng)前元素是否已經(jīng)被刪除以及被刪除的個數(shù)HashMap<Integer, Integer> smallMark, bigMark;// samll和big當(dāng)前未被刪除的元素個數(shù)int smallSiz, bigSiz;long sum;public long minimumCost(int[] nums, int k, int dist) {// k個 除掉第一個 還要選k-1個// 枚舉第2個 nums[i] nums[i+1]... nums[i+dist] 里選k-2個最小的數(shù)// nums[i+1] nums[i+k-2]small = new PriorityQueue<>(Collections.reverseOrder());smallSiz = 0;smallMark = new HashMap<>();big = new PriorityQueue<>();bigSiz = 0;bigMark = new HashMap<>();// 當(dāng)前小頂堆的和 也就是前k-2小的和sum = 0;int n = nums.length;// 把nums[1+1]...nums[1+dist]里的數(shù)加入到big里for (int i = 2; i <= Math.min(n-1, dist+1); i++) {big.add(nums[i]);bigSiz++;}// 取出前k-2小的數(shù)放入smallfor (int i = 0; i < k-2; i++ ) {int tmp = big.poll();bigSiz--;sum += tmp;small.add(tmp);smallSiz++;}long res = nums[0] + nums[1] + sum;// 枚舉第二個數(shù)的位置// 枚舉的位置從i-1變成i時 nums[i]離開了窗口 nums[i+dist]進入了窗口for (int i = 2; i + k-2 < n; i++) {// 移除nums[i]// 因為要訪問small.peek() 為了確保small.peek()是未被刪除的元素 需要先更新smallupdateSmallPeek();// nums[i]在前k-2小里if (smallSiz > 0 && small.peek() >= nums[i]) {// 因為nums[i] 是可能小于small.peek()的 我們沒法直接刪除nums[i] 所以要標(biāo)記一下smallMark.merge(nums[i], 1, Integer::sum);// 從small里刪除nums[i]smallSiz--;sum -= nums[i];} else {// nums[i]不在前k-2小里 bigMark.merge(nums[i], 1, Integer::sum);bigSiz--;// 這里是為了使得small的數(shù)量變成k-3個 也就是還差一個才夠k-2個// 是為了方便后面的操作// 從small里選一個放到big里int tmp = small.poll();smallSiz--;sum -= tmp;big.add(tmp);bigSiz++;}// 先放到big里 然后從big里面拿一個放到small就剛好k-2個if (i+dist < n) {big.add(nums[i+dist]);bigSiz++;}// 要從big里拿一個 訪問big.peek()之前要先更新bigupdateBigPeek();int tmp = big.poll();bigSiz--;sum += tmp;small.add(tmp);smallSiz++;res = Math.min(res, nums[i] + nums[0] + sum);}return res;}// 每次訪問small.peek()之前都要先更新smallpublic void updateSmallPeek() {// 如果small.peek()已經(jīng)被刪除了 那么就把它從small里移除 直到small.peek()是未被刪除的元素while (smallSiz > 0 && smallMark.getOrDefault(small.peek(), 0) > 0) {int tmp = small.poll();smallMark.merge(tmp, -1, Integer::sum);}}public void updateBigPeek() {while (bigSiz > 0 && bigMark.getOrDefault(big.peek(), 0) > 0) {int tmp = big.poll();bigMark.merge(tmp, -1, Integer::sum);}}
}

這個方法高效地使用了堆結(jié)構(gòu)來保持每次窗口移動后，都能快速地選擇出當(dāng)前窗口中的k-2個最小數(shù)，而HashMap的標(biāo)記刪除機制則可以繞過優(yōu)先隊列不支持直接刪除的限制。通過這個算法，你可以在移動窗口的過程中，不斷更新當(dāng)前窗口的最小值和，最終得到包含`nums[0]`在內(nèi)的最小成本和。

思考1：為什么要用大頂堆只用小頂堆會怎么樣?

因為小頂堆只能讓您迅速訪問堆中的最小值，而不是最大值。因此，如果窗口中有一個更小的數(shù)字需要加入到已滿的小頂堆中（這時候我們需要替換掉小頂堆中最大的數(shù)字），您需要一種方式來找到小頂堆中的最大值，而大頂堆允許我們做到這一點。?

思考2：bigMark.merge(tmp, -1, Integer::sum)這個是干什么

在Java中的?PriorityQueue?并沒有提供直接刪除特定元素的操作，而是只提供了刪除堆頂元素的操作。為了解決這個問題，bigMark?的用途是實現(xiàn)“延遲刪除”，這個技巧通常在優(yōu)先隊列中刪除非頂部元素時使用。

• 檢查 bigMark 是否包含密鑰 tmp。
• 如果 bigMark 不包含 tmp，則將鍵值對(tmp，-1)插入 bigMark。
• 如果 bigMark 包含 tmp，則使用 Integer: : sum 將 bigMark 中 tmp 的現(xiàn)有值添加到 -1(因為 -1是合并值)。然后，這個和的結(jié)果替換 bigMark 中 tmp 鍵的當(dāng)前值。

// 假設(shè)堆中有一個元素值為 5，現(xiàn)在我們要刪除它：
int tmp = 5;
bigMark.merge(tmp, 1, Integer::sum); // 標(biāo)記 tmp 為已刪除// 當(dāng)我們后續(xù)從堆中得到堆頂元素時：
updateBigPeek(); // 在訪問堆頂前更新堆// updateBigPeek 的實現(xiàn)會檢查堆頂元素是否被標(biāo)記為已刪除，如果是，就將其從堆中移除，
// 并在 bigMark 中更新其計數(shù)：
public void updateBigPeek() {while (bigSiz > 0 && bigMark.getOrDefault(big.peek(), 0) > 0) {int tmp = big.poll(); // 彈出堆頂元素bigMark.merge(tmp, -1, Integer::sum); // 更新 bigMark，減少刪除計數(shù)}
}