4.力扣-數組-數組的改變、移動

力扣-數組-數組的改變、移動

最小操作次數使數組元素相等（LeetCode453）

• 題目概述：給定一個長度為 n 的 非空 整數數組，每次操作将會使 n - 1 個元素增加 1。找出讓數組所有元素相等的最小操作次數。

• 題目示例：

  示例：

  輸入：

  [1,2,3]

  輸出：

  3

  解釋：

  隻需要3次操作（注意每次操作會增加兩個元素的值）：

  [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

• 方法一：利用排序

  利用排序再結合改進暴力法的思路，可以直接與數組中最小的進行比較，即排序過後的nums[0]

• JS代碼

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves = function(nums) {
    nums.sort((a,b)=>a-b)
    let count=0
    nums.forEach((num)=> {
        count+=num-nums[0]
    })
    return count
};
           

• Java代碼

class Solution {
    public int minMoves(int[] nums) {
        Arrays.sort(nums);
        int count=0;
        for(int num:nums) {
            count+=num-nums[0];
        }
        return count;
    }
}
           

• 方法二：動态規劃

  如果對數組進行排序得到有序數列 a，可以有效地簡化問題。考慮有序數組 a，我們不考慮整個問題，而是将問題分解。假設，直到 i-1 位置的元素都已經相等，我們隻需要考慮 i 位的元素，将內插補點 diff=a[i]-a[i-1] 加到總移動次數上，使得第 i 位也相等。moves=moves+diff。

  但當我們想要繼續這一步時，a[i] 之後的元素也會被增加 diff，亦即 a[j]=a[j]+diff，其中 j>i。

  但當實作本方法時，我們不需要對這樣的 a[j] 進行增加。相反，我們把 moves 的數量增加到目前元素（a[i]）中，a’[i]=a[i]+moves。

  簡而言之，我們對數列進行排序，一直更新 moves 以使得直到目前的元素相等，而不改變除了目前元素之外的元素。在整個數組掃描完畢後，moves 即為答案。

• java代碼

public class Solution {
    public int minMoves(int[] nums) {
        Arrays.sort(nums);
        int moves = 0;
        for (int i = 1; i < nums.length; i++) {
            int diff = (moves + nums[i]) - nums[i - 1];
            //因為要和前一個進行比較，是以要進行數組的元素修改
            //加過之後就等于前i-1位保持一緻
            nums[i] += moves;
            //a[i] 之後的元素也會被增加 diff，是以move是累加的
            moves += diff;
        }
        return moves;
    }
}
           

非遞減數列（LeetCode665）

• 題目概述：給你一個長度為 n 的整數數組，請你判斷在 最多 改變 1 個元素的情況下，該數組能否變成一個非遞減數列。

  我們是這樣定義一個非遞減數列的： 對于數組中任意的 i (0 <= i <= n-2)，總滿足 nums[i] <= nums[i + 1]。

• 題目示例：

  

• 方法一：數組

  首先思考問題：要使數組變成一個非遞減數列，數組中至多有多少個 i 滿足 nums[i]>nums[i+1]？——至多一個

  但會出現一個問題，就是例如數組 [3,4,1,2],無論怎麼修改也無法将其變成非遞減數列，是以要對發現問題的數組進行修改然後進行判斷是否滿足要求

  這時就會出現第二個問題，修改誰，修改為多少

  第一種：可以将nums[i]修改成小于或等于nums[i+1]的數，又得保證nums[i]不小于前面的數，是以nums[i]越大越好，是以最好修改為nums[i+1]

  第二種：同理可以修改nums[i+1]為nums[i]的值

  注意：這裡必須兩種都要驗證，否則就會出現考慮不周的現象，例如數組[4,2,3]，數組[5,7,1,8]

• java代碼

class Solution {
    public boolean checkPossibility(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; ++i) {
            int x = nums[i], y = nums[i + 1];
            if (x > y) {
                nums[i] = y;
                if (isSorted(nums)) {
                    return true;
                }
                nums[i] = x; // 複原
                nums[i + 1] = x;
                return isSorted(nums);
            }
        }
        return true;
    }

    public boolean isSorted(int[] nums) {
        int n = nums.length;
        for (int i = 1; i < n; ++i) {
            if (nums[i - 1] > nums[i]) {
                return false;
            }
        }
        return true;
    }
}
           

• JS代碼

var checkPossibility = function(nums) {
    const n = nums.length;
    for (let i = 0; i < n - 1; ++i) {
        const x = nums[i], y = nums[i + 1];
        if (x > y) {
            nums[i] = y;
            if (isSorted(nums)) {
                return true;
            }
            nums[i] = x; // 複原
            nums[i + 1] = x;
            return isSorted(nums);
        }
    }
    return true;
};

const isSorted = (nums) => {
    const n = nums.length;
    for (let i = 1; i < n; ++i) {
        if (nums[i - 1] > nums[i]) {
            return false;
        }
    }
    return true;
}
           

• 方法二：數組優化

  優化在減少多周遊nums數組

  當nums[i]修改為nums[i+1]後，還需保證nums[i-1]<=nums[i],即要保證nums[i+1]>=nums[i-1],否則即要修改nums[i+1]為nums[i]，接着判斷後續數字的大小關系

• java代碼

class Solution {
    public boolean checkPossibility(int[] nums) {
        int n = nums.length, cnt = 0;
        for (int i = 0; i < n - 1; ++i) {
            int x = nums[i], y = nums[i + 1];
            if (x > y) {
                cnt++;
                if (cnt > 1) {
                    return false;
                }
                if (i > 0 && y < nums[i - 1]) {
                    nums[i + 1] = x;
                }
            }
        }
        return true;
    }
}