陕西荣天建设网站,网站后缀ga,江西网站开发多少钱,交互做的很好的网站前言数据结构是计算机存储、组织数据的方式,算法是系统描述解决问题的策略。了解基本的数据结构和算法可以提高代码的性能和质量。也是程序猿进阶的一个重要技能。手撸代码实现栈,队列,链表,字典,二叉树,动态规划和贪心算法1.数据结构篇1.1 栈栈的特点#xff1a;先进后出clas…前言数据结构是计算机存储、组织数据的方式,算法是系统描述解决问题的策略。了解基本的数据结构和算法可以提高代码的性能和质量。也是程序猿进阶的一个重要技能。手撸代码实现栈,队列,链表,字典,二叉树,动态规划和贪心算法1.数据结构篇1.1 栈栈的特点先进后出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); // 8stack.push(11);console.log(stack.size); // 3console.log(stack.isEmpty); // false1.2 队列队列先进先出 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); // truequeue.enqueue(John);queue.enqueue(Jack);queue.enqueue(Camila);console.log(queue.size); // 3console.log(queue.isEmpty); // falsequeue.dequeue();queue.dequeue();1.3 链表链表:存贮有序元素的集合,但是不同于数组,每个元素是一个存贮元素本身的节点和指向下一个元素引用组成要想访问链表中间的元素,需要从起点开始遍历找到所需元素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;}// 寻找元素下标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;}// 转为字符串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 字典字典类似对象以keyvalue存贮值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)*/// 在这里我们通过循环生成一个数组并输出return Object.keys(this.items).reduce((r, c, i) {r.push(this.items[c]);return r;}, []);}}const dictionary new Dictionary();dictionary.set(Gandalf, gandalfemail.com);dictionary.set(John, johnsnowemail.com);dictionary.set(Tyrion, tyrionemail.com);console.log(dictionary);console.log(dictionary.keys);console.log(dictionary.values);console.log(dictionary.items); 1.5 二叉树特点每个节点最多有两个子树的树结构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);}}//访问树节点的三种方式:中序,先序,后序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 动态规划特点通过全局规划,将大问题分割成小问题来取最优解案例最少硬币找零美国有以下面额(硬币d11, d25, d310, d425如果要找36美分的零钱我们可以用1个25美分、1个10美分和1个便士 1美分)class MinCoinChange {constructor(coins) {this.coins coinsthis.cache {}
}makeChange(amount) {if (!amount) return []if (this.cache[amount]) return this.cache[amount]let min [], newMin, newAmountthis.coins.forEach(coin {newAmount amount - coinif (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 贪心算法特点通过最优解来解决问题用贪心算法来解决2.3中的案例class MinCoinChange2 {constructor(coins) {this.coins coins
}makeChange(amount) {const change []let total 0this.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))
