摘要:序列文章面試之函數(shù)面試之對象面試之?dāng)?shù)組的幾個不操作面試之對比分析前言數(shù)據(jù)結(jié)構(gòu)是計算機(jī)存儲組織數(shù)據(jù)的方式算法是系統(tǒng)描述解決問題的策略。了解基本的數(shù)據(jù)結(jié)構(gòu)和算法可以提高代碼的性能和質(zhì)量。
序列文章
JS面試之函數(shù)(1)
JS面試之對象(2)
JS面試之?dāng)?shù)組的幾個不low操作(3)
JS面試之http0.9~3.0對比分析(4)
數(shù)據(jù)結(jié)構(gòu)是計算機(jī)存儲、組織數(shù)據(jù)的方式,算法是系統(tǒng)描述解決問題的策略。了解基本的數(shù)據(jù)結(jié)構(gòu)和算法可以提高代碼的性能和質(zhì)量。1.數(shù)據(jù)結(jié)構(gòu)篇 1.1 棧
也是程序猿進(jìn)階的一個重要技能。
手?jǐn)]代碼實現(xiàn)棧,隊列,鏈表,字典,二叉樹,動態(tài)規(guī)劃和貪心算法
棧的特點:先進(jì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 = []; } } // 實例化一個棧 const stack = new Stack(); console.log(stack.isEmpty); // true // 添加元素 stack.push(5); stack.push(8); // 讀取屬性再添加 console.log(stack.peek); // 8 stack.push(11); console.log(stack.size); // 3 console.log(stack.isEmpty); // false1.2 隊列
隊列:先進(jìn)先出
class Queue { constructor(items) { this.items = items || []; } enqueue(element) { this.items.push(element); } 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.toString()); } } const queue = new Queue(); console.log(queue.isEmpty); // true queue.enqueue("John"); queue.enqueue("Jack"); queue.enqueue("Camila"); console.log(queue.size); // 3 console.log(queue.isEmpty); // false queue.dequeue(); queue.dequeue();1.3 鏈表
鏈表:存貯有序元素的集合,
但是不同于數(shù)組,每個元素是一個存貯元素本身的節(jié)點和指向下一個元素引用組成
要想訪問鏈表中間的元素,需要從起點開始遍歷找到所需元素
class Node { constructor(element) { this.element = element; this.next = null; } } // 鏈表 class LinkedList { constructor() { this.head = null; this.length = 0; } // 追加元素 append(element) { const node = new Node(element); let current = null; if (this.head === null) { this.head = node; } else { current = this.head; while (current.next) { current = current.next; } current.next = node; } this.length++; } // 任意位置插入元素 insert(position, element) { if (position >= 0 && position <= this.length) { const node = new Node(element); let current = this.head; let previous = null; let index = 0; if (position === 0) { this.head = node; } else { while (index++ < position) { previous = current; current = current.next; } node.next = current; previous.next = node; } this.length++; return true; } return false; } // 移除指定位置元素 removeAt(position) { // 檢查越界值 if (position > -1 && position < length) { 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; } return null; } // 尋找元素下標(biāo) findIndex(element) { let current = this.head; let index = -1; while (current) { if (element === current.element) { return index + 1; } index++; current = current.next; } return -1; } // 刪除指定文檔 remove(element) { const index = this.indexOf(element); return this.removeAt(index); } isEmpty() { return !this.length; } size() { return this.length; } // 轉(zhuǎn)為字符串 toString() { let current = this.head; let string = ""; while (current) { string += ` ${current.element}`; current = current.next; } return string; } } const linkedList = new LinkedList(); console.log(linkedList); linkedList.append(2); linkedList.append(6); linkedList.append(24); linkedList.append(152); linkedList.insert(3, 18); console.log(linkedList); console.log(linkedList.findIndex(24));1.4 字典
字典:類似對象,以key,value存貯值
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("Gandalf", "gandalf@email.com"); dictionary.set("John", "johnsnow@email.com"); dictionary.set("Tyrion", "tyrion@email.com"); console.log(dictionary); console.log(dictionary.keys); console.log(dictionary.values); console.log(dictionary.items);1.5 二叉樹
特點:每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)
class NodeTree { constructor(key) { this.key = key; this.left = null; this.right = null; } } class BinarySearchTree { constructor() { this.root = null; } insert(key) { const newNode = new NodeTree(key); const insertNode = (node, newNode) => { if (newNode.key < node.key) { if (node.left === null) { node.left = newNode; } else { insertNode(node.left, newNode); } } else { if (node.right === null) { node.right = newNode; } else { insertNode(node.right, newNode); } } }; if (!this.root) { this.root = newNode; } else { insertNode(this.root, newNode); } } //訪問樹節(jié)點的三種方式:中序,先序,后序 inOrderTraverse(callback) { const inOrderTraverseNode = (node, callback) => { if (node !== null) { inOrderTraverseNode(node.left, callback); callback(node.key); inOrderTraverseNode(node.right, callback); } }; inOrderTraverseNode(this.root, callback); } min(node) { const minNode = node => { return node ? (node.left ? minNode(node.left) : node) : null; }; return minNode(node || this.root); } max(node) { const maxNode = node => { return node ? (node.right ? maxNode(node.right) : node) : null; }; return maxNode(node || this.root); } } 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(13); tree.insert(12); tree.insert(14); tree.inOrderTraverse(value => { console.log(value); }); console.log(tree.min()); console.log(tree.max());2.算法篇 2.1 冒泡算法
冒泡排序,選擇排序,插入排序,此處不做贅述,請戳 排序
2.2 斐波那契特點:第三項等于前面兩項之和
function fibonacci(num) { if (num === 1 || num === 2) { return 1 } return fibonacci(num - 1) + fibonacci(num - 2) }2.3 動態(tài)規(guī)劃
特點:通過全局規(guī)劃,將大問題分割成小問題來取最優(yōu)解
案例:最少硬幣找零
美國有以下面額(硬幣):d1=1, d2=5, d3=10, d4=25
如果要找36美分的零錢,我們可以用1個25美分、1個10美分和1個便士( 1美分)
class MinCoinChange { constructor(coins) { this.coins = coins this.cache = {} } makeChange(amount) { if (!amount) return [] if (this.cache[amount]) return this.cache[amount] let min = [], newMin, newAmount this.coins.forEach(coin => { newAmount = amount - coin if (newAmount >= 0) { newMin = this.makeChange(newAmount) } if (newAmount >= 0 && (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) { min = [coin].concat(newMin) } }) return (this.cache[amount] = min) } } const rninCoinChange = new MinCoinChange([1, 5, 10, 25]) console.log(rninCoinChange.makeChange(36)) // [1, 10, 25] const minCoinChange2 = new MinCoinChange([1, 3, 4]) console.log(minCoinChange2.makeChange(6)) // [3, 3]2.4 貪心算法
特點:通過最優(yōu)解來解決問題
用貪心算法來解決2.3中的案例
class MinCoinChange2 { constructor(coins) { this.coins = coins } makeChange(amount) { const change = [] let total = 0 this.coins.sort((a, b) => a < b).forEach(coin => { if ((total + coin) <= amount) { change.push(coin) total += coin } }) return change } } const rninCoinChange2 = new MinCoinChange2 ( [ 1, 5, 10, 25]) console.log (rninCoinChange2. makeChange (36))
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/103310.html
摘要:快速排序是一種劃分交換排序。快速排序基于冒泡遞歸分治。他在大數(shù)據(jù)情況下是最快的排序算法之一,平均事件復(fù)雜度很低而且前面的系數(shù)很小,在大量隨機(jī)輸入的情況下最壞情況出現(xiàn)的概率是極小的。 快速排序是一種劃分交換排序。它采用了一種分治的策略,通常稱其為分治法。 分治法的基本思想是:將原問題分解為若干個規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題,然后將這些子問題的解組合為原問題的解。...
摘要:序列文章面試之函數(shù)面試之對象面試之?dāng)?shù)組的幾個不操作面試之對比分析面試之?dāng)?shù)據(jù)結(jié)構(gòu)與算法前言設(shè)計模式如果應(yīng)用到項目中,可以實現(xiàn)代碼的復(fù)用和解耦,提高代碼質(zhì)量。 showImg(https://segmentfault.com/img/bVbq2VA?w=480&h=260); 序列文章 JS面試之函數(shù)(1)JS面試之對象(2)JS面試之?dāng)?shù)組的幾個不low操作(3)JS面試之http0.9~...
摘要:動態(tài)定義間隔序列參考來源詳細(xì)介紹了十種算法大家可以去學(xué)習(xí)下以后大概會盡量每天更新一個算法學(xué)習(xí)吧溫故而知新 參考書:嚴(yán)蔚敏-數(shù)據(jù)結(jié)構(gòu) 希爾排序(Shells Sort) 希爾排序又稱縮小增量排序,歸屬于插入排序一類,簡單來說,和我們的插入排序比,它更快. 奇妙的記憶點: 內(nèi)排序(內(nèi)存排序就夠了) 不穩(wěn)定(排序后原始順序無法保證) 希爾排序重點在于分割. 基本思想: 將整個待排序記錄序...
摘要:面試中,經(jīng)常遇到的一個簡單算法題查找兩個單鏈表的公共節(jié)點最近在讀源碼的時候發(fā)現(xiàn)一個樹中對該算法的運用見函數(shù),在此做簡單的記錄。地址在樹中獲取當(dāng)前實例節(jié)點的父節(jié)點實例組件對應(yīng)的,比如的表示為類組件,其為對應(yīng)元素。 面試中,經(jīng)常遇到的一個簡單算法題:查找兩個單鏈表的公共節(jié)點最近在讀react源碼的時候發(fā)現(xiàn)一個react樹中對該算法的運用(見getLowestCommonAncestor函數(shù)...
閱讀 2065·2021-10-11 10:59
閱讀 924·2021-09-23 11:21
閱讀 3541·2021-09-06 15:02
閱讀 1610·2021-08-19 10:25
閱讀 3364·2021-07-30 11:59
閱讀 2362·2019-08-30 11:27
閱讀 2574·2019-08-30 11:20
閱讀 2964·2019-08-29 13:15