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

比賽地址?

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

public class Solution {public int minimumCost(int[] nums) {if (nums.length < 3) {// 數(shù)組長度小于3時(shí)，無法分割成3個(gè)子數(shù)組return -1;}int minCost = Integer.MAX_VALUE;int n = nums.length;// 第一個(gè)分割點(diǎn)至少在索引1，第二個(gè)分割點(diǎn)至少在索引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]) {// 如果前一個(gè)元素的1的數(shù)量大于后一個(gè)元素的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ù)組分成最小總代價(jià)的子數(shù)組 I

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

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

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

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

• 如果 minCount=1

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

• 如果 minCount>1?

1. 如果數(shù)組 nums 中存在一個(gè)元素 num 滿足 num?mod?minNum≠0 ，記 newNum= (num? mod ?minNu)
2. 則必有 0<newNum<minNum 可以在一次操作中選擇 num 和 minNum ，刪除這兩個(gè)元素并添加元素newNum。
3. 由于 newNum < minNum ，因此 newNum 成為數(shù)組 nums 中的新的最小元素且最小元素唯一，之后可以每次選擇 newNum 和另一個(gè)元素，其效果是刪除另一個(gè)元素，保留 newNum ，直到數(shù)組 nums 中只有一個(gè)元素 newNum ，數(shù)組 nums 的最小長度是 1
4. 如果數(shù)組 nums 中不存在元素 num 滿足 num? mod? minNum ≠ 0 ，則無法通過操作得到小于 minNum 的元素，因此在將所有大于 minNu 的元素刪除之后，剩余 minCount 個(gè)元素 minNum 。由于每次可以選擇 2 個(gè)元素 minNum 執(zhí)行操作得到元素 0 無法繼續(xù)操作，因此 minCount 個(gè)元素 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)生新的最小值，計(jì)算最小值的數(shù)量return (count_min ) // 2 +1 if count_min % 2 != 0 else count_min // 2

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

一、直接用滑動(dòng)窗口求解

這種方法會(huì)超時(shí)

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

二、引入堆的代碼實(shí)現(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):# 維護(hù)一個(gè)大小為 dist + 1 的最小堆min_heap = nums[start:start + dist + 1]heapq.heapify(min_heap)window_cost = 0# 彈出最小的 k-1 個(gè)元素并計(jì)算它們的和for _ in range(k-1):if min_heap:window_cost += heapq.heappop(min_heap)minimumCost = min(minimumCost, window_cost)return first + minimumCost

三、大小頂堆、延遲刪除、滑動(dòng)窗口

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

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

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

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

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

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

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

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

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

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

class Solution {// small是小頂堆 維護(hù)前k-2小的數(shù)// big是大頂堆 維護(hù)窗口內(nèi)剩下的數(shù)PriorityQueue<Integer> small, big;// 標(biāo)記當(dāng)前元素是否已經(jīng)被刪除以及被刪除的個(gè)數(shù)HashMap<Integer, Integer> smallMark, bigMark;// samll和big當(dāng)前未被刪除的元素個(gè)數(shù)int smallSiz, bigSiz;long sum;public long minimumCost(int[] nums, int k, int dist) {// k個(gè) 除掉第一個(gè) 還要選k-1個(gè)// 枚舉第2個(gè) nums[i] nums[i+1]... nums[i+dist] 里選k-2個(gè)最小的數(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;// 枚舉第二個(gè)數(shù)的位置// 枚舉的位置從i-1變成i時(shí) nums[i]離開了窗口 nums[i+dist]進(jìn)入了窗口for (int i = 2; i + k-2 < n; i++) {// 移除nums[i]// 因?yàn)橐L問small.peek() 為了確保small.peek()是未被刪除的元素 需要先更新smallupdateSmallPeek();// nums[i]在前k-2小里if (smallSiz > 0 && small.peek() >= nums[i]) {// 因?yàn)閚ums[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個(gè) 也就是還差一個(gè)才夠k-2個(gè)// 是為了方便后面的操作// 從small里選一個(gè)放到big里int tmp = small.poll();smallSiz--;sum -= tmp;big.add(tmp);bigSiz++;}// 先放到big里 然后從big里面拿一個(gè)放到small就剛好k-2個(gè)if (i+dist < n) {big.add(nums[i+dist]);bigSiz++;}// 要從big里拿一個(gè) 訪問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);}}
}

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

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

因?yàn)樾№敹阎荒茏屇杆僭L問堆中的最小值，而不是最大值。因此，如果窗口中有一個(gè)更小的數(shù)字需要加入到已滿的小頂堆中（這時(shí)候我們需要替換掉小頂堆中最大的數(shù)字），您需要一種方式來找到小頂堆中的最大值，而大頂堆允許我們做到這一點(diǎn)。?

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

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

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

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