佇列

佇列簡介

• 一個先進先出的資料結構
• js中沒有佇列,但是可以用Array實作對佇列的所有功能

使用陣列模擬先進先出的場景

const queue = [] 
// 進佇列
queue.push(1)
queue.push(2)

// 出佇列
const itme1 = queue.shift()
const itme2 = queue.shift()

什么時候用

1. 食堂排隊打飯
2. 所有先進先出的場景
3. js 異步中的任務佇列
   一個leetcode題 第933題

鏈表

鏈表是什么

• 多個元素組成的串列
• 勻速存盤不連續, 用next指標連在一起

陣列 vs 鏈表

• 陣列:增刪非收尾元素是往往需要移動元素
• 鏈表:增刪非收尾元素,不需要移動元素,只需要更改next指標即可

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

// 遍歷
let point = a
while (point) {
    console.log(point.val)
    point = point.next
}

// 插入
(c-d)中插入d

const e = {val:'e'}
c.next = e
e.next = d


// 洗掉 (洗掉e)
c.next = d

leetcode練習:第83題-洗掉鏈表重復元素

var deleteDuplicates = function(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
 
};

• 前端原型鏈的鏈表 JavaScript 一文搞定理解原型與原型鏈
  手寫一個instanceof

function myInstanceof (A, B) {
  // 遍歷鏈表
  let p =  A
  while (p) {
    p = p.__proto__
    // B的 prototype 屬性是否出現在A實體物件的原型鏈上
    if (p === B.prototype) {
      return true
    }
   
  }
  return false
}
function Foo () {}
var f = new Foo()
console.log(myInstanceof(f, Foo)); // true
console.log(myInstanceof(f, Object)); // true

集合

集合簡介

• 一種無序且唯一的資料結構
• ES6中有集合, 名為Set
• 集合常用操作: 去重,判斷某元素是否在集合中,求交集

// 去重
const arr = [1,1,2,3,4,3]
const arr2 = [...new Set(arr)]

// 判斷元素是否在集合中
let set = new Set(arr)

// add 方法
set.add(1)
set.add('text')
set.add({a:1,b:2})

// has方法
const has =set.has(3)

// delete方法
set.delete(1)

// 獲取size 方法
console.log(set.size)
// 求交集
const set2 = new Set([2,3])
const set3 new Set([...set]).filter(item => set2.has(item))

// 求差集
const set2 = new Set([2,3])
const set4 = new Set([...set]).filter(item => !set2.has(item))

// 陣列轉為set
set2 = new Set([1,2,3])

// 迭代方法 fot ..of
for (let item of set) console.log(item)
for (let item of set.keys())) console.log(item)
for (let item of set.values()) console.log(item)
for (let item of set.entrise()) console.log(item)

補充說明迭代
內置迭代器:

可迭代的物件，都內置以下3種迭代器

entries(): 回傳一個迭代器，值為鍵值對

values(): 回傳一個迭代器, 值為集合的值

keys(): 回傳一個迭代器，值為集合中的所有鍵

let userList = [ 'ghostwu', '悟空', '八戒' ];

for ( let name of userList.entries() ) {
    console.log( name );
}

let set = new Set( [ 10, 20, 30 ] );
for ( let num of set.entries() ){
    console.log( num );
}

let map = new Map( [ [ 'name', 'ghostwu' ], [ 'age', 22 ] ] );
for ( let detail of map.entries() ){
    console.log( detail );
}

字典

字典簡介

• 與集合相似, 字典也是一種存盤為一值的資料結構, 但他是以鍵值對的形式存盤
• ES6中有字典–>Map(映射)
• 常見操作 增(set) 刪(delete) 改(set) 查(get)

const m = new Map()

//增
m.set('a','aaa')

// 刪
m.delete('a')
m.clear()

// 改
m.set('a','aaaaa')

// 查
m.get('a')

使用Map取兩個陣列的交集

var intersection = function(nums1, nums2) {
  // new Set(nums1) 去重
  return  [...new Set(nums1)].filter(item => nums2.includes(item))
};

樹

樹簡介

• 一種分層資料的抽象模型
• 前端作業中常見的樹包括:DOM樹,級聯選擇,樹形控制元件…
• js中沒有樹,但是可以用Array 和Object構建樹
• 樹的常用操作: 深度/廣度優先遍歷 , 先中后序遍歷

樹的深度/廣度優先遍歷

• 深度優先遍歷： 盡可能深的搜索樹的分支:遞回
  1. 訪問根節點
  2. 對根節點的children挨個進行深度優先遍歷
     

const tree = {
  val: 'a',
  children: [
    {
      val: 'b',
      children: [
        {
          val: 'd',
          children: [
            
          ]
        },
        {
          val: 'e',
          children: [
            
          ]
        }
      ]
    },
    {
      val: 'c',
      children: [
        {
          val: 'f',
          children: [
            
          ]
        },
        {
          val: 'g',
          children: [
            
          ]
        }
      ]
    }
  ]
}
const dfs =(root) => {
  console.log(root.val)
  root.children.forEach(dfs)
}

dfs(tree)

列印結果

• 廣度優先遍歷:先訪問離根節點最近的節點
  1. 新建一個佇列, 把根節點入隊
  2. 把對頭出隊并訪問
  3. 把對頭的children挨個入隊
  4. 重復第二,第三,直到佇列為空

const bfc = (root) => {
  const q = [root]
  while (q.length > 0) {
    const n = q.shift()
    console.log(n.val)
    n.children.forEach(child => {
      q.push(child)
    })
  }
}

列印結果:

二叉樹的先中后序遍歷

二叉樹是什么?

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

• 在js中通常用Object來模擬二叉樹

const binaryTree = {
  val: 1,
  left: {
    val:2,
    left: null,
    right: null
  },
  right: {
    val:3,
    left: null,
    right: null
  }
}

先序遍歷演算法

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

遍歷順序如圖

定義一棵樹

const binaryTree = {
 val: 1,
 left: {
   val: 2,
   left: {
     val: 4,
     left: null,
     right: null,
   },
   right: {
     val: 5,
     left: {
       val: 7,
       left: null,
       right: null,
     },
     right: null,
   },
 },
 right: {
   val: 3,
   left: null,
   right: {
     val: 6,
     left: null,
     right: null,
   },
 },
};

遞回版:

const preorder = root => {
  if (!root) return;
  console.log(root.val);
  preorder(root.left);
  preorder(root.right);
};
preorder(binaryTree);

非遞回(堆疊特性):

const preorder = root => {
  if (!root) return;
  const stack = [root];
  while (stack.length) {
    const n = stack.pop();
    console.log(n.val);
    n.right && stack.push(n.right);
    n.left && stack.push(n.left);
  }
};
preorder(binaryTree);

列印結果:

中序遍歷演算法

1. 對根節點的左子樹進行中序遍歷
2. 訪問根接節點
3. 對根節點的右子樹進行中序遍歷

遍歷順序如圖

還是使用binaryTree這個樹
遞回版實作:

const inorder = root => {
  if(!root) return 
  inorder(root.left)
  console.log(root.val)
  inorder(root.right)
}
inorder(binaryTree)

非遞回版實作:

const inorder = root => {
  if (!root) return;
  const stack = [];
  let p = root;
  while (stack.length || p) {
    while (p) {
      stack.push(p);
      p = p.left;
    }
    const n = stack.pop();
    console.log(n.val);
    p = n.right;
  }
}
inorder(binaryTree)

列印結果:

后序遍歷演算法

1. 對根節點的左子樹進行中序遍歷
2. 對根節點的右子樹進行中序遍歷
3. 訪問根接節點

還是使用binaryTree這個樹
遞回版實作:

const postorder = (root) => {
  if (!root) return;
  postorder(root.left);
  postorder(root.right);
  console.log(root.val);
};
postorder(binaryTree);

非遞回版實作:

const inorder = root => {
  if (!root) return;
  const outputStack = [];
  const stack = [root];
  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);
  }
}
inorder(binaryTree)

列印結果:

前端與樹

遍歷JSON的所有節點值

使用深度優先遍歷

const json = {
  a: { b: { c: 1 } },
  d: [1, 2],
};
// 深度優先遍歷
const dfs = (n, path) => {
  console.log(n, path);
  Object.keys(n).forEach((k) => {
    dfs(n[k], path.concat(k));
  });
};
dfs(json, []);

列印結果

圖

圖是什么

• 圖是網路結構的抽象模型, 是一組由邊連接的節點
• 圖可以表示任何二元關系, 比如路,航班
• js沒有圖, 可以用Array Object模擬

圖的表示法

鄰接矩陣

鄰接表

圖的遍歷

• 深度優先遍歷: 盡可能深的搜索圖的分支

1. 訪問根節點
2. 對根節點的沒訪問過得相鄰節點挨個進行深度優先遍歷

定義一個圖

const graph = {
  0:[1,2],
  1:[2],
  2:[0,3],
  3:[3]
}

使用深度優先遍歷

const visited = new Set()
const dfs = n => {
  console.log(n)
  visited.add(n)
  graph[n].forEach(c => {
    if(!visited.has(c)) {
      dfs(c)
    }
  })
}
dfs(2)

列印結果

• 廣度優先遍歷: 先訪問離根節點最近的節點

1. 新建一個佇列, 把根節點入隊
2. 把隊頭出隊并訪問
3. 把隊頭的沒訪問過得相鄰節點入隊
4. 重復第二 三步, 直到佇列為空

const bfs = node => {
  const visited = new Set()
  visited.add(node)
  const q = [node]
  while (q.length) {
    const n = q.shift()
    console.log(n)
    graph[n].forEach(c => {
      if(!visited.has(c)) {
        q.push(c)
        visited.add(c)
      }
    })
  }
}
bfs(2)

列印結果:

堆

堆是什么

• 堆是一種特殊的完全二叉樹
  完全二叉樹如圖:
  

• 所有的節點都大于等于(最大堆)或小于等于(最小堆)他的節點

• js中通常用陣串列述堆

• 左側子節點的位置是2 * index + 1

• 右側子節點的位置是2 * index + 2

• 父節點的位置是(index - 1) / 2

堆的應用

• 對能高效快速地找出最大值和最小值, 時間復雜度:O(1)
• 找出第K個最大(小)元素

第K個最大元素

1. 構建一個最小堆, 并將元素依次插入堆中
2. 當堆的容量超過K, 就是洗掉堆頂
3. 插入結束后, 堆頂就是第K個最大元素

js實作最小堆類

• 構建一個類

1. 在類里, 宣告一個陣列, 用來裝元素
2. 主要方法: 插入, 洗掉堆頂, 獲取堆頂, 獲取堆大小

• 插入

1. 將值插入堆的底部,即陣列的尾部
2. 然后上移: 將這個值和它的防父節點進行交換, 直到父節點小于等于這個插入的值
3. 大小為k的堆中插入元素的時間復雜度為O(logk)

• 洗掉堆頂

1. 用陣列尾部元素替換堆頂(直接洗掉堆頂會破壞堆結構)
2. 然后下移: 將新堆頂和它的子節點進行交換, 直到子節點大于等于這個新堆頂
3. 大小為k的堆中洗掉堆頂得時間復雜度為O(logk)