數(shù)據(jù)結(jié)構(gòu)與算法
-
入門篇
復(fù)雜度分析
-
時間復(fù)雜度
大O時間復(fù)雜度表示法扎筒，表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢，也叫漸進時間復(fù)雜度酬姆，簡稱時間復(fù)雜度嗜桌。
規(guī)律公式：T(n) = O(f(n))// 求1,2,3,4...N的累加和 var numSum = function(n) { var sum = 0; for(var i=1; i<=n; ++i) { sum = sum + i } return sum } /** 假設(shè)每行代碼執(zhí)行的時間為u nit_time則代碼的執(zhí)行總時間：`T(n) = (2n+1)*unit_time` */ var cal = function(n) { var sum = 0; for(var i=1; i<=n; ++i) { for(var j=1; j<=n; ++j) { sum = sum + i*j } } return sum } /** 假設(shè)每行代碼執(zhí)行的時間為unit_time則代碼的執(zhí)行總時間： T(n) = (2n^2+n+2)*unit_time */
總結(jié)：
- 只關(guān)注循環(huán)執(zhí)行次數(shù)最多的一段代碼
- 加法法則：總復(fù)雜度等于量級最大的那段代碼的復(fù)雜度
- 乘法法則：嵌套代碼的復(fù)雜度等于嵌套內(nèi)外代碼復(fù)雜度的乘積
常見時間復(fù)雜度：
O(1)O(logn)O(nlogn)O(n)O(n^2)-
基礎(chǔ)篇
-
基于數(shù)組實現(xiàn)棧結(jié)構(gòu)
function Stack() { // 棧中的屬性 this.items = [] // 1. 入棧 Stack.prototype.push = function (ele) { this.items.push(ele) } // 2. 出棧 Stack.prototype.pop = function () { return this.items.pop() } // 3. 查看棧頂元素 Stack.prototype.peek = function () { return this.items[this.items.length - 1] } // 4. 判斷棧是否為空 Stack.prototype.isEmpty = function () { return this.items.length === 0 } // 5. 獲取棧中元素的個數(shù) Stack.prototype.size = function () { return this.items.length } // 6. toString Stack.prototype.toString = function () { let resString = '' for (let i = 0; i < this.items.length; i++) { resString += this.items[i] + '' } return resString } } // 測試 // const s = new Stack() // s.push(1) // s.push(20) // s.push(21) // s.push(23) // s.push(1001) // console.log('push==', s) // console.log('peek', s.peek()) // console.log('peek end==', s) // s.pop() // s.pop() // console.log('pop==', s) // console.log('size==', s.size()) // console.log('isEmpty==', s.isEmpty()) // console.log('toString', s.toString())1.1 應(yīng)用
// 棧的應(yīng)用：十進制轉(zhuǎn)二進制 function dec2bin(decNum) { // 1. 創(chuàng)建一個棧 // 2. decNum % 2 取余數(shù)壓入棧 // 3. decNum = decNum / 2 整除后的結(jié)果賦值給decNum // 4. 循環(huán)結(jié)束條件，decNum <= 0 const stack = new Stack() while (decNum > 0) { stack.push(decNum % 2) decNum = Math.floor(decNum / 2) } let res = '' while (!stack.isEmpty()) { res += stack.pop() } return res } // 測試十進制轉(zhuǎn)二進制 console.log(dec2bin(100))- 基于數(shù)組實現(xiàn)隊列
function Queue() { // 屬性 this.items = [] // 1. 向隊尾加入一個或多個元素 Queue.prototype.enqueue = function (ele) { this.items.push(ele) } // 2. 刪除隊列中最前面的一項辞色，并返回被移除的元素（改變原隊列） Queue.prototype.dequeue = function () { return this.items.shift() } // 3. 返回隊列中最前面的一項(不改變原對列) Queue.prototype.front = function () { return this.items[0] } // 4. 檢驗對壘是否為空 Queue.prototype.isEmpty = function () { return this.items.length === 0 } // 5. 查看隊列的元素個數(shù) Queue.prototype.size = function () { return this.items.length } // 6. tosTring Queue.prototype.toString = function () { let resString = '' for (let i = 0; i < this.items.length; i++) { resString += this.items[i] + '' } return resString } } // test // const q = new Queue() // q.enqueue(1) // q.enqueue(2) // q.enqueue(31) // q.enqueue(14) // console.log(q) // q.dequeue() // console.log(q) // console.log(q.isEmpty()) // console.log(q.front()) // console.log(q) // console.log(q.size()) // console.log(q.toString())2.1 隊列的應(yīng)用
// 隊列的應(yīng)用：擊鼓傳花 -> n個人圍成一圈數(shù)數(shù)骨宠，數(shù)到數(shù)字 m 時則退出游戲， // 最后剩下的一個人為勝利者相满，求勝利者是原來那個位置上的人 function passGame(nameList, num) { const queue = new Queue() // 將所有數(shù)據(jù)加入隊列 for (let i = 0; i < nameList.length; i++) { queue.enqueue(nameList[i]) } // 開始數(shù)數(shù)层亿，結(jié)束條件是只剩一個時 while (queue.size() > 1) { // 不是 num 時，取出重新加入到隊尾 for (let j = 0; j < num - 1; j++) { queue.enqueue(queue.dequeue()) } // 是 num 時立美，將其從隊列中刪除 queue.dequeue() } // 獲取剩下的那個人, 求他所在位置 const endName = queue.front() console.log(endName) return nameList.indexOf(endName) } // // 測試 // console.log(passGame(['zs', 'ls', 'ww', '小明', '小凡凡', '小民哥'], 6))-
基于數(shù)組的優(yōu)先隊列
function PriorityQueue() { // 可以看做內(nèi)部類 function QueueElement(element, priority) { this.element = element this.priority = priority } // 屬性 this.items = [] // 1. 實現(xiàn)隊列的插入數(shù)據(jù)方法 PriorityQueue.prototype.enqueue = function (element, priority) { // 1.1 創(chuàng)建 QueueElement 實例 const queueElement = new QueueElement(element, priority) // 1.2 判斷隊列是否為空匿又，為空直接添加 // 如果不為空，循環(huán)判斷建蹄，加入合適位置添加碌更，停止循環(huán) // 如果循環(huán)結(jié)束仍然沒有添加進去，就直接添加到隊尾 if (this.items.length === 0) { this.items.push(queueElement) } else { let added = false for (let i = 0; i < this.items.length; i++) { if (queueElement.priority < this.items[i].priority) { this.items.splice(i, 0, queueElement) added = true break } } if (!added) { this.items.push(queueElement) } } } // 2. 刪除隊列中最前面的一項躲撰，并返回被移除的元素（改變原隊列） PriorityQueue.prototype.dequeue = function () { return this.items.shift() } // 3. 返回隊列中最前面的一項(不改變原隊列) PriorityQueue.prototype.front = function () { return this.items[0] } // 4. 檢驗對列是否為空 PriorityQueue.prototype.isEmpty = function () { return this.items.length === 0 } // 5. 查看隊列的元素個數(shù) PriorityQueue.prototype.size = function () { return this.items.length } // 6. tosTring PriorityQueue.prototype.toString = function () { let resString = '' for (let i = 0; i < this.items.length; i++) { resString += this.items[i].element + '' + this.items[i].priority + ' ' } return resString } } // test // const pq = new PriorityQueue() // pq.enqueue('abc', 1) // pq.enqueue('abc', 10) // pq.enqueue('abc', 120) // pq.enqueue('abc', 101) // pq.enqueue('abc', 21) // console.log(pq.toString()) 實現(xiàn)單鏈表
function LinkedList() { // 內(nèi)部類: 節(jié)點 function Node(data) { this.data = data this.next = null } // 屬性 this.head = null this.length = 0 // 1. 向鏈表尾部添加一個新的項 LinkedList.prototype.append = function (data) { // 創(chuàng)建一個新節(jié)點 const newNode = new Node(data) /** * 判斷是否是第一個節(jié)點针贬，如果是讓 head 直接指向新節(jié)點 * 如果不是第一個節(jié)點，就要循環(huán)拢蛋，直到 next -> null * 這里定義了 current 變量代指循環(huán)過程中的節(jié)點，最終循環(huán)結(jié)束找到最后一個節(jié)點蔫巩，current.next -> 新節(jié)點 */ if (this.length === 0) { this.head = newNode } else { let current = this.head while (current.next) { current = current.next } current.next = newNode } this.length += 1 } // 2. 向鏈表特定的位置插入一個新的項 LinkedList.prototype.insert = function (position, data) { /** * 情況一：插入position為0的位置谆棱，先把新節(jié)點的 next 指向 head快压，再讓 head 指向新節(jié)點 * 情況二：0 < position <= this.length 循環(huán)賦值前一個節(jié)點 previous 和 當前節(jié)點 current * 讓前一個節(jié)點指向添加的新節(jié)點，添加的新節(jié)點指向 current */ // 對 position 做越界處理 if (position < 0 || position > this.length || typeof position != 'number') return false // 創(chuàng)建一個新節(jié)點 const newNode = new Node(data) if (position === 0) { newNode.next = this.head this.head = newNode } else { let index = 0 let current = this.head let previous = null while (index++ < position) { previous = current current = current.next } newNode.next = current previous.next = newNode } this.length += 1 return true } // 3. 獲取對應(yīng)位置的元素 LinkedList.prototype.get = function (position) { // 越界判斷 if (position < 0 || position >= this.length || typeof position != 'number') return null // 獲取對應(yīng)的 data 循環(huán)鏈表垃瞧，移動 current let current = this.head let index = 0 while (index++ < position) { current = current.next } return current.data } // 4. 返回元素在鏈表中的索引蔫劣，如果鏈表中沒有該元素返回-1 LinkedList.prototype.indexOf = function (data) { // 定義指針變量和index let current = this.head let index = 0 // 開始查找 while (current) { if (current.data === data) return index current = current.next index += 1 } return -1 } // 5. 修改鏈表中某個位置的元素 LinkedList.prototype.update = function (position, newData) { // 越界判斷 if (position < 0 || position >= this.length || typeof position != 'number') return false // 查找節(jié)點 let current = this.head let index = 0 while (index++ < position) { current = current.next } // 將 current 指向的node節(jié)點的data修改為新的data current.data = newData return true } // 6. 從鏈表中的特定位置移除一項 LinkedList.prototype.removeAt = function (position) { /** * 情況一：刪除 position 為 0 的位置的元素，直接將原來的head指向head.next * 情況二：0 < position < this.length 循環(huán)獲取上一個節(jié)點和當前節(jié)點个从，直接讓上一個節(jié)點的next指向當前節(jié)點的next */ // 越界判斷 if (position < 0 || position >= this.length || typeof position != 'number') return null // position 為0脉幢，head 直接指向之前指向的下一個 let current = this.head if (position === 0) this.head = this.head.next else { let index = 0 let previous = null while (index++ < position) { previous = current current = current.next } // 前一個節(jié)點的 next 不在指向current，而是指向current.next previous.next = current.next } this.length -= 1 return current.data } // 7. 從鏈表中移除一項 LinkedList.prototype.remove = function (data) { // 1. 獲取data在鏈表中的位置 let position = this.indexOf(data) // 2. 根據(jù)位置信息嗦锐，刪除節(jié)點 return this.removeAt(position) } // 8. 判斷鏈表是否為空嫌松，true or false LinkedList.prototype.isEmpty = function () { return this.length === 0 ? true : false } // 9. 返回鏈表中的元素個數(shù) LinkedList.prototype.size = function () { return this.length } // 10. 輸出元素的值 toString LinkedList.prototype.toString = function () { let current = this.head let listStr = '' while (current) { listStr += current.data + ' ' current = current.next } return listStr } } // test // const list = new LinkedList() // console.log(list.isEmpty()) // // 添加 // list.append(1) // list.append(2) // list.append(3) // list.append(4) // // insert // list.insert(3, '111') // list.insert(5, '222') // list.insert(0, '000') // // update // list.update(0, 'ccc') // console.log(list.toString()) // console.log(list.get(6)) // console.log(list.indexOf('ccc')) // console.log(list.removeAt(0)) // console.log(list.toString()) // console.log(list.remove(1)) // console.log(list.toString()) // console.log(list.size()) // console.log(list.isEmpty())- 實現(xiàn)雙向鏈表
function DoublyLinkedList() { // 節(jié)點類 function Node(data) { this.data = data this.prev = null this.next = null } // 屬性 this.head = null this.tail = null this.length = 0 // 1. 向列表尾部添加一個新的項 DoublyLinkedList.prototype.append = function (data) { // 創(chuàng)建一個新節(jié)點 const newNode = new Node(data) /** * 判斷是否是第一個節(jié)點，如果是讓 head奕污，tail 都指向 newNode * 如果不是第一個節(jié)點萎羔， 新節(jié)點newNode.prev = tail 之前尾部節(jié)點 tail.next = newNode * 再將尾部節(jié)點指向新節(jié)點 tail = newNode */ if (this.length === 0) { this.head = newNode this.tail = newNode } else { newNode.prev = this.tail this.tail.next = newNode this.tail = newNode } this.length += 1 } // 2. 向列表特定位置插入一個新的項 DoublyLinkedList.prototype.insert = function (position, data) { /** * 情況一：列表為空的情況（length = 0） tail指向newNode，head指向newNode * 情況二：position = 0 原來節(jié)點的 prev 指向 newNode * 新節(jié)點 newNode.next 指向原來的節(jié)點 * head指針指向新的節(jié)點 newNode * 情況三：position = length 則與 append 的邏輯相同 * 情況四： 0 < position < length 循環(huán)找到替換位置的節(jié)點碳默， * 新節(jié)點 prev 指向找到節(jié)點的上一個節(jié)點(即是：current.prev)贾陷， * 新節(jié)點的next 指向找到的節(jié)點（current) * 找到節(jié)點的上一個節(jié)點的next指向新節(jié)點（current.prev.next -> newNode） * 找到的節(jié)點的 prev 指向新的節(jié)點 */ // 對 position 做越界處理 if (position < 0 || position > this.length || typeof position != 'number') return false // 創(chuàng)建新節(jié)點 const newNode = new Node(data) if (this.length === 0) { this.head = newNode this.tail = newNode } else { if (position === 0) { this.head.prev = newNode newNode.next = this.head this.head = newNode } else if (position === this.length) { newNode.prev = this.tail this.tail.next = newNode this.tail = newNode } else { let current = this.head let index = 0 while (index++ < position) { current = current.next } // 修改指針 newNode.next = current newNode.prev = current.prev current.prev.next = newNode current.prev = newNode } } this.length += 1 return true } // 3. 獲取對應(yīng)位置的元素 DoublyLinkedList.prototype.get = function (position) { // 對 position 做越界處理 if (position < 0 || position >= this.length || typeof position != 'number') return null // 優(yōu)化: 利用length/2與position比較，判斷是從后往前還是從前往后循環(huán) let poor = this.length / 2 - position // 循環(huán)嘱根，找到與 position 對應(yīng)的項 let current = null if (poor > 0) { current = this.head let index = 0 while (index++ < position) { current = current.next } } else { current = this.tail let index = this.length - 1 while (index-- > position) { current = current.prev } } return current.data } // 4. 返回元素在鏈表中的索引髓废，如果鏈表中沒有該元素返回-1 DoublyLinkedList.prototype.indexOf = function (data) { // 循環(huán)（結(jié)束條件current -> null) 找到 current.data = data 結(jié)束，返回index let current = this.head let index = 0 while (current) { if (current.data === data) { return index } current = current.next index += 1 } return -1 } // 5. 修改列表中某個位置的元素 DoublyLinkedList.prototype.update = function (position, newData) { // 對 position 做越界處理 if (position < 0 || position >= this.length || typeof position != 'number') return false // 優(yōu)化: 利用length/2與position比較该抒，判斷是從后往前還是從前往后循環(huán) let poor = this.length / 2 - position // 循環(huán)瓦哎，找到與 position 對應(yīng)的項 let current = null if (poor > 0) { current = this.head let index = 0 while (index++ < position) { current = current.next } } else { current = this.tail let index = this.length - 1 while (index-- > position) { current = current.prev } } current.data = newData return true } // 6. 從列表中特定位置移除某一項 DoublyLinkedList.prototype.removeAt = function (position) { /** * 情況一：刪除節(jié)點只有一個，則head和tail指向null * 情況二：列表不止一個節(jié)點柔逼，刪除的節(jié)點為第一個position = 0, * head 指向的節(jié)點的下一個節(jié)點的prev指向 null * head 指向原來指向節(jié)點的下一個接點 head -> head.next * 情況三： 列表不止一個節(jié)點蒋譬，刪除的節(jié)點是最后一個節(jié)點 position = length-1 * tail指向節(jié)點的上一個節(jié)點的next 指向 null * tail指向上一個節(jié)點的 prev * 情況四：0 < position < length-1 * 從前往后循環(huán)，找到 current愉适，current的上一個節(jié)點直接指向它的下一個節(jié)點 * current的下一個節(jié)點的prev直接指向它的上一個節(jié)點 */ // 對 position 做越界處理 if (position < 0 || position >= this.length || typeof position != 'number') return null // 放到全局 let current = this.head // 只有一個節(jié)點 if (this.length === 1) { this.head = null this.tail = null } else { if (position === 0) { this.head.next.prev = null this.head = this.head.next } else if (position === this.length - 1) { current = this.tail this.tail.prev.next = null this.tail = this.tail.prev } else { let index = 0 while (index++ < position) { current = current.next } current.prev.next = current.next current.next.prev = current.prev } } this.length -= 1 return current.data } // 7. 從列表中移除一項 DoublyLinkedList.prototype.remove = function (data) { // 根據(jù)data獲取index let index = this.indexOf(data) // 根據(jù)index刪除 return this.removeAt(index) } // 8. 判斷列表是否為空 return false or true DoublyLinkedList.prototype.isEmpty = function () { return this.length === 0 } // 9. size 返回鏈表包含的元素個數(shù) DoublyLinkedList.prototype.size = function () { return this.length } // 10. toSting DoublyLinkedList.prototype.toString = function () { return this.backwardString() } // 11. 返回向前遍歷的節(jié)點字符串形式 DoublyLinkedList.prototype.forwardString = function () { let current = this.tail let resStr = '' // 依次向前遍歷犯助，獲取每個節(jié)點，移動指針 while (current) { resStr += current.data + '' current = current.prev } return resStr } // 12. 返回向后遍歷的節(jié)點字符串形式 DoublyLinkedList.prototype.backwardString = function () { let current = this.head let resStr = '' // 依次向后遍歷维咸，獲取每個節(jié)點剂买，移動指針 while (current) { resStr += current.data + '' current = current.next } return resStr } // 13. 獲取鏈表第一個元素 DoublyLinkedList.prototype.getHead = function () { return this.head.data } // 14. 獲取鏈表最后一個元素 DoublyLinkedList.prototype.getTail = function () { return this.tail.data } } // test // let list = new DoublyLinkedList() // list.append('111') // list.append('122') // list.append('333') // list.append('444') // list.append('555') // console.log(list) // console.log(list.backwardString()) // console.log(list.forwardString()) // console.log(list.toString()) // list.insert(2, 'aaaa') // list.insert(0, 'ccc') // list.insert(5, 'zzz') // console.log(list.toString()) // console.log(list.size()) // console.log(list.get(7)) // console.log(list.indexOf('zzz')) // console.log(list.update(5, 'ggg')) // console.log(list.update(8, 'ttt')) // console.log(list.toString()) // console.log(list.removeAt(1)) // console.log(list.toString()) // console.log(list.remove(122)) // console.log(list.toString()) // console.log(list.isEmpty()) // console.log(list.getHead()) // console.log(list.getTail())
-
-
