本人水平有限，只做出3道，最后1道放棄。

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

給你一個長度為 n 的整數(shù)數(shù)組 nums 。

一個數(shù)組的 代價 是它的 第一個 元素。比方說，[1,2,3] 的代價是 1 ，[3,4,1] 的代價是 3 。

你需要將 nums 分成 3 個 連續(xù)且沒有交集 的子數(shù)組。

請你返回這些子數(shù)組的 最小 代價 總和 。

示例 1：

輸入：nums = [1,2,3,12]
輸出：6
解釋：最佳分割成 3 個子數(shù)組的方案是：[1] ，[2] 和 [3,12] ，總代價為 1 + 2 + 3 = 6 。
其他得到 3 個子數(shù)組的方案是：

• [1] ，[2,3] 和 [12] ，總代價是 1 + 2 + 12 = 15 。
• [1,2] ，[3] 和 [12] ，總代價是 1 + 3 + 12 = 16 。
  示例 2：

輸入：nums = [5,4,3]
輸出：12
解釋：最佳分割成 3 個子數(shù)組的方案是：[5] ，[4] 和 [3] ，總代價為 5 + 4 + 3 = 12 。
12 是所有分割方案里的最小總代價。
示例 3：

輸入：nums = [10,3,1,1]
輸出：12
解釋：最佳分割成 3 個子數(shù)組的方案是：[10,3] ，[1] 和 [1] ，總代價為 10 + 1 + 1 = 12 。
12 是所有分割方案里的最小總代價。

解題思路

題目要求將原數(shù)組分割為三個子數(shù)組，每個子數(shù)組的第一個元素為該子數(shù)組的代價，求分割方案中三個子數(shù)組的最小總代價

設(shè)定兩個指針i和j作為邊界分割，三個子數(shù)組的區(qū)間范圍為[0,i-1],[i,j-1],[j,m]。
花銷的表達式為nums[0]+nums[i]+nums[j]

代碼

class Solution {
    public int minimumCost(int[] nums) {
        int n = nums.length;
        int minCost = Integer.MAX_VALUE;
        for (int i = 1; i < n-1; i++) {
            for (int j = i+1; j < n; j++) {
                minCost = Math.min(minCost, nums[0] + nums[i] + nums[j]);
            }
        }
        return minCost;
    }
}

二、判斷一個數(shù)組是否可以變?yōu)橛行?/h3>

題目

給你一個下標(biāo)從 0 開始且全是 正 整數(shù)的數(shù)組 nums 。

一次 操作 中，如果兩個 相鄰 元素在二進制下數(shù)位為 1 的數(shù)目 相同 ，那么你可以將這兩個元素交換。你可以執(zhí)行這個操作 任意次 （也可以 0 次）。

如果你可以使數(shù)組變有序，請你返回 true ，否則返回 false 。

示例 1：

輸入：nums = [8,4,2,30,15]
輸出：true
解釋：我們先觀察每個元素的二進制表示。 2 ，4 和 8 分別都只有一個數(shù)位為 1 ，分別為 “10” ，“100” 和 “1000” 。15 和 30 分別有 4 個數(shù)位為 1 ：“1111” 和 “11110” 。
我們可以通過 4 個操作使數(shù)組有序：

• 交換 nums[0] 和 nums[1] 。8 和 4 分別只有 1 個數(shù)位為 1 。數(shù)組變?yōu)?[4,8,2,30,15] 。
• 交換 nums[1] 和 nums[2] 。8 和 2 分別只有 1 個數(shù)位為 1 。數(shù)組變?yōu)?[4,2,8,30,15] 。
• 交換 nums[0] 和 nums[1] 。4 和 2 分別只有 1 個數(shù)位為 1 。數(shù)組變?yōu)?[2,4,8,30,15] 。
• 交換 nums[3] 和 nums[4] 。30 和 15 分別有 4 個數(shù)位為 1 ，數(shù)組變?yōu)?[2,4,8,15,30] 。
  數(shù)組變成有序的，所以我們返回 true 。
  注意我們還可以通過其他的操作序列使數(shù)組變得有序。
  示例 2：

輸入：nums = [1,2,3,4,5]
輸出：true
解釋：數(shù)組已經(jīng)是有序的，所以我們返回 true 。
示例 3：

輸入：nums = [3,16,8,4,2]
輸出：false
解釋：無法通過操作使數(shù)組變?yōu)橛行颉?/p>

解題思路

題目要求我們只能對在二進制下數(shù)位為1的數(shù)量相同的數(shù)字之間進行交換，判斷數(shù)組是否可以變得有序。
初始思路考慮過，構(gòu)建一個數(shù)組表示原始數(shù)組元素二進制形式數(shù)位為1的數(shù)量，構(gòu)建另一個數(shù)組表示排序后的原始數(shù)組二進制形式數(shù)位為1的數(shù)量，并通過Arrays.equals()進行比較。但是，要考慮到特殊情況數(shù)位小的數(shù)字可能比數(shù)位大的數(shù)字要大，例如：4的數(shù)位為1，3的數(shù)位卻為2.

最終考慮到題目要求允許交換二進制中1的數(shù)目相同的相鄰元素，符合動態(tài)連通性的定義，考慮通過并查集解決問題。先克隆一個原始數(shù)組，并對其進行排序，以獲取每個元素應(yīng)該存放的位置，并將相鄰元素間二進制數(shù)位為1數(shù)量相同的進行合并，合并后，對每個位置上的現(xiàn)有元素和應(yīng)存放元素進行查找，判斷這兩個元素是否具有相同的關(guān)鍵元素，從而判斷原始元素是否能夠通過元素交換交換到正確的位置上。

代碼

class Solution {
    public boolean canSortArray(int[] nums) {
        int n = nums.length;
        // nums1 是 nums 的一個副本，用于排序
        int[] nums1 = nums.clone();
        Arrays.sort(nums1);

        // 初始化并查集的數(shù)組
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        // d 是一個映射，用于記錄原數(shù)組中每個數(shù)字的位置
        Map<Integer, Integer> d = new HashMap<>();
        for (int i = 0; i < n; i++) {
            d.put(nums[i], i);
        }

        // 遍歷數(shù)組，將二進制1的數(shù)量相同的相鄰元素合并
        for (int i = 1; i < n; i++) {
            if (Integer.bitCount(nums[i]) == Integer.bitCount(nums[i - 1])) {
                union(parent, i, i - 1);
            }
        }

        // 檢查排序后的數(shù)組是否可以通過交換特定的相鄰元素變?yōu)樵瓟?shù)組的順序
        for (int i = 0; i < n; i++) {
            if (nums[i] != nums1[i] && find(parent, i) != find(parent, d.get(nums1[i]))) {
                return false;
            }
        }
        return true;
    }

    // find 函數(shù)用于查找元素所在集合的代表元素
    private int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }

    // union 函數(shù)用于合并兩個元素所在的集合
    private void union(int[] parent, int x, int y) {
        int fx = find(parent, x);
        int fy = find(parent, y);
        if (fx != fy) {
            parent[fx] = fy;
        }
    }
}

并查集

適用場景：涉及多個元素分組和組間關(guān)系的場景。
動態(tài)連接問題

1. 合并(Union)：
   將兩個符合相同規(guī)則的獨立集合合并為一個集合。

2. 查詢(Find)：
   找到這個集合的"根"，便于我們快速檢查兩個元素是否屬于一個集合。

代碼模板：

...
// 初始化并查集數(shù)組
int[] parent = new int[n];
for(int i = 0;i < n;i++){
	parent[i] = i;// parent[i]表示元素`i`在并查集中的代表元素的位置
}

// find 函數(shù)用于查找元素所在集合的代表元素
private int find(int[] parent,int x){
	if(parent[x] != x){
		parent[x] = find(parent,parent[x]);
	}
	return parent[x];
}

// union 函數(shù)用于合并兩個元素所在的集合
private void union(int[] parent,int x,int y){
	int fx = find(parent,x);
	int fy = find(parent,y);
	if(fx!=fy){
		parent[fx] = fy;
	}
}

三、通過操作使數(shù)組長度最小

題目

給你一個下標(biāo)從 0 開始的整數(shù)數(shù)組 nums ，它只包含 正 整數(shù)。

你的任務(wù)是通過進行以下操作 任意次 （可以是 0 次） 最小化 nums 的長度：

在 nums 中選擇 兩個不同 的下標(biāo) i 和 j ，滿足 nums[i] > 0 且 nums[j] > 0 。
將結(jié)果 nums[i] % nums[j] 插入 nums 的結(jié)尾。
將 nums 中下標(biāo)為 i 和 j 的元素刪除。
請你返回一個整數(shù)，它表示進行任意次操作以后 nums 的 最小長度 。

示例 1：

輸入：nums = [1,4,3,1]
輸出：1
解釋：使數(shù)組長度最小的一種方法是：
操作 1 ：選擇下標(biāo) 2 和 1 ，插入 nums[2] % nums[1] 到數(shù)組末尾，得到 [1,4,3,1,3] ，然后刪除下標(biāo)為 2 和 1 的元素。
nums 變?yōu)?[1,1,3] 。
操作 2 ：選擇下標(biāo) 1 和 2 ，插入 nums[1] % nums[2] 到數(shù)組末尾，得到 [1,1,3,1] ，然后刪除下標(biāo)為 1 和 2 的元素。
nums 變?yōu)?[1,1] 。
操作 3 ：選擇下標(biāo) 1 和 0 ，插入 nums[1] % nums[0] 到數(shù)組末尾，得到 [1,1,0] ，然后刪除下標(biāo)為 1 和 0 的元素。
nums 變?yōu)?[0] 。
nums 的長度無法進一步減小，所以答案為 1 。
1 是可以得到的最小長度。
示例 2：

輸入：nums = [5,5,5,10,5]
輸出：2
解釋：使數(shù)組長度最小的一種方法是：
操作 1 ：選擇下標(biāo) 0 和 3 ，插入 nums[0] % nums[3] 到數(shù)組末尾，得到 [5,5,5,10,5,5] ，然后刪除下標(biāo)為 0 和 3 的元素。
nums 變?yōu)?[5,5,5,5] 。
操作 2 ：選擇下標(biāo) 2 和 3 ，插入 nums[2] % nums[3] 到數(shù)組末尾，得到 [5,5,5,5,0] ，然后刪除下標(biāo)為 2 和 3 的元素。
nums 變?yōu)?[5,5,0] 。
操作 3 ：選擇下標(biāo) 0 和 1 ，插入 nums[0] % nums[1] 到數(shù)組末尾，得到 [5,5,0,0] ，然后刪除下標(biāo)為 0 和 1 的元素。
nums 變?yōu)?[0,0] 。
nums 的長度無法進一步減小，所以答案為 2 。
2 是可以得到的最小長度。
示例 3：

輸入：nums = [2,3,4]
輸出：1
解釋：使數(shù)組長度最小的一種方法是：
操作 1 ：選擇下標(biāo) 1 和 2 ，插入 nums[1] % nums[2] 到數(shù)組末尾，得到 [2,3,4,3] ，然后刪除下標(biāo)為 1 和 2 的元素。
nums 變?yōu)?[2,3] 。
操作 2 ：選擇下標(biāo) 1 和 0 ，插入 nums[1] % nums[0] 到數(shù)組末尾，得到 [2,3,1] ，然后刪除下標(biāo)為 1 和 0 的元素。
nums 變?yōu)?[1] 。
nums 的長度無法進一步減小，所以答案為 1 。
1 是可以得到的最小長度。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109

解題思路

題目要求我們對數(shù)組選取下標(biāo)i,j(nums[i]>0 nums[j]>0)，插入nums[i]%nums[j]，并且刪除nums[i],nums[j]。根據(jù)這個規(guī)則，求出數(shù)組的最小長度。
首先對nums[i]%nums[j]進行分類討論
① nums[i]<nums[j]
nums[i]%nums[j]=nums[i]，最終保留nums[i]，剔除nums[j]，理解為小數(shù)踢大數(shù)
② nums[i]>=nums[j]
A.非整除
顯然nums[i]%nums[j]<nums[j]<=nums[i]，得到一個更小數(shù)，這個更小數(shù)可以提走所有大數(shù)，結(jié)果為1(這也是最優(yōu)情況)
B.整除
如果大數(shù)整除小數(shù)，生成0，會占位置，因為nums[i]=0不能參與規(guī)則，因此考慮小數(shù)整除大數(shù)。并且分類討論奇數(shù)和偶數(shù)個最小值的情況，總結(jié)出規(guī)律(m+1)//2

對規(guī)律進行提煉優(yōu)化，即考慮遍歷所有數(shù)并判斷是否能夠整除最小數(shù)，如果不能，結(jié)果為1;如果能，再獲取最小數(shù)的數(shù)量，并且利用(m+1)//2計算。文章來源地址http://www.zghlxwxcb.cn/news/detail-829445.html

代碼

class Solution {
    public int minimumArrayLength(int[] nums) {
        int m = findMin(nums);
        for (int num : nums) {
            if (num % m != 0) { // 可以產(chǎn)生新的最小值
                return 1;
            }
        }
        int length = count(nums, m);
        return (length + 1) / 2;  // 向上取整
    }

    // 尋找數(shù)組中的最小值
    private int findMin(int[] nums) {
        int minVal = nums[0];
        for (int num : nums) {
            if (num < minVal) {
                minVal = num;
            }
        }
        return minVal;
    }

    // 計算最小值在數(shù)組中出現(xiàn)的次數(shù)
    private int count(int[] nums, int m) {
        int count = 0;
        for (int num : nums) {
            if (num == m) {
                count++;
            }
        }
        return count;
    }
}

到了這里，關(guān)于leetcode 122雙周賽 解題思路+代碼的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！