一. 概論
1. 數(shù)據(jù)結構隊列：一種遵循先進先出 (FIFO / First In First Out) 原則的一組有序的項；隊列在尾部添加新元素，并從頭部移除元素。最新添加的元素必須排在隊列的末尾。（例如：去食堂排隊打飯，排在前面的人先打到飯，先離開；排在后面的人后打到飯，后離開。）
棧：一種遵從先進后出 (LIFO) 原則的有序集合；新添加的或待刪除的元素都保存在棧的末尾，稱作棧頂，另一端為棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。（例如：往口袋里面裝東西，先裝進去的放在最下面，后裝進去的放在最上面，取出的時候只能從上往下取。）
鏈表：存儲有序的元素集合，但不同于數(shù)組，鏈表中的元素在內存中并不是連續(xù)放置的；每個元素由一個存儲元素本身的節(jié)點和一個指向下一個元素的引用（指針/鏈接）組成。
集合：由一組無序且唯一（即不能重復）的項組成；這個數(shù)據(jù)結構使用了與有限集合相同的數(shù)學概念，但應用在計算機科學的數(shù)據(jù)結構中。
字典：以 [鍵，值] 對為數(shù)據(jù)形態(tài)的數(shù)據(jù)結構，其中鍵名用來查詢特定元素，類似于 Javascript 中的Object。
哈希表：根據(jù)關鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結構。通過把關鍵碼值映射到表中某個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫散列表。
給定表M，存在函數(shù)f(key)，對任意給定的關鍵字值key，代入函數(shù)后若能得到包含該關鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表，函數(shù)f(key)為哈希(Hash) 函數(shù)。
樹：由 n（n>=1）個有限節(jié)點組成一個具有層次關系的集合；把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，基本呈一對多關系，樹也可以看做是圖的特殊形式。
圖：圖是網(wǎng)絡結構的抽象模型；圖是一組由邊連接的節(jié)點（頂點）；任何二元關系都可以用圖來表示，常見的比如：道路圖、關系圖，呈多對多關系。
2. 算法
排序算法：冒泡排序（升序）：逐一比較相鄰兩個元素，如果前面的元素比后面的元素大則交換兩者順序；元素項向上移動至正確的順序，好似氣泡上升至表面一般，因此得名。（冒泡排序每一輪至少有一個元素會出現(xiàn)在正確位置）
快速排序（升序）：選擇一個基準值，每一個元素與基準值比較。比基準值小的元素放在基準值左邊，比基準值大的元素放在基準值右邊，左右兩邊遞歸執(zhí)行此操作。通常選擇中間的元素作為基準值。
選擇排序：每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在序列的起始位置，以此循環(huán)，直至排序完畢。
插入排序：將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)，此算法適用于少量數(shù)據(jù)的排序。
歸并排序：將原始序列切分成較小的序列，只到每個小序列無法再切分，然后執(zhí)行合并，即將小序列歸并成大的序列，合并過程進行比較排序，只到最后只有一個排序完畢的大序列，時間復雜度為 O(n log n)。
各種時間復雜度的直觀比較：
搜索算法：順序搜索：讓目標元素與列表中的每一個元素逐個比較，直到找出與給定元素相同的元素為止，缺點是效率低下。
二分搜索：在一個有序列表，以中間值為基準拆分為兩個子列表，拿目標元素與中間值作比較從而再在目標的子列表中遞歸此方法，直至找到目標元素。
其他算法：貪心算法：在對問題求解時，不考慮全局，總是做出局部最優(yōu)解的方法。
動態(tài)規(guī)劃：在對問題求解時，由以求出的局部最優(yōu)解來推導全局最優(yōu)解。
復雜度概念：一個方法在執(zhí)行的整個生命周期，所需要占用的資源，主要包括：時間資源、空間資源。
二. 數(shù)據(jù)結構
隊列概念：一種遵循先進先出 (FIFO / First In First Out) 原則的一組有序的項；隊列在尾部添加新元素，并從頭部移除元素。最新添加的元素必須排在隊列的末尾。
在 Javascript 中實現(xiàn)一個隊列類。
1.創(chuàng)建一個類：
class Queue{
constructor(items) {
this.items = items || []
}
// 1. 在末尾添加元素
enqueue(element){
this.items.push(element)
}
// 2. 在頭部刪除元素
dequeue(){
return this.items.shift()
}
// 3. 獲取頭部元素
front(){
return this.items[0]
}
// 4. 獲取隊列長度
get size(){
return this.items.length
}
// 5. 判斷是否是空隊列
get isEmpty(){
return !this.items.length
}
// 6. 清空隊列
clear(){
this.items = []
}
}
2.使用類：
const queue = new Queue() // 類的實例化
queue.isEmpty // true
queue.enqueue('John') // {items: ['John']}
queue.enqueue('Jack') // {items: ['John','Jack']}
queue.enqueue('Camila') // {items: ['John','Jack','Camila']}
queue.size // 3
queue.isEmpty // false
queue.dequeue() // John
queue.dequeue() // Jack
queue.dequeue() // Camila
優(yōu)先隊列概念：元素的添加和移除是基于優(yōu)先級的，不在滿足完全意義的先進先出。例如機場登機的順序，頭等艙和商務艙乘客的優(yōu)先級要高于經(jīng)濟艙乘客，這些乘客不需要通過正常排隊登機。或是去醫(yī)院看病，醫(yī)生也會根據(jù)病情程度優(yōu)先處理病情嚴重的。
在 Javascript 中實現(xiàn)一個隊列類：
1.創(chuàng)建一個類：
class PriorityQueue {
constructor() {
this.items = []
}
enqueue(element, priority){
const queueElement = { element, priority }
if (this.isEmpty) {
this.items.push(queueElement)
} else {
// 在列表中找到第一個比后進入的元素的priority大的元素的位置，如果有，將這個元素插入這里。如果沒有，將這個元素放在最后面。
const preIndex = this.items.findIndex((item) => queueElement.priority < item.priority)
if (preIndex > -1) {
this.items.splice(preIndex, 0, queueElement)
} else {
this.items.push(queueElement)
}
}
}
dequeue(){
return this.items.shift()
}
front(){
return this.items[0]
}
clear(){
this.items = []
}
get size(){
return this.items.length
}
get isEmpty(){
return !this.items.length
}
print() {
console.log(this.items)
}
}
2.使用類：
const priorityQueue = new PriorityQueue()
priorityQueue.enqueue('Wangjiajia', 2) // {items: [{element: 'Wangjiajia', priority: 2}]}
priorityQueue.enqueue('Wangtongtong', 1) // {items: [{element: 'Wangtongtong', priority: 1},{element: 'Wangjiajia', priority: 2}]}
priorityQueue.enqueue('Davide', 4) // {items: [{element: 'Wangtongtong', priority: 1},{element: 'Wangjiajia', priority: 2},{element: 'Davide', priority: 4}]}
priorityQueue.enqueue('Tom', 3) // {items: [{element: 'Wangtongtong', priority: 1},{element: 'Wangjiajia', priority: 2},{element: 'Tom', priority: 3},{element: 'Davide', priority: 4}]}
priorityQueue.enqueue('James', 2) // {items: [{element: 'Wangtongtong', priority: 1},{element: 'Wangjiajia', priority: 2},{element: 'James', priority: 2},{element: 'Tom', priority: 3},{element: 'Davide', priority: 4}]}
循環(huán)隊列概念：為充分利用向量空間，克服"假溢出"現(xiàn)象將向量空間想象為一個首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量。存儲在其中的隊列稱為循環(huán)隊列（Circular Queue）。通俗來說：循環(huán)隊列是把順序隊列首尾相連，把存儲隊列元素的表從邏輯上看成一個環(huán)，成為循環(huán)隊列。假溢出： 隊列的空間未利用完,但是卻造成了元素的溢出。
基于首次實現(xiàn)的隊列類，簡單實現(xiàn)一個循環(huán)引用的示例：
class LoopQueue extends Queue {
constructor(items) {
super(items)
}
getIndex(index) {
const length = this.items.length
return index > length ? (index % length) : index
}
find(index) {
return !this.isEmpty ? this.items[this.getIndex(index)] : null
}
}
使用：
const loopQueue = new LoopQueue(['Surmon'])
loopQueue.enqueue('SkyRover')
loopQueue.enqueue('Even')
loopQueue.enqueue('Alice')
console.log(loopQueue.size, loopQueue.isEmpty) // 4 false
(loopQueue.find(26) // 'Evan'
(loopQueue.find(87651) // 'Alice'
棧：概念：一種遵從先進后出 (LIFO) 原則的有序集合；新添加的或待刪除的元素都保存在棧的末尾，稱作棧頂，另一端為棧底，出去的時候從棧頂開始出去。在棧里，新元素都靠近棧頂，舊元素都接近棧底。`
用javascript基于數(shù)組的方法實現(xiàn)一個棧的功能：
class Stack {
constructor() {
this.items = []
}
// 入棧
push(element) {
this.items.push(element)
}
// 出棧
pop() {
return this.items.pop()
}
// 末位
get peek() {
return this.items[this.items.length - 1]
}
// 是否為空棧
get isEmpty() {
return !this.items.length
}
// 尺寸
get size() {
return this.items.length
}
// 清空棧
clear() {
this.items = []
}
// 打印棧數(shù)據(jù)
print() {
console.log(this.items.toString())
}
}
使用棧：
// 實例化一個棧
const stack = new Stack()
console.log(stack.isEmpty) // true
// 添加元素
stack.push(5) // [5]
stack.push(8) // [5,8]
// 讀取屬性再添加
console.log(stack.peek) // 8
stack.push(11) // [5,8,11]
stack.pop() // 11
console.log(stack.size) // 3
console.log(stack.isEmpty) // false
鏈表：概念：存儲有序的元素集合，但不同于數(shù)組，鏈表中的元素在內存中并不是連續(xù)放置的；每個元素由一個存儲元素本身的節(jié)點和一個指向下一個元素的引用（指針/鏈接）組成。分類：單向鏈表，雙向鏈表，循環(huán)鏈表鏈表和數(shù)組的區(qū)別：
* 數(shù)組在添加或者刪除元素的時候需要移動其他元素，鏈表不需要。鏈表需要使用指針，因此使用的時候需要額外注意一下。
* 數(shù)組可以訪問其中任何一個元素，鏈表需要從頭開始迭代，直到找到所需的元素。
鏈表的常見方法：1、append(element)：向列表尾部添加一個新的項2、insert(position, element)：向列表的特定位置插入一個新的項。3、remove(element)：從列表中移除一項。4、removeAt(position)：從列表的特定位置移除一項。5、indexOf(element)：返回元素在列表中的索引。如果列表中沒有該元素則返回-1。6、getElementAt(index): 返回鏈表中特定位置的元素, 如果不存在這樣的元素則返回undefined7、isEmpty()：如果鏈表中不包含任何元素，返回true，如果鏈表長度大于0則返回false。8、size()：返回鏈表包含的元素個數(shù)。與數(shù)組的length屬性類似。9、toString()：由于列表項使用了Node類，就需要重寫繼承自JavaScript對象默認的toString方法，讓其只輸出元素的值element。
整體操作方法和數(shù)組非常類似, 因為鏈表本身就是一種可以代替數(shù)組的結構.使用javascript描述一個單向鏈表：
單向鏈表：
生活中的例子：火車就可以看做鏈表，每一節(jié)都是由一節(jié)車廂和車廂之間的連接帶組成，這個連接帶就可以看成是指針。
用javascript來描述一個單向鏈表：
// 鏈表節(jié)點
class Node {
constructor(element) {
this.element = element
this.next = null
}
}
// 單向鏈表
class LinkedList {
constructor() {
this.head = null
this.length = 0
}
// 1. 追加元素
// 向鏈表尾部追加數(shù)據(jù)可能有兩種情況:
// 鏈表本身為空, 新添加的數(shù)據(jù)是唯一的節(jié)點.
// 鏈表不為空, 需要向其他節(jié)點后面追加節(jié)點.
append(element) {
const node = new Node(element)
let current = null
// 鏈表本身為空, 新添加的數(shù)據(jù)是唯一的節(jié)點.
if (this.head === null) {
this.head = node
} else {
// 鏈表不為空, 需要向其他節(jié)點后面追加節(jié)點.
current = this.head
while(current.next) {
current = current.next
}
current.next = node
}
this.length++
}
// 2. 任意位置插入元素
insert(position, element) {
// 1.檢測越界問題: 越界插入失敗, 返回false
if (position < 0 || position > this.length) return false
// 2.找到正確的位置, 并且插入數(shù)據(jù)
// 定義要插入的變量newNode, current當前節(jié)點, previous上一個節(jié)點
let newNode = new Node(element)
let current = this.head // 初始值為head, 對第一個元素的引用
let previous = null // 存儲當前current的上一個節(jié)點
let index = 0 // 位置
// 3.判斷是否列表是否在第一個位置插入
if (position == 0) {
newNode.next = current
this.head = newNode
} else {
while (index++ < position) { // 向前趕, 直到找到當前位置position
previous = current
current = current.next
}
// index === position, 找到要插入的位置
newNode.next = current
previous.next = newNode
}
// 4.length+1
this.length++
}
// 3. 從鏈表中任意移除一項
removeAny(position) {
//邊界檢查，越界返回false
if(position < 0 || position > this.length-1){
return false
}
let current = this.head
let previous = null
let index = 0
// 如果刪除第一個元素
if(position == 0){
this.head = current.next
}else{
// 不是刪除第一個找到刪除的位置
while(index++ < position){
previous = current
current = current.next
}
previous.next = current.next
}
this.length--
return current.element
}
// 4. 尋找元素下標
findIndex(element) {
let current = this.head
let index = 0
//遍歷鏈表直到找到data匹配的position
while (current) {
if (element === current.element) {
return index
}
current = current.next
index++
}
return false
}
// 5. 從鏈表的特定位置移除一項。
remove(element) {
const index = this.indexOf(element)
return this.removeAt(index)
}
// 6. 判斷是否為空鏈表
isEmpty() {
return !this.length
}
// 7. 獲取鏈表長度
size() {
return this.length
}
// 8. 轉為字符串
toString() {
let current = this.head
let str = ''
while (current) {
str += ` ${current.element}`
current = current.next
}
return str
}
}
鏈表類的使用：
const linkedList = new LinkedList()
console.log(linkedList) // LinkedList {head: null, length: 0}
// 1. 在末尾追加元素
linkedList.append(2) // LinkedList {head: {element:2,next:null}, length: 1}
linkedList.append(4) // LinkedList {head: {element:2,next:{element:4,next:null}}, length: 2}
linkedList.append(6) // LinkedList {head: {element:2,next:{element:4,next:{element:6,next:null}}}, length: 3}
// 2. 在任意位置插入一個元素
linkedList.insert(2, 18) // LinkedList {head: {element:2,next:{element:4,next:{element:18,next:{element:6,next:null}}}}, length: 4}
// 3. 從鏈表中任意位置刪除一項
linkedList.removeAny(2) // 18
// 4. 尋找元素下標
linkedList.findIndex(6) // 2
linkedList.findIndex(18) // false
linkedList.findIndex(20) // false
// 5. 從鏈表的特定位置移除一項。
linkedList.remove(4)
// 6. 判斷是否為空鏈表
linkedList.isEmpty() // false
// 7. 獲取鏈表長度
linkedList.size() // 2
// 8. 轉為字符串
linkedList.toString() // ' 2 4 18 6'
雙向鏈表：概念：雙向鏈表和普通鏈表的區(qū)別在于，在鏈表中， 一個節(jié)點只有鏈向下一個節(jié)點的鏈接，而在雙向鏈表中，鏈接是雙向的：一個鏈向下一個元素， 另一個鏈向前一個元素，如下圖所示：
使用javacsript來實現(xiàn)一個雙向鏈表類：
class Node{
constructor(element){
this.element = element
this.next = null
this.prev = null
}
}
// 雙向鏈表
class DoublyLinkedList {
constructor() {
this.head = null
this.tail = null
this.length = 0
}
// 1. 任意位置插入
insert(position,element){
// 1.1 檢測越界問題: 越界插入失敗, 返回false
if (position < 0 || position > this.length) return false
let newNode = new Node(element)
let current = this.head // 初始值為head, 對第一個元素的引用
let previous = null // 存儲當前current的上一個節(jié)點
let index = 0 // 位置
// 1.2 如果插在了首位
if(position == 0){
// 空鏈表
if(!head){
this.head = node
this.tail = node
}else{
this.head = node
node.next = current
current.prev = node
}
}
// 1.3 如果插在了末位
else if(position == this.length) {
this.tail = node
current.next = node
node.prev = current
}else {
// 如果插在了中間位置
// 找到插入的位置
while(idex++ < position){
previous = current
current = current.next
}
// 插入進去
node.next = current
previous.next = node
node.pre = previous
current.pre = node
this.length++
return true
}
}
// 2. 移除任意位置元素
removeAny(position){
// 2.1 邊界檢查，越界返回false
if(position < 0 || position > this.length-1) return false
let current = this.head
let previous = null
let index = 0
// 2.2 如果刪除的是首位
if(position == 0){
this.head = current.next
this.head.prev = null
}else if(position == this.length - 1){
// 2.3 如果刪除的是末位
this.tail = current.pre
this.tail.next = null
}else {
// 2.4 中間項
// 找到刪除的位置
while(index++ < position){
previous = current
current = current.next
}
previous.next = current.next
current.prev = current.next.prev
this.length--
return current.element
}
}
}
循環(huán)鏈表：概念：循環(huán)鏈表可以像單向鏈表一樣只有單向引用，也可以向雙向鏈表一樣具有雙向引用。單向循環(huán)鏈表：最后一個元素指向下一個元素的指針(tail.next)不是引用null， 而是指向第一個元素(head)，如下圖所示：
雙向循環(huán)鏈表：最后一個元素指向下一個元素的指針tail.next不是nul，而是指向第一個元素（head），同時第一個元素指向前一個元素的指針head.prev不是null，而是最后一個元素tail。如圖所示：
鏈表的優(yōu)勢：無需移動鏈表中的元素，就能輕松地添加和移除元素。因此，當你需要添加和移除很多元素 時，最好的選擇就是鏈表，而非數(shù)組。
集合：概念：集合是由一組無序且唯一（不能重復）的項組成的。目前在ES6中已經(jīng)內置了Set的實現(xiàn)。集合中常用的一些方法：
add() 添加元素
delete() 刪除元素，返回布爾值，刪除成功返回true,刪除失敗返回false
has() 判斷是否含有某個元素，返回布爾值
clear() 清空set數(shù)據(jù)結構
size 沒有括號，返回此結構長度
在ES6中使用集合：
const arr = [1,2,2,3,3,3,4,4,5]
const str = 'wangjiajiawwwjiajiawwwww'
// 1.添加元素
new Set(arr) // Set{1,2,3,4,5}
new Set(str ) // Set{'w', 'a', 'n', 'g', 'j', 'i'}
new Set(arr).add(8) // Set{1,2,3,4,5,8}
// 2.刪除元素
new Set(arr).delete(2) // true
new Set(arr).delete(9) // false
// 3.判斷是否含有某個元素
new Set(arr).has(2) // true
new Set(arr).has(9) // false
// 4.清空set數(shù)據(jù)結構
new Set(arr).clear() // undefined
// 5.沒有括號，返回此結構長度
new Set(arr).size // 5
在javascript中使用集合：
// hasOwnProperty(propertyName)方法 是用來檢測屬性是否為對象的自有屬性，如果是，返回true，否則返回false; 參數(shù)propertyName指要檢測的屬性名；
// hasOwnProperty() 方法是 Object 的原型方法（也稱實例方法），它定義在 Object.prototype 對象之上，所有 Object 的實例對象都會繼承 hasOwnProperty() 方法。
class Set {
constructor() {
this.items = {}
}
has(value) {
return this.items.hasOwnProperty(value)
}
add(value) {
if (!this.has(value)) {
this.items[value] = value
return true
}
return false
}
remove(value) {
if (this.has(value)) {
delete this.items[value]
return true
}
return false
}
get size() {
return Object.keys(this.items).length
}
get values() {
return Object.keys(this.items)
}
}
const set = new Set()
set.add(1)
console.log(set.values) // ["1"]
console.log(set.has(1)) // true
console.log(set.size) // 1
set.add(2)
console.log(set.values) // ["1", "2"]
console.log(set.has(2)) // true
console.log(set.size) // 2
set.remove(1)
console.log(set.values) // ["2"]
console.log(set.has(1)) // false
set.remove(2)
console.log(set.values) // []
對集合可以執(zhí)行如下操作：并集：對于給定的兩個集合，返回一個包含兩個集合中所有元素的新集合。交集：對于給定的兩個集合，返回一個包含兩個集合中共有元素的新集合。差集：對于給定的兩個集合，返回一個包含所有存在于第一個集合且不存在于第二個集合的元素的新集合。
并集：
并集的數(shù)學概念：集合A和B的并集，表示為A∪B，定義如下：A∪B = { x | x∈A V x∈B }，意思是x（元素）存在于A中，或x存在于B中。如圖：
基于剛才的 Set 類實現(xiàn)一個并集方法：
union(otherSet) {
const unionSet = new Set()
// 先添加其中一個集合的元素放在unionSet中
this.values.forEach((v, i) => unionSet.add(this.values[i]))
// 在把另一個集合的元素放入unionSet中
otherSet.values.forEach((v, i) => unionSet.add(otherSet.values[i]))
return unionSet
}
交集：
并集的數(shù)學概念：集合A和B的交集，表示為A∩B，定義如下：A∩B = { x | x∈A ∧ x∈B }，意思是x（元素）存在于A中，且x存在于B中。如圖：
基于剛才的 Set 類實現(xiàn)一個交集方法：
intersection(otherSet) {
const intersectionSet = new Set()
// 從集合A開始循環(huán)判斷，如果這個元素也在集合B中，那就說明這個元素是集合A,B公有的。這時候把這個元素放到一個新的集合中
this.values.forEach((v, i) => {
if (otherSet.has(v)) {
intersectionSet.add(v)
}
})
return intersectionSet
}
差集：
差集的數(shù)學概念：集合A和B的差集，表示為A-B，定義如下：A-B = { x | x∈A ∧ x?B }，意思是x（元素）存在于A中，且不x存在于B中。如圖：
基于剛才的 Set 類實現(xiàn)一個差集 A-B 的方法：
difference(otherSet) {
// 從集合A開始循環(huán)判斷，如果這個元素不在集合B中。說明這個元素是A私有的，此時把這個元素放入一個新的集合中。
const differenceSet = new Set()
this.values.forEach((v, i) => {
if (!otherSet.has(v)) {
differenceSet.add(v)
}
})
return differenceSet
}
子集：
子集的數(shù)學概念：集合A是B的子集，或者說集合B包含了集合A，如圖：
基于剛才的 Set 類實現(xiàn)一個子集方法：
// 在這里this代表集合A，otherSet代表集合B
subset(otherSet){
if(this.size > otherSet.size){
return false
}else{
// 只要A里面有一個元素不在B里面就說明A不是B的子集，后面元素不用在判斷了
this.values.every(v => !otherSet.has(v))
}
}
字典：
集合、字典、散列表都可以存儲不重復的數(shù)據(jù)。字典以鍵值對的形式存儲數(shù)據(jù)，類似于javascript中的Object對象。
在javascript中實現(xiàn)字典：
class Dictionary {
constructor() {
this.items = {}
}
set(key, value) {
this.items[key] = value
}
get(key) {
return this.items[key]
}
remove(key) {
delete this.items[key]
}
get keys() {
return Object.keys(this.items)
}
get values() {
/*
也可以使用ES7中的values方法
return Object.values(this.items)
*/
// 在這里我們通過循環(huán)生成一個數(shù)組并輸出
return Object.keys(this.items).reduce((r, c, i) => {
r.push(this.items[c])
return r
}, [])
}
}
使用字典：
const dictionary = new Dictionary()
dictionary.set('Wangjiajia', 'Wangjiajia@email.com')
dictionary.set('Wangtongtong', 'Wangtongtong@email.com')
dictionary.set('davide', 'davide@email.com')
console.log(dictionary) // {items:{'Wangjiajia', 'Wangjiajia@email.com','Wangtongtong', 'Wangtongtong@email.com','davide', 'davide@email.com'}}
console.log(dictionary.keys) // ['Wangjiajia','Wangtongtong','davide']
console.log(dictionary.values) // [Wangjiajia@email.com','Wangtongtong@email.com','davide@email.com']
console.log(dictionary.items) // {'Wangjiajia': 'Wangjiajia@email.com','Wangtongtong': 'Wangtongtong@email.com','davide':'davide@email.com'}
哈希表：
-
根據(jù)關鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結構。通過把關鍵碼值映射到表中某個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫散列表。 給定表M，存在函數(shù)f(key)，對任意給定的關鍵字值key，代入函數(shù)后若能得到包含該關鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表，函數(shù)f(key)為哈希(Hash) 函數(shù)。
哈希表示意圖：
哈希表沖突：當通過哈希函數(shù)取得一個哈希值時，很有可能這個值的下標所處的位置上已經(jīng)存放過數(shù)據(jù)，這時候便出現(xiàn)沖突。解決沖突：鏈地址法、開放地址法。
在javascript中實現(xiàn)哈希表：
function HashTable(){
// 初始化哈希列表
// 1. 設置哈希表數(shù)組
this.item = []
// 2. 設置哈希表長度
this.limit = 10
// 3. 設置表中數(shù)據(jù)量
this.total = 0
// 設置哈希函數(shù)
HashTable.prototype.hashFunc = function(key, limit){
let keyvalue = 0
for(let i=0; i<key.length; i++){
keyvalue=keyvalue * 12 + key.charCodeAt(i)
}
//使用取余運算計算hashCode
return keyvalue%limit
}
// 增、改
HashTable.prototype.put = function(key, value){
// 根據(jù)hashCode找到對應下標修改或者添加數(shù)據(jù)
let index = this.hashFunc(key, this.limit)
let arr = this.item[index]
// 如果這個下標所處的位置已經(jīng)存放過數(shù)據(jù)，即arr有值，此時存在哈希表沖突
if(arr){
let completed = false
// 遍歷數(shù)組，如果發(fā)現(xiàn)重名數(shù)據(jù)則直接修改
arr.forEach(item=>{
if(key===item[0]){
completed = true
return item[1] = value
}
})
// 如果沒有重名則在末尾添加新數(shù)據(jù)
if(!completed){
arr.push([key, value])
this.total++
}
}else{
//如果basket為null則重新創(chuàng)建數(shù)組
this.item[index] = [[key, value]]
this.total++
}
}
// 查
HashTable.prototype.get = function(key){
let index = this.hashFunc(key, this.limit)
let basket = this.item[index]
//如果basket為null則沒有對應數(shù)據(jù)
if(basket===undefined){
return null
}else{
//如果有basket, 則遍歷basket，遍歷完沒有對應key則不存在對應數(shù)據(jù)
for(let i = 0; i < basket.length; i++){
if(key===basket[i][0]) return basket[i][1]
}
return null
}
}
// 刪
HashTable.prototype.remove = function(key){
let index = this.hashFunc(key, this.limit)
let basket = this.item[index]
//如果basket為null則沒有對應數(shù)據(jù)
if(!basket){
return null
}else{
//如果有basket, 則遍歷basket，遍歷完沒有對應key則不存在對應數(shù)據(jù)
for(let i = 0; i < basket.length; i++){
if(key===basket[i][0]){
this.total--
return basket.splice(i, 1)
}
}
return null
}
}
//求表長
HashTable.prototype.size = function(){
return this.total
}
//判斷表空
HashTable.prototype.isEmpty = function(){
return this.total===0
}
}
樹：
-
概念：是一種天然具有遞歸屬性的非順序數(shù)據(jù)結構，是一種特殊的圖（無向無環(huán)）。由n個節(jié)點組成，具有一定的層級關系。 -
根結點：樹的最頂端的節(jié)點，根節(jié)點只有一個 -
子節(jié)點：除根節(jié)點之外，并且本身下面還連接有節(jié)點的節(jié)點。 -
葉子結點：自己下面不再連接有節(jié)點的節(jié)點（即末端），稱為葉子節(jié)點（又稱為終端結點），度為0 -
深度：節(jié)點到根結點的節(jié)點數(shù)量
-
高度：所有節(jié)點深度中的最大值
-
普通樹：
-
二叉樹：
- 樹的每個節(jié)點最多只能有兩個子節(jié)點
- 二叉樹可以為空，也就是沒有任何節(jié)點，如果不為空它是由左右子樹兩個不相交的二叉樹組成。
-
二叉搜索樹：
- 非空左子樹的鍵值要小于根結點的鍵值
- 非空右子樹的鍵值要大于根結點的鍵值
- 左右子樹都要是二叉搜索樹
-
滿二叉樹與完全二叉樹
滿二叉樹是每一個節(jié)點都有兩個子節(jié)點，左右子樹呈對稱趨勢。完全二叉樹有的分支不完全對稱。
-
紅黑二叉樹
紅黑二叉樹本質上就是一種二叉搜索樹，在插入和刪除等操作的時候通過特定操作保持二叉樹的平衡。紅黑二叉樹本身是復雜的，但它的最壞情況運行時間也是非常良好的，并且在實踐中是高效的：它可以在O(log n)時間內做查找，插入和刪除，這里的 n 是樹中元素的數(shù)目。
紅黑二叉樹在二叉搜索樹的基礎上必須滿足以下要求：- 節(jié)點必須是紅色的或者黑色的
- 根結點必須是黑色的
- 如果節(jié)點是紅色的，那么他的子節(jié)點必須是黑色的（反之未必）
- 從根節(jié)點到任意一個葉子結點不能有兩個連續(xù)的紅色節(jié)點
- 從任意節(jié)點開始到他的每一個葉子節(jié)點，所有路線上的黑色節(jié)點數(shù)目相同
用javascript實現(xiàn)二叉樹的一些操作：
// 封裝二叉樹節(jié)點
class Node {
constructor(data){
this.data = data
this.left = null
this.right = null
}
}
// 封裝二叉搜索樹
class BinarySearchTree {
constructor(){
this.root = null // 定義二叉樹根節(jié)點
}
// 插入節(jié)點
insert(key){
const newNode = new Node(key)
// 定義插入節(jié)點的函數(shù)，比根節(jié)點小的放左邊，比根節(jié)點大的放右邊
function insertNode(node, newNode){
if(newNode.key < node.key){
// 判斷根節(jié)點的左側是否有節(jié)點，如果沒有節(jié)點則直接插入，如果有節(jié)點則遞歸執(zhí)行insertNode函數(shù)
if(node.left == null){
node.left = newNode
}else{
insertNode(node.left, newNode)
}
}else{
// 判斷根節(jié)點的右側是否有節(jié)點，如果沒有節(jié)點則直接插入，如果有節(jié)點則遞歸執(zhí)行insertNode函數(shù)
if(node.right == null){
node,right = newNode
}else{
insertNode(node.right, newNode)
}
}
}
// 如果是空二叉樹，則插入的節(jié)點就是根節(jié)點，否則正常插入
if(!this.root){
this.root = newNode
}else{
insertNode(this.root, newNode)
}
}
}
二叉搜索樹類的使用：
const tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(5)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(15)
tree.insert(13)
tree.insert(12)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)
二叉樹的遍歷：訪問樹的每一個節(jié)點并對他們進行某種操作的過程
-
前序遍歷：先訪問根節(jié)點，再訪問左節(jié)點，最后訪問右節(jié)點（左右子樹同樣進行該操作，根左右） -
中序遍歷：先訪問左節(jié)點，再訪問根節(jié)點，最后訪問右結點，（左根右） -
后序遍歷：先訪問左節(jié)點，再訪問右節(jié)點，最后訪問根節(jié)點。（左右根）
前序遍歷：
function preorder(root){
// 排除根節(jié)點為空的情況
if(!root) return
// 1. 訪問根節(jié)點
console.log(root.key) // 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
// 2. 遞歸對根節(jié)點的左子樹進行先序遍歷
preorder(root.left)
// 3. 遞歸對根節(jié)點的右子樹進行先序遍歷
preorder(root.right)
}
preorder(tree)
中序遍歷：
const inorder = (root) => {
if(!root) return
// 1. 遞歸對根節(jié)點的左子樹進行中序遍歷
inorder(root.left)
// 2. 訪問根節(jié)點
console.log(root.key) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
// 3. 遞歸對根節(jié)點的右子樹進行中序遍歷
inorder(root.right)
}
inorder(tree)
后序遍歷：
const postorder = (root) => {
if (!root) return
// 1. 遞歸對根節(jié)點的左子樹進行后序遍歷
postorder(root.left)
// 2. 遞歸對根節(jié)點的左子樹進行后序遍歷
postorder(root.right)
// 3. 訪問根節(jié)點
console.log(root.key) // 3 6 5 8 10 9 7 12 14 13 18 25 20 15 11
}
postorder(tree)
搜索最小值和最大值：
最小值在最左邊，最大值在最右邊
function minNum(node) {
const minNode = node => {
return node ? (node.left ? minNode(node.left) : node.key) : null
}
return minNode(node || this.root)
}
function maxNum(node) {
const maxNode = node => {
return node ? (node.right ? maxNode(node.right) : node.key) : null
}
return maxNode(node || this.root)
}
minNum(tree.root) // 3
maxNum(tree.root) // 25
搜索特定的值：
function search(node,key){
const searchNode = (node,key)=>{
if(node === null)return false
if(node.key === key) return true
return searchNode( key < node.key ? node.left : node.right, key)
}
return searchNode(node, key)
}
search(tree.root,3) // true
search(tree.root,3) // false
圖：
- 概念：由一組頂點和連接頂點之間的邊所組成的數(shù)據(jù)結構
- 表示方法： G=(V, E) V是圖G中頂點的集合，E是圖G中邊的集合。
無向圖：連接頂點的邊沒有方向
說明：由一條邊連接起來的頂點，稱為相鄰頂點，比如A和B是相鄰的，A和D是相鄰的，A和C 是相鄰的，A和E不是相鄰的。一個頂點的度，是其相鄰頂點的數(shù)量。例如：A的度為3，E的度為2。如果存在環(huán)稱為有環(huán)圖，如果每兩個頂點之間都存在路徑，則稱圖是連通的。
有向圖：連接頂點的邊有方向
說明： 如果圖中每兩個頂點間在雙向上都存在路徑，則該圖是強連通的。例如，C和D是強連通的， 而A和B不是強連通的。
加權圖：圖的邊被賦予了權值
圖的表示方法：
- 鄰接矩陣
- 鄰接表
鄰接矩陣：
1. 可以通過一個二維數(shù)組來表示圖的結構
2. 當圖為稀疏圖時這個二維數(shù)組許多的空間都會被賦值為0，浪費計算機存儲空間
3. 鄰接矩陣示意圖
說明：用一個二維數(shù)組表示，如果這兩個頂點相鄰，那么這個值就記為1，否則記為0。這種方法可能會記錄很多0，造成計算機性能的浪費。因為即使這個頂點只有一個相鄰頂點，我們也要迭代一整行。例如：上面I頂點。
鄰接表：由一個頂點以及跟這個頂點相鄰的其他頂點列表組成，能夠減少內存消耗。
使用javascript創(chuàng)建圖：
class Graph {
constructor(){
this.vertices = [] // 用來保存頂點的數(shù)組
this.adjList = {} // 用來保存邊的字典，可以直接用一個對象代替。
}
// 添加頂點
addVertex(v){
this.vertices.push(v)
this.adjList[v] = []
}
// 添加邊
addEdge(v,w){
this.adjList[v].push(w)
this.adjList[w].push(v)
}
// 返回字符串
graphToString(){
return this.vertices.reduce((r,v) => {
return this.adjList[v].reduce((r,w) => {
return r + `${w}`
},`${r}\n${v} => `)
},'')
}
}
const graph = new Graph();
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'].forEach(c => graph.addVertex(c))
graph.addEdge('A', 'B')
graph.addEdge('A', 'C')
graph.addEdge('A', 'D')
graph.addEdge('C', 'D')
graph.addEdge('C', 'G')
graph.addEdge('D', 'G')
graph.addEdge('D', 'H')
graph.addEdge('B', 'E')
graph.addEdge('B', 'F')
graph.addEdge('E', 'I')
console.log(graph.graphToString())
圖的遍歷：將圖的每個頂點訪問一次，并且不能有重復的訪問
- 廣度優(yōu)先遍歷（Breadth-first-search BFS）
- 深度優(yōu)先遍歷（Depth-first-search DFS）
廣度優(yōu)先遍歷：隊列，通過將頂點存入隊列中，最先入隊列的頂點先被探索。廣度優(yōu)先搜索算法會從指定的第一個頂點開始遍歷圖，先訪問其所有的相鄰點，就像一次訪問圖的一層。簡單說，就是一層一層地訪問頂點，如下圖所示：
在javascript中實現(xiàn)廣度優(yōu)先遍歷：
breadthFirst(v, callback) {
const read = []
const adjList = this.adjList
let pending = [v || this.vertices[0]]
const readVertices = vertices => {
vertices.forEach(key => {
read.push(key)
pending.shift()
adjList[key].forEach(v => {
if (!pending.includes(v) && !read.includes(v)) {
pending.push(v)
}
})
if (callback) callback(key)
if (pending.length) readVertices(pending)
})
}
readVertices(pending)
}
深度優(yōu)先遍歷：深度優(yōu)先搜索算法將會從第一個指定的頂點開始遍歷圖，沿著路徑直到這條路徑最后一個頂 點被訪問了，接著原路回退并探索下一條路徑。換句話說，它是先深度后廣度地訪問頂點，如下圖所示：
在javascript中實現(xiàn)深度優(yōu)先遍歷：
deepFirst(callback) {
const read = []
const adjList = this.adjList
const readVertices = vertices => {
vertices.forEach(key => {
if (read.includes(key)) return false
read.push(key)
if (callback) callback(key)
if (read.length !== this.vertices.length) {
readVertices(adjList[key])
}
})
}
readVertices(Object.keys(adjList))
}
算法：
排序算法：1.冒泡排序：冒泡排序比較任何兩個相鄰的項，如果第一個比第二個大，則交換它們。最壞的情況下比較n輪，n為數(shù)組的長度。
const arr = [2,4,1,9,8,7,6,5,3]
function bubbleSort(arr){
if(!Array.isArray(arr)){
console.log('請輸入一個數(shù)組！')
return false
}
const len = arr.length
for(let i=0; i<len; i++){
for(let j=0; j<len - i; j++){
if(arr[j] > arr[j+1]){
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
}
}
}
return arr
}
const res = bubbleSort(arr) // [1, 2, 3, 4, 5,6, 7, 8, 9]
模擬圖：
2.快速排序：
// 1. 選擇基準值，一般選擇數(shù)組中間的值并且向下取整
// 2. 定義左右兩個數(shù)組，比基準值小的放在左邊，比基準值大的放在右邊
// 3. 遞歸左右兩個數(shù)組
// 4. 終止條件是左右兩個數(shù)組都只有一個元素
const arr = [49, 38, 65, 97, 76, 13, 27, 49]
function quickSort(arr){
// 終止條件是左右兩個數(shù)組都只有一個元素
if(arr.length<2){
return arr
}
// 定義左右兩個數(shù)組
const leftArr = [],
rightArr = []
// 獲取基準值
const index = Math.floor(arr.length/2)
const baseValue = arr.splice(index,1)
// 比基準值小的放在左邊，比基準值大的放在右邊
for(let i of arr){
if(i < baseValue){
leftArr.push(i)
}else{
rightArr.push(i)
}
}
// 遞歸左右兩個數(shù)組
return [...quickSort(leftArr), ...baseValue, ...quickSort(rightArr)]
}
const res = quickSort(arr)
console.log(res); // [13, 27, 38, 49,49, 65, 76, 97]
3.選擇排序：找到數(shù)據(jù)結構中的最小值并 將其放置在第一位，接著找到第二小的值并將其放在第二位，以此類推。
// 選擇排序：每次找到最小值放在最前面
const arr = [49, 38, 65, 97, 76, 13, 27, 49]
function choseSort(arr){
for(let i=0; i<arr.length; i++){
// 假設最小值元素對應的下標為 i
let minIndex = i
// 尋找最小值
for(let j=i+1; j<arr.length; j++){
if(arr[minIndex] > arr[j]){
minIndex = j
}
}
// 交換數(shù)據(jù)，第一輪交換第一個數(shù)和最小數(shù)的位置，以此類推
[arr[i],arr[minIndex]] = [arr[minIndex],arr[i]]
}
return arr
}
const res = choseSort(arr)
console.log(res); // [13, 27, 38, 49,49, 65, 76, 97]
4.插入排序：對循環(huán)次數(shù)的真正優(yōu)化，將一組無序數(shù)列的左側始終看成是有序的。
// 1. 第一次是首位，因為只有一個元素
// 2. 第二次取出數(shù)組中第二個元素，從后向前遍歷左側的有序數(shù)列，找到第一個比這個數(shù)大的數(shù)，將取出來的數(shù)插到這個數(shù)的前面
// 3. 如果沒有比取出來的數(shù)大的，則將這個數(shù)插在左側有序數(shù)列的最后面
// 4. 重復步驟2,3，每次向后取一個元素
const arr = [49, 38, 65, 97, 76, 13, 27, 49]
function insertSort(arr){
for(let i=1; i<arr.length; i++){
// 取出來的目標數(shù)
let targetNum = arr[i],j = i-1
// 從后向前遍歷
while(arr[j] > targetNum){
// 將目標數(shù)插入到比它大的數(shù)的前面
arr[j+1] = arr[j];
j--
}
// 沒有比目標數(shù)大的數(shù)，則目標數(shù)就在原位，不需要改動
arr[j+1] = targetNum
}
return arr
}
const res = insertSort(arr)
console.log(res); // [13, 27, 38, 49,49, 65, 76, 97]
5.歸并排序：歸并排序是一種分治算法。其思想是將原始數(shù)組切分成較小的數(shù)組，直到每個小數(shù)組只有一 個位置，接著將小數(shù)組歸并成較大的數(shù)組，直到最后只有一個排序完畢的大數(shù)組。
// 合并兩個有序數(shù)組
// 將待排序序列不斷地二分，直到只有一個元素。
// 遞歸地將左右兩個子序列進行歸并排序。
// 合并兩個有序子序列，生成一個新的有序序列。
// 合并地具體操作如下：
// 創(chuàng)建一個臨時數(shù)組，用于存儲合并結果。
// 比較左右兩個子序列的第一個元素，將較小的元素放入臨時數(shù)組，并將對應子序列的指針向后移動一位。
// 重復上述比較和放入操作，直到其中一個子序列為空。
// 將另一個非空子序列的剩余元素依次放入臨時數(shù)組。
// 將臨時數(shù)組的元素復制回原始數(shù)組相應位置。
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
// 示例用法
const arr = [5, 3, 8, 4, 2, 9, 1, 7, 6];
const sortedArr = mergeSort(arr);
console.log(sortedArr); // [1, 2, 3, 4, 5, 6, 7, 8, 9]
搜索算法：順序搜索：最基本的一種搜索算法，就是將數(shù)據(jù)結構中的每一個元素，和我們要找的元素作比較，這種搜索算法非常的低效率。
const arr = [5,4,3,2,1]
const arr = [5,4,3,2,1]
function sequentialSearch(arr, value){
for(let i of arr){
if(i == value)return '搜索到了'
}
return '沒有搜索到'
}
const res = sequentialSearch(arr, 3)
console.log(res,'res=='); // 搜索到了
二分搜索：
// 二分搜索
// 1. 要求被搜索的數(shù)據(jù)結構已經(jīng)排序，選擇中間值
// 2. 如果中間值等于目標值，則找到，算法執(zhí)行完畢
// 3. 如果中間值大于目標值，則說明目標值在中間值的左側，此時在左側在找到中間值，在比較，以此類推
// 4. 如果中間值小于目標值，則說明目標值在中間值的右側，此時在右側在找到中間值，在比較，以此類推
const arr = [1,2,3,4,5,6,7,8]
function BinarySearchTree(arr, value){
// arr是一個已經(jīng)排序好的數(shù)組，如果是無序的先進行排序
let left = 0
let right = arr.length - 1
while(left <= right){
// 中間值的下標
let mid = Math.floor((left + right) / 2)
if(arr[mid] == value){
return `找到了下標為：${mid}`
}else if(arr[i] > value){
right = mid -1
}else{
left = mid +1
}
}
return '找不到目標值'
}
const res = BinarySearchTree(arr,5) // '找到了下標為：4'
const res = BinarySearchTree(arr,9) // '找不到目標值'
斐波那鍥數(shù)列：前兩個數(shù)都為1，從第三個數(shù)字開始是前兩個數(shù)字之和。
function fibonacci(n){
// 要求n是大于0的整數(shù)
if(n < 3){
return 1
}else{
return fibonacci(n-1) + fibonacci(n-2)
}
}
fibonacci(1) // 1
fibonacci(2) // 1
fibonacci(3) // 2
fibonacci(6) // 8
階乘數(shù)列：當前數(shù)等于從1開始乘，一直乘到當前數(shù)字。例如：f(3)=123
function factorial(n){
// 要求n是大于0的整數(shù)
if(n == 1){
return 1
}else{
return factorial(n-1) * n
}
}
factorial(1) // 1
factorial(2) // 2
factorial(3) // 6
factorial(4) // 24
factorial(5) // 120
分治法：它將一個復雜的問題分解成多個相對簡單且獨立的子問題，然后遞歸地解決這些子問題，最后將其合并得到原問題的解，具體步驟為：分解（Divide）：將原問題劃分成多個相同或相似的子問題。這一步驟通常利用遞歸實現(xiàn)。解決（Conquer）：遞歸地解決子問題。如果子問題足夠小，可以直接求解。合并（Combine）：將子問題的解合并成原問題的解。
例如：歸并排序、快速排序
動態(tài)規(guī)劃：它將一個復雜的問題分解成多個相互關聯(lián)的子問題，通過反復求解子問題，來解決原來的問題。
常見動態(tài)規(guī)劃問題有：斐波那鍥數(shù)列，爬樓梯，打家劫舍，背包問題，最長公共子序列問題，硬幣找零，圖的全源最短路徑。
爬樓梯問題：假設你正在爬樓梯。需要 n 階你才能到達樓頂。每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？
// 動態(tài)規(guī)劃，爬樓梯
// 示例 1：
// 輸入：n=2
// 輸出：2
// 解釋：有兩種爬樓梯的方法：
// 1. 1 階 + 1 階
// 2. 2 階
// 示例 2：
// 輸入：n = 3
// 輸出：3
// 解釋：有三種方法可以爬到樓頂。
// 1. 1 階 + 1 階 + 1 階
// 2. 1 階 + 2 階
// 3. 2 階 + 1 階
// 解題思路：可以假設在第n-1個臺階爬一個臺階，或者在第n-2個臺階爬兩個臺階。則問題就變?yōu)榱耍篺(n)=f(n-1) + f(n-2)
// f(n-1) 為爬到第n-1個臺階的辦法，f(n-2)為爬到第n-2個臺階的辦法
// 時間復雜度O（n）
// 空間復雜度O（n）
function climbStairs(n){
// 規(guī)定n是大于等于1的正整數(shù)
if(n==1){
return 1
}else{
// 存放f(n)的數(shù)組
let dp = [1,1]
for(let i=2;i<=n;i++){
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
}
// 優(yōu)化算法：變量替換數(shù)組
// 時間復雜度O（n）
// 空間復雜度O（1）
function climbStairs(n){
if(n==1) return 1
let dp0 = 1,dp1 = 1
for(let i=2;i<=n;i++){
[dp0, dp1] = [dp1, dp0 + dp1]
}
return dp1
}
climbStairs(5) // 8
climbStairs(8) // 34
取值問題：在不同時經(jīng)過兩個相鄰房間的情況下，能夠獲取到的最多錢財
// 示例 1：
// 輸入：[1,2,3,1]
// 輸出：4
// 解釋：1 號房屋 (金額 = 1) ，然后 3 號房屋 (金額 = 3)。
// 獲取到的最高金額 = 1 + 3 = 4 。
// 示例 2：
// 輸入：[2,7,9,3,1]
// 輸出：12
// 解釋：1 號房屋 (金額 = 2), 3 號房屋 (金額 = 9)，接著5 號房屋 (金額 = 1)。
// 獲取到的最高金額 = 2 + 9 + 1 = 12 。
// 解題思路：到第 k 間房能獲取到的最大金額，應該是前 k-2 間房獲取到的最大金額加上第 k 間房的金額。
// 或者是 前 k-1 間房獲取到的最大金額。
// 最終結果就是這兩種情況下取最大值。
// f(k): 前 k 間房獲取的最大值，a(k): 第 k 間房的金額。
// f(k) = Math.max(f(k-2) + a(k), f(k-1))
function getmoney(list){
if(list.length == 0)return 0
// 存放能獲取到的最大金額的數(shù)組,i表示房間數(shù)
let dp = [0, list[0]]
for(let i=2;i<=list.length;i++){
dp[i] = Math.max(dp[i-2] + list[i-1], dp[i-1])
}
return dp[list.length]
}
getmoney([2,5,3,1,9,4,7,6]) // 21
getmoney([2,8,3,1,9,4,7,6]) // 24
貪心算法：期望通過每一個階段的局部最優(yōu)解，從而得到全局最優(yōu)解(只是一種期望，實際上可能并不能得到全局最優(yōu)解)。它不像動態(tài)規(guī)劃那樣計算更大的格局。
貪心算法和動態(tài)規(guī)劃的異同：
相同點：
- 兩者都有最優(yōu)子結構，以及貪心選擇策略（貪心）或重疊子問題（dp）。
- 可以理解貪心算法是特殊的動態(tài)規(guī)劃算法。
不同點：文章來源：http://www.zghlxwxcb.cn/news/detail-563721.html
- 貪心算法應用的范圍較少，求解的是局部最優(yōu)解。每一個階段的最優(yōu)解依賴于上一個階段。最后得到的解是所有局部最優(yōu)解的推斷，并不一定是全局最優(yōu)解，求解過程較快，是一種自上而下的求解過程。
- 動態(tài)規(guī)劃：類似于窮舉法，求解所有可行解，最后通過回溯法獲取全局最優(yōu)解
- 貪心算法求解過程：
將所有候選解按一定規(guī)則排序；
根據(jù)貪心選擇策略（某個循環(huán)實現(xiàn)）判斷個是否選擇到最優(yōu)解中。 - 動態(tài)規(guī)劃求解過程：
①將所有于問題的可行解存儲在一個列表中；
②循環(huán)寫遞推式（可用遞歸寫的部分）
③使用回溯法推出最優(yōu)解。
const coinArr = [1,0.5,5,2,10,50,20,100]
const amount = 43
function changeAmount(coins, amount){
// 把錢幣面額數(shù)組從大到小排序
coins.sort((a,b)=>b-a)
// 存儲找零結果
let result = []
for (let i = 0;i<coinArr.length;i++){
while(amount>=coins[i]){
// 將最大面值放進數(shù)組
result.push(coinArr[i])
// 減去已經(jīng)找零的金額
amount -= coinArr[i]
}
}
// 能找開的時候amount一定是等于零的
if(amount>0){
return '找不開零錢'
}
return result
}
console.log(changeAmount(coinArr,amount));
文章來源地址http://www.zghlxwxcb.cn/news/detail-563721.html
到了這里，關于數(shù)據(jù)結構與算法--javascript（持續(xù)更新中...）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
![Javascript 數(shù)據(jù)結構[入門]](https://imgs.yssmx.com/Uploads/2024/02/636445-1.png)
