萬字總結 JS 數據結構與常用的算法

一、前言

首先，爲什麼我會學習數據結構與算法呢，其實主要是有兩方面

第一，是我在今年的 flag 裏明確說到我會學這個東西
第二，學了這些，對自己以後在工作或者面試也會帶來許多好處

然後，本文是最近學習的一個總結文章，文中有不足的地方也希望大家在評論區進行指正，本文較長，設有目錄。可直接通過目錄跳轉閱讀。

文中的算法題，大部分都是 leetcode 中的，如不太理解題意，可直接去 leetcode 中找到對應的題。

二、基本概念

常常聽到算法的時候，就會有人說到 時間複雜度， 空間複雜度。那麼這倆玩意是啥呢，下面我就來一一解釋

時間複雜度

其實就是一個函數，用大 O 表示，比如 O(1)、 O(n)...

它的作用就是用來定義描述算法的運行時間

O(1)

    let i = 0
    i += 1
複製代碼

O(n)： 如果是 O(1) + O(n) 則還是 O(n)

    for (let i = 0; i < n; i += 1) {
      console.log(i)
    }
複製代碼

O(n^2)： O(n) * O(n), 也就是雙層循環，自此類推：O(n^3)...

    for (let i = 0; i < n; i += 1) {
      for (let j = 0; j < n; j += 1) {
        console.log(i, j)
      }
    }
複製代碼

O(logn)： 就是求 log 以 2 爲底的多少次方等於 n

    // 這個例子就是求2的多少次方會大於i，然後就會結束循環。 這就是一個典型的 O(logn)
    let i = 1
    while (i < n) {
      console.log(i)
      i *= 2
    }
複製代碼

空間複雜度

和時間複雜度一樣，空間複雜度也是用大 O 表示，比如 O(1)、 O(n)...

它用來定義描述算法運行過程中臨時佔用的存儲空間大小

佔用越少代碼寫的就越好

O(1)： 單個變量，所以佔用永遠是 O(1)

    let i = 0
    i += 1
複製代碼

O(n)： 聲明一個數組，添加 n 個值，相當於佔用了 n 個空間單元

    const arr = []
    for (let i = 0; i < n; i += 1) {
      arr.push(i)
    }
複製代碼

O(n^2)： 類似一個矩陣的概念，就是二維數組的意思

    const arr = []
    for (let i = 0; i < n; i += 1) {
      arr.push([])
      for (let j = 0; j < n; j += 1) {
        arr[i].push(j)
      }
    }
複製代碼

三、數據結構

一個後進先出的數據結構

按照常識理解就是有序的擠公交，最後上車的人會在門口，然後門口的人會最先下車

js 中沒有棧的數據類型，但我們可以通過 Array 來模擬一個

const stack = [];

stack.push(1); // 入棧
stack.push(2); // 入棧

const item1 = stack.pop();  //出棧的元素
複製代碼

1）十進制轉二進制

// 時間複雜度 O(n) n爲二進制的長度
// 空間複雜度 O(n) n爲二進制的長度
const dec2bin = (dec) => {
  // 創建一個字符串
  let res = "";

  // 創建一個棧
  let stack = []

  // 遍歷數字 如果大於0 就可以繼續轉換2進制
  while (dec > 0) {
    // 將數字的餘數入棧
    stack.push(dec % 2);

    // 除以2
    dec = dec >> 1;
  }

  // 取出棧中的數字
  while (stack.length) {
    res += stack.pop();
  }

  // 返回這個字符串
  return res;
};
複製代碼

2）判斷字符串的有效括號

// 時間複雜度O(n) n爲s的length
// 空間複雜度O(n)
const isValid = (s) => {

  // 如果長度不等於2的倍數肯定不是一個有效的括號
  if (s.length % 2 === 1) return false;

  // 創建一個棧
  let stack = [];

  // 遍歷字符串
  for (let i = 0; i < s.length; i++) {

    const c = s[i];

    // 如果是左括號就入棧
    if (c === '(' || c === "{" || c === "[") {
      stack.push(c);
    } else {

      // 如果不是左括號 且棧爲空 肯定不是一個有效的括號 返回false
      if (!stack.length) return false

      // 拿到最後一個左括號
      const top = stack[stack.length - 1];

      // 如果是右括號和左括號能匹配就出棧
      if ((top === "(" && c === ")") || (top === "{" && c === "}") || (top === "[" && c === "]")) {
        stack.pop();
      } else {

        // 否則就不是一個有效的括號
        return false
      }
    }

  }
  return stack.length === 0;
};
複製代碼

隊列

和棧相反 先進先出的一個數據結構

按照常識理解就是銀行排號辦理業務, 先去領號排隊的人, 先辦理業務

同樣 js 中沒有棧的數據類型，但我們可以通過 Array 來模擬一個

const queue = [];

// 入隊
queue.push(1);
queue.push(2);

// 出隊
const first = queue.shift();
const end = queue.shift();
複製代碼

1）最近的請求次數

var RecentCounter = function () {
  // 初始化隊列
  this.q = [];
};

// 輸入 inputs = [[],[1],[100],[3001],[3002]] 請求間隔爲 3000ms
// 輸出 outputs = [null,1,2,3,3]   

// 時間複雜度 O(n) n爲剔出老請求的長度
// 空間複雜度 O(n) n爲最近請求的次數
RecentCounter.prototype.ping = function (t) {
  // 如果傳入的時間小於等於最近請求的時間，則直接返回0
  if (!t) return null

  // 將傳入的時間放入隊列
  this.q.push(t);

  // 如果隊頭小於 t - 3000 則剔除隊頭
  while (this.q[0] < t - 3000) {
    this.q.shift();
  }

  // 返回最近請求的次數
  return this.q.length;
};
複製代碼

鏈表

多個元素組成的列表，元素存儲不連續，通過 next 指針來鏈接, 最底層爲 null

就類似於 父輩鏈接關係 吧，比如：你爺爺的兒子是你爸爸，你爸爸的兒子是你，而你假如目前還沒有結婚生子，那你就暫時木有兒子

js 中類似於鏈表的典型就是原型鏈, 但是 js 中沒有鏈表這種數據結構，我們可以通過一個 object 來模擬鏈表

const a = {
  val: "a"
}

const b = {
  val: "b"
}

const c = {
  val: "c"
}

const d = {
  val: "d"
}

a.next = b;
b.next = c;
c.next = d;

// const linkList = {
//    val: "a",
//    next: {
//        val: "b",
//        next: {
//            val: "c",
//            next: {
//                val: "d",
//                next: null
//            }
//        }
//    }
// }

// 遍歷鏈表
let p = a;
while (p) {
  console.log(p.val);
  p = p.next;
}

// 插入
const e = { val: 'e' };
c.next = e;
e.next = d;


// 刪除
c.next = d;
複製代碼

1）手寫 instanceOf

const myInstanceOf = (A, B) => {
  // 聲明一個指針
  let p = A;
  
  // 遍歷這個鏈表
  while (p) {
    if (p === B.prototype) return true;
    p = p.__proto__;
  }

  return false
}

myInstanceOf([], Object)
複製代碼

2）刪除鏈表中的節點

// 時間複雜和空間複雜度都是 O(1)
const deleteNode = (node) => {
  // 把當前鏈表的指針指向下下個鏈表的值就可以了
  node.val = node.next.val;
  node.next = node.next.next
}
複製代碼

3）刪除排序鏈表中的重複元素

// 1 -> 1 -> 2 -> 3 -> 3 
// 1 -> 2 -> 3 -> null

// 時間複雜度 O(n) n爲鏈表的長度
// 空間複雜度 O(1)
const deleteDuplicates = (head) => {

  // 創建一個指針
  let p = head;

  // 遍歷鏈表
  while (p && p.next) {

    // 如果當前節點的值等於下一個節點的值
    if (p.val === p.next.val) {

      // 刪除下一個節點
      p.next = p.next.next
    } else {

      // 否則繼續遍歷
      p = p.next
    }
  }

  //  最後返回原來鏈表
  return head
}
複製代碼

4）反轉鏈表

// 1 -> 2 -> 3 -> 4 -> 5 -> null
// 5 -> 4 -> 3 -> 2 -> 1 -> null

// 時間複雜度 O(n) n爲鏈表的長度
// 空間複雜度 O(1)
var reverseList = function (head) {

  // 創建一個指針
  let p1 = head;

  // 創建一個新指針
  let p2 = null;

  // 遍歷鏈表
  while (p1) {

    // 創建一個臨時變量
    const tmp = p1.next;

    // 將當前節點的下一個節點指向新鏈表
    p1.next = p2;

    // 將新鏈表指向當前節點
    p2 = p1;

    // 將當前節點指向臨時變量
    p1 = tmp;
  }

  // 最後返回新的這個鏈表
  return p2;
}

reverseList(list
複製代碼

集合

一種無序且唯一的數據結構

ES6 中有集合 Set 類型

const arr = [1, 1, 1, 2, 2, 3];

// 去重
const arr2 = [...new Set(arr)];

// 判斷元素是否在集合中
const set = new Set(arr);
set.has(2) // true

//  交集
const set2 = new Set([1, 2]);
const set3 = new Set([...set].filter(item => set.has(item)));
複製代碼

1）去重

具體代碼在上面介紹中有寫過，就不再重寫了

2）兩個數組的交集

// 時間複雜度 O(n^2) n爲數組長度
// 空間複雜度 O(n)  n爲去重後的數組長度
const intersection = (nums1, nums2) => {

  // 通過數組的filter選出交集
  // 然後通過 Set集合 去重 並生成數組
  return [...new Set(nums1.filter(item => nums2.includes(item)))];
}
複製代碼

字典

與集合類似，一個存儲唯一值的結構, 以鍵值對的形式存儲

js 中有字典數據結構就是 Map 類型

1）兩數之和

// nums = [2, 7, 11, 15] target = 9

// 時間複雜度O(n) n爲nums的length
// 空間複雜度O(n)
var twoSum = function (nums, target) {

  // 建立一個字典數據結構來保存需要的值
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
  
    // 獲取當前的值，和需要的值
    const n = nums[i];
    const n2 = target - n;
    
    // 如字典中有需要的值，就匹配成功
    if (map.has(n2)) {
      return [map.get(n2), i];
    } else {
    
    // 如沒有，則把需要的值添加到字典中
      map.set(n, i);
    }
  }
};
複製代碼

2）兩個數組的交集

// nums1 = [1,2,2,1], nums2 = [2,2]
// 輸出：[2]

// 時間複雜度 O(m + n) m爲nums1長度 n爲nums2長度
// 空間複雜度 O(m) m爲交集的數組長度
const intersection = (nums1, nums2) => {
  // 創建一個字典
  const map = new Map();

  // 將數組1中的數字放入字典
  nums1.forEach(n => map.set(n, true));

  // 創建一個新數組
  const res = [];

  // 將數組2遍歷 並判斷是否在字典中
  nums2.forEach(n => {
    if (map.has(n)) {
      res.push(n);

      // 如果在字典中，則刪除該數字
      map.delete(n);
    }
  })

  return res;
};
複製代碼

3）字符的有效的括號

// 用字典優化

// 時間複雜度 O(n) n爲s的字符長度
// 空間複雜度 O(n) 
const isValid = (s) => {

  // 如果長度不等於2的倍數肯定不是一個有效的括號
  if (s.length % 2 !== 0) return false

  // 創建一個字典
  const map = new Map();
  map.set('(', ')');
  map.set('{', '}');
  map.set('[', ']');

  // 創建一個棧
  const stack = [];

  // 遍歷字符串
  for (let i = 0; i < s.length; i++) {

    // 取出字符
    const c = s[i];

    // 如果是左括號就入棧
    if (map.has(c)) {
      stack.push(c)
    } else {

      // 取出棧頂
      const t = stack[stack.length - 1];

      // 如果字典中有這個值 就出棧
      if (map.get(t) === c) {
        stack.pop();
      } else {

        // 否則就不是一個有效的括號
        return false
      }

    }

  }

  return stack.length === 0;
};
複製代碼

4）最小覆蓋字串

// 輸入：s = "ADOBECODEBANC", t = "ABC"
// 輸出："BANC"


// 時間複雜度 O(m + n) m是t的長度 n是s的長度
// 空間複雜度 O(k) k是字符串中不重複字符的個數
var minWindow = function (s, t) {
  // 定義雙指針維護一個滑動窗口
  let l = 0;
  let r = 0;

  // 建立一個字典
  const need = new Map();

  //  遍歷t
  for (const c of t) {
    need.set(c, need.has(c) ? need.get(c) + 1 : 1)
  }

  let needType = need.size

  // 記錄最小子串
  let res = ""

  // 移動右指針
  while (r < s.length) {
  
    // 獲取當前字符
    const c = s[r];

    // 如果字典裏有這個字符
    if (need.has(c)) {
    
      // 減少字典裏面的次數
      need.set(c, need.get(c) - 1);

      // 減少需要的值
      if (need.get(c) === 0) needType -= 1;
    }

    // 如果字典中所有的值都爲0了 就說明找到了一個最小子串
    while (needType === 0) {
    
      // 取出當前符合要求的子串
      const newRes = s.substring(l, r + 1)

      // 如果當前子串是小於上次的子串就進行覆蓋
      if (!res || newRes.length < res.length) res = newRes;

      // 獲取左指針的字符
      const c2 = s[l];

      // 如果字典裏有這個字符
      if (need.has(c2)) {
        // 增加字典裏面的次數
        need.set(c2, need.get(c2) + 1);

        // 增加需要的值
        if (need.get(c2) === 1) needType += 1;
      }
      l += 1;
    }
    r += 1;
  }
  return res
};
複製代碼

一種分層數據的抽象模型，比如 DOM 樹、樹形控件等

js 中沒有樹但是可以用 Object 和 Array 構建樹

1）普通樹

// 這就是一個常見的普通樹形結構
const tree = {
  val: "a",
  children: [
    {
      val: "b",
      children: [
        {
          val: "d",
          children: [],
        },
        {
          val: "e",
          children: [],
        }
      ],
    },
    {
      val: "c",
      children: [
        {
          val: "f",
          children: [],
        },
        {
          val: "g",
          children: [],
        }
      ],
    }
  ],
}
複製代碼

> 深度優先遍歷

儘可能深的搜索樹的分支, 就比如遇到一個節點就會直接去遍歷他的子節點，不會立刻去遍歷他的兄弟節點
口訣：
訪問根節點
對根節點的 children 挨個進行深度優先遍歷

// 深度優先遍歷
const dfs = (tree) => {
  tree.children.forEach(dfs)
};
複製代碼

> 廣度優先遍歷

先訪問離根節點最近的節點, 如果有兄弟節點就會先遍歷兄弟節點，再去遍歷自己的子節點
口訣
新建一個隊列並把根節點入隊
把隊頭出隊並訪問
把隊頭的 children 挨個入隊
重複第二、三步直到隊列爲空

// 廣度優先遍歷
const bfs = (tree) => {
  const q = [tree];

  while (q.length > 0) {
    const n = q.shift()
    console.log(n.val);
    n.children.forEach(c => q.push(c))
  }
};
複製代碼

2）二叉樹

樹中每個節點 最多隻能有兩個子節點

 const bt = {
  val: 1,
  left: {
    val: 2,
    left: null,
    right: null
  },
  right: {
    val: 3,
    left: {
      val: 4,
      left: null,
      right: null
    },
    right: {
      val: 5,
      left: null,
      right: null
    }
  }
}
複製代碼

> 二叉樹的先序遍歷

訪問根節點
對根節點的左子樹進行先序遍歷
對根節點的右子樹進行先序遍歷

// 先序遍歷 遞歸
const preOrder = (tree) => {
  if (!tree) return

  console.log(tree.val);

  preOrder(tree.left);
  preOrder(tree.right);
}



// 先序遍歷 非遞歸
const preOrder2 = (tree) => {
  if (!tree) return

  // 新建一個棧
  const stack = [tree];

  while (stack.length > 0) {
    const n = stack.pop();
    console.log(n.val);

    // 負負爲正
    if (n.right) stack.push(n.right);
    if (n.left) stack.push(n.left);

  }
}
複製代碼

> 二叉樹的中序遍歷

對根節點的左子樹進行中序遍歷
訪問根節點
對根節點的右子樹進行中序遍歷

二叉樹中序. png

// 中序遍歷 遞歸
const inOrder = (tree) => {
  if (!tree) return;
  inOrder(tree.left)
  console.log(tree.val);
  inOrder(tree.right)
}


// 中序遍歷 非遞歸
const inOrder2 = (tree) => {
  if (!tree) return;

  // 新建一個棧
  const stack = [];

  // 先遍歷所有的左節點
  let p = tree;
  while (stack.length || p) {

    while (p) {
      stack.push(p)
      p = p.left
    }

    const n = stack.pop();
    console.log(n.val);

    p = n.right;
  }
}
複製代碼

> 二叉樹的後序遍歷

對根節點的左子樹進行後序遍歷
對根節點的右子樹進行後序遍歷
訪問根節點

二叉樹後序. png

// 後序遍歷 遞歸
const postOrder = (tree) => {
  if (!tree) return

  postOrder(tree.left)
  postOrder(tree.right)
  console.log(tree.val)
};



// 後序遍歷 非遞歸
const postOrder2 = (tree) => {
  if (!tree) return

  const stack = [tree];
  const outputStack = [];

  while (stack.length) {
    const n = stack.pop();
    outputStack.push(n)
    // 負負爲正
    if (n.left) stack.push(n.left);
    if (n.right) stack.push(n.right);

  }

  while (outputStack.length) {
    const n = outputStack.pop();
    console.log(n.val);
  }
};
複製代碼

> 二叉樹的最大深度

// 給一個二叉樹，需要你找出其最大的深度，從根節點到葉子節點的距離

// 時間複雜度 O(n) n爲樹的節點數
// 空間複雜度 有一個遞歸調用的棧 所以爲 O(n) n也是爲二叉樹的最大深度
var maxDepth = function (root) {
  let res = 0;
    
  // 使用深度優先遍歷
  const dfs = (n, l) => {
    if (!n) return;
    if (!n.left && !n.right) {
     // 沒有葉子節點就把深度數量更新
      res = Math.max(res, l);
    }
    dfs(n.left, l + 1)
    dfs(n.right, l + 1)
  }

  dfs(root, 1)

  return res
}
複製代碼

> 二叉樹的最小深度

// 給一個二叉樹，需要你找出其最小的深度， 從根節點到葉子節點的距離


// 時間複雜度O(n) n是樹的節點數量
// 空間複雜度O(n) n是樹的節點數量
var minDepth = function (root) {
  if (!root) return 0
  
  // 使用廣度優先遍歷
  const q = [[root, 1]];

  while (q.length) {
    // 取出當前節點
    const [n, l] = q.shift();
    
    // 如果是葉子節點直接返回深度就可
    if (!n.left && !n.right) return l
    if (n.left) q.push([n.left, l + 1]);
    if (n.right) q.push([n.right, l + 1]);
  }

}
複製代碼

> 二叉樹的層序遍歷

// 需要返回 [[1], [2,3], [4,5]]


// 時間複雜度 O(n) n爲樹的節點數
// 空間複雜度 O(n) 
var levelOrder = function (root) {
  if (!root) return []
   
  // 廣度優先遍歷
  const q = [root];
  const res = [];
  while (q.length) {
    let len = q.length

    res.push([])
    
    // 循環每層的節點數量次
    while (len--) {
      const n = q.shift();
      
      res[res.length - 1].push(n.val)
      
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }

  }

  return res
};
複製代碼

圖是網絡結構的抽象模型, 是一組由邊連接的節點

js 中可以利用 Object 和 Array 構建圖

樹. png

// 上圖可以表示爲
const graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3]
}


// 深度優先遍歷，對根節點沒訪問過的相鄰節點挨個進行遍歷
{
    // 記錄節點是否訪問過
    const visited = new Set();
    const dfs = (n) => {
      visited.add(n);
      
      // 遍歷相鄰節點
      graph[n].forEach(c => {
        // 沒訪問過纔可以，進行遞歸訪問
        if(!visited.has(c)){
          dfs(c)
        }
      });
    }
    
    // 從2開始進行遍歷
    dfs(2)
}


// 廣度優先遍歷 
{
    const visited = new Set();
    // 新建一個隊列， 根節點入隊， 設2爲根節點
    const q = [2];
    visited.add(2)
    while (q.length) {
    
      // 隊頭出隊，並訪問
      const n = q.shift();
      console.log(n);
      graph[n].forEach(c => {
      
        // 對沒訪問過的相鄰節點入隊
        if (!visited.has(c)) {
          q.push(c)
          visited.add(c)
        }
      })
    }
}
複製代碼

1）有效數字

// 生成數字關係圖 只有狀態爲 3 5 6 的時候才爲一個數字
const graph = {
  0: { 'blank': 0, 'sign': 1, ".": 2, "digit": 6 },
  1: { "digit": 6, ".": 2 },
  2: { "digit": 3 },
  3: { "digit": 3, "e": 4 },
  4: { "digit": 5, "sign": 7 },
  5: { "digit": 5 },
  6: { "digit": 6, ".": 3, "e": 4 },
  7: { "digit": 5 },
}


// 時間複雜度 O(n) n是字符串長度
// 空間複雜度 O(1) 
var isNumber = function (s) {

  // 記錄狀態
  let state = 0;

  // 遍歷字符串
  for (c of s.trim()) {
    // 把字符進行轉換
    if (c >= '0' && c <= '9') {
      c = 'digit';
    } else if (c === " ") {
      c = 'blank';
    } else if (c === "+" || c === "-") {
      c = "sign";
    } else if (c === "E" || c === "e") {
      c = "e";
    }

    // 開始尋找圖
    state = graph[state][c];

    // 如果最後是undefined就是錯誤
    if (state === undefined) return false
  }

  // 判斷最後的結果是不是合法的數字
  if (state === 3 || state === 5 || state === 6) return true
  return false
}; 
複製代碼

一種特殊的完全二叉樹, 所有的節點都大於等於最大堆, 或者小於等於最小堆的子節點

js 通常使用數組來表示堆

左側子節點的位置是 2*index + 1
右側子節點的位置是 2*index + 2
父節點的位置是 (index - 1) / 2 , 取餘數

堆. png

2）JS 實現一個最小堆

// js實現最小堆類
class MinHeap {
  constructor() {
    // 元素容器
    this.heap = [];
  }

  // 交換節點的值
  swap(i1, i2) {
    [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]
  }

  //  獲取父節點
  getParentIndex(index) {
    // 除以二， 取餘數
    return (index - 1) >> 1;
  }

  // 獲取左側節點索引
  getLeftIndex(i) {
    return (i << 1) + 1;
  }

  // 獲取右側節點索引
  getRightIndex(i) {
    return (i << 1) + 2;
  }


  // 上移
  shiftUp(index) {
    if (index == 0) return;

    // 獲取父節點
    const parentIndex = this.getParentIndex(index);

    // 如果父節點的值大於當前節點的值 就需要進行交換
    if (this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index);

      // 然後繼續上移
      this.shiftUp(parentIndex);
    }
  }

  // 下移
  shiftDown(index) {
    // 獲取左右節點索引
    const leftIndex = this.getLeftIndex(index);
    const rightIndex = this.getRightIndex(index);

    // 如果左子節點小於當前的值
    if (this.heap[leftIndex] < this.heap[index]) {

      // 進行節點交換
      this.swap(leftIndex, index);

      // 繼續進行下移
      this.shiftDown(leftIndex)
    }

    // 如果右側節點小於當前的值
    if (this.heap[rightIndex] < this.heap[index]) {
      this.swap(rightIndex, index);
      this.shiftDown(rightIndex)
    }
  }

  // 插入元素
  insert(value) {
    // 插入到堆的底部
    this.heap.push(value);

    // 然後上移： 將這個值和它的父節點進行交換，知道父節點小於等於這個插入的值
    this.shiftUp(this.heap.length - 1)
  }

  // 刪除堆項
  pop() {

    // 把數組最後一位 轉移到數組頭部
    this.heap[0] = this.heap.pop();

    // 進行下移操作
    this.shiftDown(0);
  }

  // 獲取堆頂元素
  peek() {
    return this.heap[0]
  }

  // 獲取堆大小
  size() {
    return this.heap.length
  }

}
複製代碼

2）數組中的第 k 個最大元素

// 輸入 [3,2,1,5,6,4] 和 k = 2
// 輸出 5

// 時間複雜度 O(n * logK) K就是堆的大小
// 空間複雜度 O(K) K是參數k
var findKthLargest = function (nums, k) {

  // 使用上面js實現的最小堆類，來構建一個最小堆
  const h = new MinHeap();
  
  // 遍歷數組
  nums.forEach(n => {
    
    // 把數組中的值依次插入到堆裏
    h.insert(n);
    
    if (h.size() > k) {
      // 進行優勝劣汰
      h.pop();
    }
  })

  return h.peek()
};
複製代碼

3）前 K 個高頻元素

// nums = [1,1,1,2,2,3], k = 2
// 輸出: [1,2]


// 時間複雜度 O(n * logK) 
// 空間複雜度 O(k)
var topKFrequent = function (nums, k) {

  // 統計每個元素出現的頻率
  const map = new Map();

  // 遍歷數組 建立映射關係
  nums.forEach(n => {
    map.set(n, map.has(n) ? map.get(n) + 1 : 1);
  })

  // 建立最小堆
  const h = new MinHeap();

  // 遍歷映射關係
  map.forEach((value, key) => {

    // 由於插入的元素結構發生了變化，所以需要對 最小堆的類 進行改造一下,改造的方法我會寫到最後
    h.insert({ value, key })
    if (h.size() > k) {
      h.pop()
    }
  })
  return h.heap.map(item => item.key)
};

// 改造上移和下移操作即可
// shiftUp(index) {
//   if (index == 0) return;
//   const parentIndex = this.getParentIndex(index);
//   if (this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value) {
//     this.swap(parentIndex, index);
//     this.shiftUp(parentIndex);
//   }
// }
// shiftDown(index) {
//   const leftIndex = this.getLeftIndex(index);
//   const rightIndex = this.getRightIndex(index);

//   if (this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value) {
//     this.swap(leftIndex, index);
//     this.shiftDown(leftIndex)
//   }

//   if (this.heap[rightIndex] && this.heap[rightIndex].value < this.heap[index].value) {
//     this.swap(rightIndex, index);
//     this.shiftDown(rightIndex)
//   }
// }
複製代碼

四、常見算法及算法思想

排序

把某個亂序的數組變成升序序或者降序的數組， js 比較常用 sort 方法進行排序

1）冒泡排序

比較所有相鄰元素，如果第一個比第二個大就交換他們
執行一次後可以保證最後一個數字是最大的
重複執行 n-1 次，就可以完成排序

// 時間複雜度 O(n ^ 2) n爲數組長度
// 空間複雜度 O(1)
Array.prototype.bubbleSort = function () {
  for (i = 0; i < this.length - 1; i++) {
    for (let j = 0; j < this.length - 1 - i; j++) {
      if (this[j] > this[j + 1]) {
      
        // 交換數據
        [this[j], this[j + 1]] = [this[j + 1], this[j]];
      }
    }
  }
}
複製代碼

2）選擇排序

找到數組中最小的值, 選中它並放到第一位
接着找到數組中第二小的值, 選中它並放到第二位
重複上述步驟執行 n-1 次

// 時間複雜度：O(n ^ 2) n爲數組長度
// 空間複雜度：O(1)
Array.prototype.selectionSort = function () {
  for (let i = 0; i < this.length - 1; i++) {
    let indexMin = i;

    for (let j = i; j < this.length; j++) {

      // 如果當前這個元素 小於最小值的下標 就更新最小值的下標
      if (this[j] < this[indexMin]) {
        indexMin = j;
      }
    }

    // 避免自己和自己進行交換
    if (indexMin !== i) {

      // 進行交換數據
      [this[i], this[indexMin]] = [this[indexMin], this[i]];
    }
  }
}
複製代碼

3）插入排序

從第二個數，開始往前比較
如它大就往後排
以此類推進行到最後一個數

// 時間複雜度 O(n ^ 2)
Array.prototype.insertionSort = function () {

  // 遍歷數組 從第二個開始
  for (let i = 1; i < this.length; i++) {

    // 獲取第二個元素
    const temp = this[i];

    let j = i;
    while (j > 0) {

      // 如果當前元素小於前一個元素 就開始往後移動
      if (this[j - 1] > temp) {
        this[j] = this[j - 1];
      } else {

        // 否則就跳出循環
        break
      }

      // 遞減
      j--;
    }

    // 前一位置賦值爲當前元素
    this[j] = temp;
  }
}
複製代碼

4）歸併排序

分：把數組劈成兩半 在遞歸的對子數組進行分操作，直到分成一個個單獨的數
合：把兩個樹合併爲有序數組，再對有序數組進行合併，直到全部子數組合併爲一個完整的數組

// 時間複雜度 O(nlogn) 分需要劈開數組，所以是logn， 合則是n
// 空間複雜度 O(n)
Array.prototype.mergeSort = function () {

  const rec = (arr) => {
    // 遞歸終點
    if (arr.length === 1) return arr

    // 獲取中間索引
    const mid = arr.length >> 1;

    // 通過中間下標,進行分割數組
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);

    // 左邊和右邊的數組進行遞歸,會得到有序的左數組,和有序的右數組
    const orderLeft = rec(left);
    const orderRight = rec(right);


    // 存放結果的數組
    const res = [];

  
    while (orderLeft.length || orderRight.length) {

      // 如左邊和右邊數組都有值
      if (orderLeft.length && orderRight.length) {

        // 左邊隊頭的值小於右邊隊頭的值 就左邊隊頭出隊,否則就是右邊隊頭出隊
        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 res = rec(this)

  // 把結果放入原數組
  res.forEach((n, i) => this[i] = n)
}
複製代碼

> 合併兩個有序鏈表

// 時間複雜度O(n) n爲鏈表1和鏈表2的長度之和
// 空間複雜度O(1)
var mergeTwoLists = function (list1, list2) {

  // 新建一個新鏈表 作爲返回值
  const res = {
    val: 0,
    next: null
  }

  // 指向新鏈表的指針
  let p = res;

  // 建立兩個指針
  let p1 = list1;
  let p2 = list2;


  // 遍歷兩個鏈表
  while (p1 && p2) {

    // 如果鏈表1 小於 鏈表2的值 就接入鏈表1的值
    if (p1.val < p2.val) {
      p.next = p1;

      // 需要往後移動
      p1 = p1.next;
    } else {

      // 否則接入鏈表2的值
      p.next = p2;

      // 需要往後移動
      p2 = p2.next;
    }

    // p永遠要往後移動一位
    p = p.next;
  }

  // 如果鏈表1或者鏈表2還有值,就把後面的值全部接入新鏈表
  if (p1) {
    p.next = p1;
  }
  if (p2) {
    p.next = p2;
  }

  return res.next;
};
複製代碼

5）快速排序

分區：從數組中任意選擇一個基準，所有比基準小的元素放在基準前面，比基準大的元素放在基準後面
遞歸： 遞歸的對基準前後的子數組進行分區

// 時間複雜度 O(nlogN)
// 空間複雜度 O(1)
Array.prototype.quickSort = function () {
  const rec = (arr) => {
  
    // 如果數組長度小於等於1 就不用排序了
    if (arr.length <= 1) { return arr }

    // 存放基準前後的數組
    const left = [];
    const right = [];

    // 取基準
    const mid = arr[0];

    for (let i = 1; i < arr.length; i++) {

      // 如果當前值小於基準就放到基準前數組裏面
      if (arr[i] < mid) {
        left.push(arr[i]);
      } else {

        // 否則就放到基準後數組裏面
        right.push(arr[i]);
      }
    }

    // 遞歸調用兩邊的子數組
    return [...rec(left), mid, ...rec(right)];
  };

  const res = rec(this);
  res.forEach((n, i) => this[i] = n);
}
複製代碼

搜索

找出數組中某個元素的下標，js 中通常使用 indexOf 方法進行搜索

1）順序搜索

就比如 indexOf 方法， 從頭開始搜索數組中的某個元素

2）二分搜索

從數組中的中間位置開始搜索，如果中間元素正好是目標值，則搜索結束
如果目標值大於或者小於中間元素，則在大於或者小於中間元素的那一半數組中搜索
數組必須是有序的，如不是則需要先進行排序

// 時間複雜度：O(log n)
// 空間複雜度：O(1)
Array.prototype.binarySearch = function (item) {
  // 代表數組的最小索引
  let low = 0;

  // 和最大索引
  let higt = this.length - 1;


  while (low <= higt) {

    // 獲取中間元素索引
    const mid = (low + higt) >> 1;
    
    const element = this[mid];

    // 如果中間元素小於於要查找的元素 就把最小索引更新爲中間索引的下一個
    if (element < item) {
      low = mid + 1
    } else if (element > item) {

    // 如果中間元素大於要查找的元素 就把最大索引更新爲中間索引的前一個
      higt = mid - 1;
    } else {
      // 如果中間元素等於要查找的元素 就返回索引
      return mid;
    }
  }

  return -1
}
複製代碼

> 猜數字大小

// 時間複雜度 O(logn) 分割成兩半的 基本都是logn
// 空間複雜度 O(1)
var guessNumber = function (n) {

  // 定義範圍最小值和最大值
  const low = 1;
  const high = n;

  while (low <= high) {

    // 獲取中間值
    const mid = (low + high) >>> 1;

    // 這個方法是 leetcode 中的方法
    // 如果返回值爲-1 就是小了
    // 如果返回值爲1  就是大了
    // 如果返回值爲0  就是找到了 
    const res = guess(mid);
    
    // 剩下的操作就和二分搜索一樣
    if (res === 0) {
      return mid
    } else if (res === 1) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
};
複製代碼

分而治之

算法設計中的一種思想，將一個問題分成多個子問題，遞歸解決子問題，然後將子問題的解合併成最終的解

1）歸併排序

分：把數組從中間一分爲二
解：遞歸地對兩個子數組進行歸併排序
合：合併有序子數組

2）快速排序

分：選基準，按基準把數組分成兩個子數組
解：遞歸地對兩個子數組進行快速排序
合：對兩個子數組進行合併

3）二分搜索

二分搜索也屬於分而治之這種思想

> 分而治之思想：猜數字大小

// 時間複雜度 O(logn) 
// 空間複雜度 O(logn) 遞歸調用棧 所以是logn
var guessNumber = function (n) {

  // 遞歸函數 接受一個搜索範圍
  const rec = (low, high) => {
  
    // 遞歸結束條件
    if (low > high) return;

    // 獲取中間元素
    const mid = (low + high) >>> 1;

    // 判斷是否猜對
    const res = guess(mid)

    // 猜對
    if (res === 0) {
      return mid
    } else if (res === 1) {
      // 猜大了
      return rec(mid + 1, high)
    } else {
      // 猜小了
      return rec(low, mid - 1)
    }
  }

  return rec(1, n)
};
複製代碼

> 分而治之思想：翻轉二叉樹

// 時間複雜度 O(n) n爲樹的節點數量
// 空間複雜度 O(h) h爲樹的高度
var invertTree = function (root) {
  if (!root) return null
  return {
    val: root.val,
    left: invertTree(root.right),
    right: invertTree(root.left)
  }
};
複製代碼

> 分而治之思想：相同的樹

// 時間複雜度 o(n) n爲樹的節點數量
// 空間複雜度 o(h) h爲樹的節點數
var isSameTree = function (p, q) {
  if (!p && !q) return true
  
  if (
    p && q
    && p.val === q.val
    && isSameTree(p.left, q.left)
    && isSameTree(p.right, q.right)
  ) return true

  return false
};
複製代碼

> 分而治之思想：對稱二叉樹

// 時間複雜度 O(n)
// 空間複雜度 O(n) 
var isSymmetric = function (root) {
  if (!root) return true
  const isMirror = (l, r) => {
    if (!l && !r) return true
    if (
      l && r 
      && l.val === r.val
      && isMirror(l.left, r.right)
      && isMirror(l.right, r.left)
    ) return true
    return false
  }

  return isMirror(root.left, root.right)
};
複製代碼

動態規劃

動態規劃是算法設計中的一種思想，將一個問題分解爲相互重疊的子問題，通過反覆求解子問題來解決原來的問題

1）斐波那契數列

// 時間複雜度 O(n) 
// 空間複雜度 O(n)
function fib(n) {
    let dp = [0, 1, 1];
    for (let i = 3; i <= n; i++) {

        // 當前值等於前兩個值之和
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
複製代碼

2）爬樓梯

// 正在爬樓梯, 需要n階才能到達樓頂
// 每次只能爬 1 或者 2 個臺階, 有多少中不同的方法可以到達樓頂

// 時間複雜度 O(n) n是樓梯長度
// 空間複雜度 O(1)
var climbStairs = function (n) {
    if (n < 2) return 1

    let dp0 = 1;
    let dp1 = 1

    for (let i = 2; i <= n; i++) {
        [dp0, dp1] = [dp1, dp1 + dp0]
    }

    return dp1
};
複製代碼

貪心算法

貪心算法是算法設計中的一種思想，期盼通過每個階段的局部最優選擇，從而達到全局的最優，但 結果並不一定是最優

1）分發餅乾

// 每個孩子都有一個胃口g. 每個孩子只能擁有一個餅乾
// 輸入: g = [1,2,3], s = [1,1]
// 輸出: 1
// 三個孩子胃口值分別是1,2,3  但是隻有兩個餅乾,所以只能讓胃口1的孩子滿足

// 時間複雜度 O(nlogn) 
// 空間複雜度 O(1)
var findContentChildren = function (g, s) {
    // 對餅乾和孩子胃口進行排序
    g.sort((a, b) => a - b)
    s.sort((a, b) => a - b)


    // 是第幾個孩子
    let i = 0

    s.forEach((n) => {
        // 如果餅乾能滿足第一個孩子
        if (n >= g[i]) { 
            // 就開始滿足第二個孩子
            i += 1
        }
    })

    return i
}
複製代碼

2）買賣股票的最佳時機 Ⅱ

// 時間複雜度 O(n) n爲股票的數量
// 空間複雜度 O(1)
var maxProfit = function (prices) {
  // 存放利潤
  const profit = 0;
  for (let i = 1; i < prices.length; i++) {

    // 不貪 如有更高的利潤就直接賣出
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1]
    }
  }

  return profit
};
複製代碼

回溯算法

回溯算法是算法設計中的一種思想，一種漸進式尋找並構建問題解決方式的策略，會先從一個可能的動作開始解決問題，如不行，就回溯選擇另外一個動作，直到找到一個解

1）全排列

// 輸入 [1, 2, 3]
// 輸出 [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]


// 時間複雜度 O(n!) n! = 1 * 2 * 3 * ··· * (n-1) * n;
// 空間複雜度 O(n)
var permute = function (nums) {
  // 存放結果
  const res = [];

  const backTrack = (path) => {
    // 遞歸結束條件 
    if (path.length === nums.length) {
      res.push(path)
      return
    }

    // 遍歷傳入數組
    nums.forEach(n => {
      // 如果子數組中有這個元素就是死路， 需要回溯回去走其他路
      if (path.includes(n)) return;

      // 加入到子數組裏
      backTrack(path.concat(n))
    })
  }

  backTrack([])

  return res;
};
複製代碼

2）子集

// 輸入 [1,2,3]
// 輸出 [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

// 時間複雜度 O(2 ^ N) 每個元素都有兩種可能
// 空間複雜度 O(N)
var subsets = function (nums) {
  // 存放結果數組
  const res = [];

  const backTrack = (path, l, start) => {
    // 遞歸結束條件
    if (path.length === l) {
      res.push(path)
      return
    }

    // 遍歷輸入的數組長度 起始位置是start
    for (let i = start; i < nums.length; i++) {

      // 遞歸調用 需要保證子集的有序, start爲 i+1
      backTrack(path.concat(nums[i]), l, i + 1)
    }
  };

  // 遍歷輸入數組長度
  for (let i = 0; i <= nums.length; i++) {

    // 傳入長度 起始索引
    backTrack([], i, 0)
  }


  return res
};
複製代碼

五、結語

本文中，僅對常見和常用的數據結構與算法進行了演示

算法這個東西，平時還是要多練。記得看完後多刷一刷 leetcode

關於本文

來自：Ali2333

https://juejin.cn/post/7094056264283471908

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/1Q8pI1_sMt72UxWjR6Orlg

一、前言

二、基本概念

三、數據結構

1）十進制轉二進制

2）判斷字符串的有效括號

1）最近的請求次數

1）手寫 instanceOf

2）刪除鏈表中的節點

3）刪除排序鏈表中的重複元素

4）反轉鏈表

1）去重

2）兩個數組的交集

1）兩數之和

2）兩個數組的交集

3）字符的有效的括號

4）最小覆蓋字串

1）普通樹

> 深度優先遍歷

> 廣度優先遍歷

2）二叉樹

> 二叉樹的先序遍歷

> 二叉樹的中序遍歷

> 二叉樹的後序遍歷

> 二叉樹的最大深度

> 二叉樹的最小深度

> 二叉樹的層序遍歷

1）有效數字

2）JS 實現一個最小堆

2）數組中的第 k 個最大元素

3）前 K 個高頻元素

四、常見算法及算法思想

1）冒泡排序

2）選擇排序

3）插入排序

4）歸併排序

> 合併兩個有序鏈表

5）快速排序

1）順序搜索

2）二分搜索

> 猜數字大小

1）歸併排序

2）快速排序

3）二分搜索

> 分而治之思想：猜數字大小

> 分而治之思想：翻轉二叉樹

> 分而治之思想：相同的樹

> 分而治之思想：對稱二叉樹

1）斐波那契數列

2）爬樓梯

1）分發餅乾

2）買賣股票的最佳時機 Ⅱ

1）全排列

2）子集

五、結語

猜你喜歡