JavaScript之演算法設計思想

1??排序演算法

一、冒泡排序

1. 比較所有相鄰的元素，如果第一個比第二個大，則交換他們的位置
2. 一輪比較可以保證最后一個數是最大的，然后繼續遍歷剩余的數
3. 代碼實作

const arr = [5,4,3,7,0,2,1]
let temp = 0;
//執行arr.length-1次陣列中冒泡的程序
for(let i = 0; i < arr.length -1; i++){
	//遍歷整個陣列，將陣列中最小的一個移動到陣列最后面
	//因為每一輪回圈后，都是將陣列中最小的移動到后面，所以arr.length-i，陣列末尾已經是最小元素就不再遍歷了
    for(let j = 0; j < arr.length - i; j++){
    //將如果相鄰元素中，第一個比第二個大，則第一個元素向后移
        if(arr[j]>arr[j+1]){
            temp = arr[j+1];
            arr[j+1] = arr[j];
            arr[j] = temp
        }
    }
}

二、選擇排序

1. 找到未排序的陣列中的最小值，將他和第一位互換位置
2. 找到未排序陣列中第二小的值，選中并將其放置在第二位
3. 執行n-1輪后得到的就是一個升序陣列
4. 代碼實作

const arr = [5,4,3,7,0,2,1]
let temp = 0;
//執行arr.length-1次選擇
for(let i = 0; i < arr.length - 1; i++){
	//遍歷整個陣列
	//一輪回圈陣列中最小的元素保證在第一位，后續回圈以此類推
	//所以每一輪回圈結束，陣列前面都是交換出來的最小值
	//使j=i,可以在后續遍歷中忽略前面已經確認的較小值
    for( let j = i; j < arr.length - 1; j++){
    //如果陣列中存在元素小于第一位，則兩者互換位置-
        if(arr[j] > arr[j+1]){
            temp = arr[j+1];
            arr[j+1] = arr[i];
            arr[i] = temp
        }
   
    }    
}

三、插入排序

1. 從第二個數開始往前比
2. 遇到大于自己的就將其（大值）位置向后移一位，小于自己的就插入到這個值后面
3. 以此類推執行n-1次

const arr = [0,5,2,6,1,9]
//因為是從第二位開始比所以i=1開始
for(let i = 1; i < arr.length; i++){
    let temp = arr[i];
    let j = i;
    while( j > 0){
        if( arr[j-1] > temp ){
            //將大于當前元素的值向后移
            arr[j] = arr[j-1]
        }
        //當前元素大于前面元素時跳出回圈，比較下一位
        //這里break跳出的是while回圈，因為前面的元素比較過了，都是有序的陣列，所以當arr[j-1] < temp是可以判斷temp比之前所有的元素都大，跳出本次回圈即可
        else break;
        // j-=1如果放在if前面，當前元素大于前面值時arr[j] = temp依然會將當前元素插入到前面的位置
        //而放在后面break跳出回圈j-=1沒有執行，相當于arr[j] = arr[j],插入操作值未改變
        j -= 1;
    }
//交換元素位置（此時j已經執行了-1操作），如果是通過break跳出來的，實際上j并未發生改變，arr[j] = temp相當于給自身賦值
    arr[j] = temp;
}
//console.log(arr)

四、歸并排序

1. 分：把陣列從中間分成兩半，在不斷遞回的對陣列進行“分”的操作，直到分成一個個只存在單獨數的陣列
2. 合：把不能再分的兩個陣列合并為有序陣列，然后再對有序陣列進行合并，直到全部子陣列合并為一個完整的陣列

合并方法：

1. 新建一個空陣列res用于存放最終排序后的陣列
2. 比較兩個有序陣列的頭部·，較小者出隊（將拆分后的陣列視為為佇列）并推入res陣列中
3. 如果陣列還有值就重復一二步操作

代碼實作

const merge = (arr) => {
    // 如果陣列長度為1,相當于不能再拆分時回傳這些單個陣列
    if(arr.length === 1) {return arr;}
    // 獲取陣列的中間值
    const mid = Math.floor(arr.length / 2)
    // 將陣列從中間拆分成開，記為左右新兩個陣列
    const left = arr.slice(0,mid)
    const right = arr.slice(mid,arr.length)

    // 遞回拆分
    const orderLeft = merge(left)
    const orderRight = merge(right)
    let res = []
    //當拆分后的陣列不為空時
    while(orderLeft.length || orderRight.length){
        // 如果拆分后左右都存在就比較頭元素的大小
        if(orderLeft.length && orderRight.length){
            // 將頭元素較小的取出然后加到res陣列中
            res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
            // 拆分后只有左邊陣列存在
        }else if(orderLeft.length){
            res.push(orderLeft.shift())
            // 拆分后只有右邊陣列存在
        }else if(orderRight.length){
            res.push(orderRight.shift())
        }
    }
    return res;
}
const arr = [1,4,3,9,2]
console.log(merge(arr))

五、快速排序

1. 磁區： 從陣列中任意選擇一個基準，比基準大的元素放在基準后面，比基準小的元素放在基準前面
2. 遞回： 磁區后得到的陣列左邊都比基準值小，右邊都比基準值大，然后遞回的對基準值前后的子陣列再進行磁區

代碼實作

const fastSort = (arr) => {
    if(arr.length === 0) {return arr;}
    // 定義左右兩個陣列，大于基準的放右邊陣列，小于基準的放左邊基準
    const left = []
    const right = []
    // 基準是隨機挑選的一個數
    const stand = arr[0]
    // 因為陣列第一個數被挑出來作為基準了，所以這里i從1開始
    for(let i = 1; i < arr.length; i++){
        if(arr[i] < stand){
            left.push(arr[i])
        }else{
            right.push(arr[i])
        }
    }
    // 這里左陣列、右陣列、基準為三個獨立的部分，需要將三者合成一個陣列
    //...是ES6中新增的擴展運算子，陣列中的擴展運算子(…)用于取出引數陣列中的所有可遍歷屬性，拷貝到當前陣列之中，
    return [...fastSort(left),stand,...fastSort(right)]
}
const arr = [1,4,0,3,7]
console.log(fastSort(arr))

但是其實這種快速排序方法是錯誤的，雖然也是利用快速排序的原理左右磁區然后遞回，但是使用了兩個陣列，空間復雜度增加

下面因該是比較貼切一點的快速排序，可以使用console.time()方法來測驗一下排序用時

// 計算程式執行時間
console.time('a')
// 函式傳入三個引數，依次是：待排序的陣列，待排序陣列左邊第一個元素的索引，待排序元素右邊得第一個元素的索引
const fastSort = (arr,began,end) => {  
    // 取陣列的第一個元素為基準值
    let print = arr[began]
    //如果不定義i,j 直接改變began,end的值,會影響后面遞回開始和結束的索引值
    let i = began;
    let j = end;
    //當左邊的索引值大于右邊的時,說明本輪排序結束
    if(began >= end) {
        // 將本輪排序后的陣列回傳
        return arr
    }
    //把所有比基準值小的元素放在基準值左邊,大的元素放在基準值右邊
    while(i < j){
        // 從后往前查找到比基準值小的元素交換
        //繼續判斷i<j是因為：如果print值較小,arr[j]>print會持續成立，導致j<=i,索引j<=i表示整個陣列已經排序結束
        while(arr[j] >= print && i < j){
            j--
        }
        // 比基準值小的元素放左邊,如果不存在比基準值小的元素,此時j=i相當于自身給自身賦值
        arr[i] = arr[j] 
        // 找到比基準值大的元素交換
        // 繼續判斷i<j，因為print值較大時，arr[i] <= print會持續成立，導致j<=i
        while(arr[i] <= print && i < j){
            i++
        }
        // 比基準值大的元素放在右邊,如果不存在比基準值大的元素,此時i=j相當于自身給自身賦值
        arr[j] = arr[i]       
    }
    //一次回圈結束,將基準值放在中間位置（此時i=j，arr[i]或者arr[j]都可以）
    arr[j] = print
    //遞回,繼續對基準值左右兩邊的陣列進行排序
    // 這里began不能直接傳入0，會影響到第三輪之后的遞回，
    // 因為對基準值右邊的陣列再進行磁區排序時也會使用到began，而此時began并不是0
    fastSort(arr,began,j-1)
    fastSort(arr,j+1,end)
    //回傳排序后的陣列
    return arr
}	 	  
const arr = [9,5,1,4,8]
console.log(fastSort(arr,0,arr.length-1))
console.timeEnd('a')

之所以從右邊開始排序，是因為基準值選擇的是最左邊，舉個例子7 1 2 3 4執行快速排序，假如從左開始排，就會出現1，7，2，3，4

附：這里有一個25w個資料的亂序陣列（有重復），可以用來測驗這些排序演算法的速度 https://download.csdn.net/download/aaahuahua/34715763

2??查找方法

搜索：js中通常使用indexOf方法（回傳元素在陣列中的下標，不存在返會-1）

一、順序查找

1. 遍歷陣列
2. 找到和目標值相等的元素，回傳下標
3. 遍歷所有值后如果沒有目標值回傳-1

代碼實作

// 在Array陣列原型上添加一個方法
Array.prototype.searchWay = function (item){
// this指代這個陣列
    for(let i = 0; i < this.length; i++){
        if(item === this[i]){
            return i
        }
    }
    return -1
}
const arr = [1,3,5,2,9]
//呼叫searchWay方法
console.log(arr.searchWay(5))

二、二分查找

前提： 查找的是有序陣列

如果是一個無序陣列，需要先將其化為有序陣列之后再進行二分搜索

搜索方法

1. 從中間元素開始，如果正好是目標值，則搜索結束
2. 如果目標值小于或者大于中間元素，則在大于或者小于目標值的部分陣列中繼續進行搜索

// 在陣列的原型上添加一個search方法
Array.prototype.search = function (item){4
    // 定義查找的起始位置和結束位置
    let low = 0;
    let height = this.length - 1;
    // 等于號用于判斷陣列中只剩下最后一個數時，是否為目標值
    while(low <= height){
        // 選取陣列中間元素為基準值
        let mid = Math.floor((low + height) / 2);
        const num = this[mid]
        // 如果目標值就是基準值則回傳基準值的下標
        if(item === num){    
            return console.log(mid)
        }else if(item > num){ //當目標值大于基準值時，將查找范圍縮小為基準值右邊的陣列
            low = mid + 1
        }else if(item < num ){//當目標值小于基準值時，將查找范圍縮小為基準值左邊的陣列
            height = mid - 1
        }
    }
    // 查找結束后如果還是沒有找到目標元素，則回傳該元素不存在
    return console.log("該元素不存在")
}
//呼叫陣列原型上的search方法
const arr = [1,2,3,4,5].search(0)

3??演算法設計思想

一、動態規劃

將一個問題分解成相互重疊的子問題，通過反復求解子問題，來解決原來的問題

步驟：

1. 定義子問題
2. 回圈執行子問題中定義的公式

實戰練習

假設你正在爬樓梯，需要 n 階你才能到達樓頂，
每次你可以爬 1 或 2 個臺階，你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個正整數，

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂，
1 階 + 1 階 + 1 階
1 階 + 2 階
2 階 + 1 階

動態規劃

1. 定義子問題，到達第n階可以有兩種方法
   （1）從第n-1階爬一階
   （2）從第n-2階爬兩階

所以到達第n階的方法就是到達第n-1階的方法加上到達第n-2階方法之和:F(n)=F(n-1)+F(n-2)

2. 從n=2開始回圈執行F(n)=F(n-1)+F(n-2)

代碼實作

var climbStairs = function(n) {
//當階數小于2，也就是1階時，直接回傳1（n為正整數所以不存在復數的情況）
    if(n<2) return 1;
//定義陣列dp存放到達每一階的方法數，下標代表階數，對應值為到達改階的方法數
//雖然這里0階定義的是1，但是n為正整數，不會存在n=0的情況
    const dp = [1,1];
//因為前兩次已經被列舉出來了，所以i從2開始
    for(let i = 2;i <= n; i++){
        dp[i]=dp[i-1]+dp[i-2]
    }
    return dp[n]
};

//代碼優化，因為定義了陣列，所以空間復雜度為O(n),可以只定義兩個變數將復雜度降到O(1)
var climbStairs = function(n) {
    if(n<2) return 1;
    const dp0 = 1;
    const dp1 = 1;
    for(let i = 2;i <= n; i++){
    //臨時存盤到達第n-2階的方法
        const temp = dp0;
        dp0 = dp1;
        dp1 = temp + dp1;
    }
    return dp1;
};

二、分而治之

將原問題分為很多個相似的小問題，遞回的解決這些小問題，然后再將結果合并以解決原有的問題

1. 設計案例之歸并排序

• 分：將陣列一分為二
• 解：遞回的對兩個子陣列進行歸并排序
• 合：合并有序陣列（將遞回后長度為1的陣列合并成有序陣列，然后再把這些有序陣列繼續合并）

2. 設計案例之快速排序

• 分：選擇基準值將原陣列分成大于基準值和小于基準值的兩個陣列
• 解：遞回的對兩個子陣列進行快速排序
• 合：遞回到陣列中只剩下一個·元素時排序完畢，回傳該陣列即可

實戰練習

猜數字游戲的規則如下：

每輪游戲，都會從 1 到 n 隨機選擇一個數字， 請你猜選出的是哪個數字，如果你猜錯了，我會告訴你，你猜測的數字比我選出的數字是大了還是小了，

你可以通過呼叫一個預先定義好的介面 int guess(int num) 來獲取猜測結果，回傳值一共有 3 種可能的情況（-1，1 或 0）：

1. -1：選出的數字比你猜的數字小 pick < num
2. 1：選出的數字比你猜的數字大 pick > num
3. 0：選出的數字和你猜的數字一樣，恭喜！你猜對了！pick == num 回傳選出的數字，

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/guess-number-higher-or-lower

示例 1： 輸入：n = 10, pick = 6 輸出：6
示例 2：輸入：n = 1, pick = 1 輸出：1
示例 3：輸入：n = 2, pick = 1 輸出：1
示例 4：輸入：n = 2, pick = 2 輸出：2

解題思路：

使用二分搜索，分，解，和，利用分而治之的思想來做

1. 分：計算中間元素，分割陣列
2. 解：遞回的在較大的或者較小的陣列中進行二分搜索
3. 合：這一步可以省略，因為如果在子陣列中搜索到目標值后就直接將其回傳了

代碼實作：

var guessNumber = function(n) {
//這里定義一個二分查找的函式
    const divide = (low,height) => {
    //當最小值大于最大值時直接return
        if(low > height) return;
        //取兩個數的中間值
        const mid = Math.floor((low+height)/2);
        //呼叫介面判斷猜測結果是否正確
        const res = guess(mid);
        if(res === 0 ){
            return mid
        }else if(res === -1){
        //猜測結果小于真實值
            return divide(1,mid-1)
        }else if(res === 1 ){
        //猜測結果大于真實值
            return divide(mid+1,height)
        }
    }
    return divide(1,n)
};

對稱二叉樹

給定一個二叉樹，檢查它是否是鏡像對稱的，

例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的，

但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/symmetric-tree

解題思路：

可以轉換為左右子樹是否為鏡像的，然后分解為樹1的左子樹和樹2的右子樹是否為互為鏡像，樹1右子樹和樹2的左子樹是否為互為鏡像

代碼實作：

var isSymmetric = function(root) {
//如果二叉樹為空，回傳為true
  if(!root) return true;
  //定義一個鏡像判斷函式
  const isCheck = (left,right) => {
  //如果左右子樹都不存在，回傳為true
      if(!right && !left){
          return true
      }
      //左右子樹存在，值相等，遞回左右子節點
      if(right && left && right.val === left.val &&
        isCheck(left.left,right.right) &&
        isCheck(left.right,right.left)
      ){
          return true
      }
      //其他情況下回傳false
      return false
  }
    return isCheck(root.left,root.right)
}; 

三、貪心演算法

期盼通過每個階段的區域最優選擇，從而達到全域的最優，但是結果有可能并不是最優的

分發餅干

假設你是一位很棒的家長，想要給你的孩子們一些小餅干，但是，每個孩子最多只能給一塊餅干，

對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j] ，如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足，你的目標是盡可能滿足越多數量的孩子，并輸出這個最大數值，

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/assign-cookies

示例1：

輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋: 你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3，
雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足， 所以你應該輸出1，

示例2：

輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋:
你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2，
你擁有的餅干數量和尺寸都足以讓所有孩子滿足，
所以你應該輸出2.

解題思路：

區域最優：分發的餅干既能滿足孩子，還消耗最少，即先將較小的餅干分給胃口小的孩子

解題步驟：

1. 對餅干陣列和胃口陣列進行升序排序
2. 遍歷餅干陣列，找到能滿足第一個孩子（胃口最小的孩子）的餅干
3. 繼續遍歷餅干陣列，找到剩下能滿足第二、第三、第四…個孩子的餅干

代碼實作：

var findContentChildren = function(g,s) {
//快速排序
    const fastSort = (arr,began,end) => {
        let print = arr[began]
        let i = began;
        let j = end;
        if(began >= end){
            return arr;
        }
        while(i < j){
            while(arr[j] >= print && i < j){
                j--
            }
            arr[i] = arr[j]
            while(arr[i] <= print && i < j){
                i++
            }
            arr[j] = arr[i];
        }
        arr[j] = print;
        fastSort(arr,began,j-1)
        fastSort(arr,j+1,end)
        return arr
    } 
    //對小孩的胃口和餅干尺寸兩個陣列進行排序
    fastSort(s,0,s.length-1)
    fastSort(g,0,g.length-1)
    //定義能滿足的小孩個數
    let i = 0;
    //遍歷所有餅干
    s.forEach(item =>{
    //如果餅干尺寸大于小孩的胃口，能滿足的小孩數加1
        if(item >= g[i]){
            i+=1
        }
    })
    //回傳滿足的小孩個數
    return i
};

四、回溯演算法

一種漸進式尋找并構建問題解決方式的策略，即從一個可能的情況開始解決問題，如果不行，就回溯到另一種情況，直到問題被解決（也可以理解為暴力破解）

回溯思路

1. 使用遞回模擬出所有的情況
2. 遇到不滿足條件的情況就回溯
3. 收集所有能到達遞回終點的情況，并回傳

實戰練習

全排列規則如下：

給定一個不含重復數字的陣列 nums ，回傳其 所有可能的全排列 ，你可以 按任意順序回傳答案，

示例 1：

輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
輸入：nums = [0,1]
輸出：[[0,1],[1,0]]

示例 3：
輸入：nums = [1]
輸出：[[1]]

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/permutations

代碼實作

var permute = function(nums) {
	//定義結果集
    let res = []
    //定義已排列結果
    let way = []
    //used（標記陣列），用于記錄當前該元素是否已經被添加到已排列陣列（way）中了
    const backtrack = (arr,used) =>{
    //遞回結束條件，當已排列陣列的長度等于原陣列長度時，表明所有元素都已經被添加到已排列陣列中了
        if(way.length === arr.length) {
            //將本次排列的結果添加到結果集中
            res.push([...way])
            return;
        }
        // 遍歷陣列
        for(let i = 0; i < arr.length; i++){

    // if(way.indexOf(arr[i]) != -1)
    //  不使用這個方法是因為查找的時間復雜度為O(n)，同樣的引入used陣列會增加空間復雜度也是O(n)

            // undefind轉換為布林值是false
            if(used[i])  // 判斷該元素是否已經存在于已排列陣列中
            continue;
            //向結果集中添加元素
            way.push(arr[i])
            //標記該元素為已添加，使下一層遍歷能夠區分哪些元素是未排列的剩余元素
            used[i] = true
            // 遞回遍歷陣列，遞回遍歷arr.length次就可以將陣列中的元素全部添加到排列陣列中
            backtrack(arr,used)
            // 這個是本次全排列中回溯的重要體現
            // 使用pop方法洗掉已經添加到排列陣列中的元素，可以使排列程序回到上一層遞回
            way.pop()
            // 洗掉已經添加到排列陣列中的元素標記
            used[i] = false
        }    
    }
    backtrack(nums,[])
    return res
};

子集規則如下

給你一個整數陣列 nums ，陣列中的元素 互不相同 ，回傳該陣列所有可能的子集（冪集），
解集不能包含重復的子集，你可以按任意順序回傳解集，

示例 1：
輸入：nums = [1,2,3]
輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：
輸入：nums = [0]
輸出：[[],[0]]

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/subsets

代碼實作

const subsets = (nums) => {
    const res = [];
    const sun = (index, temp) => {
      if (index == nums.length) { // 索引等于陣列長度時
        res.push(temp.slice());   // 加入解集
        return;                   // 結束當前的遞回
      }
      temp.push(nums[index]); // 將該元素加入陣列
      sun(index + 1, temp);   // 往下遞回，添加剩余元素
      temp.pop();             // 上面的遞回結束，逐步洗掉已經添加過的元素
      // 洗掉已添加的元素后，將剩余結果加入結果集；操作剩余元素
      sun(index + 1, temp);   
    };
    sun(0, []);
    return res;
  };