前端必会算法(一)
前端数据结构与算法
数组
数组是数据结构最简单的一种，几乎所有的编程语言都支持，而在JavaScript中，数组存在着其他语言没有的方法，以至于通过数组演化而来的堆和栈结构实现起来十分轻松
数组的初始化
定义数组有很多种方式
1、new Array(1,2,3,4)
2、let arr=[1,2,3,4]
数组的增删改
增：
arr.push() 尾加
arr.unshift()头加
arr.splice(index,0,item) //意思为，在指定位置删除0个元素，加入一个元素item
删除
arr.pop() 尾删
arr.shift()头删
arr.splice(index,1) //从下标为index的元素删除一个，不添加新元素
改：arr.splice(index,1,item) 下表为index的1个元素删掉，并且加入item 从而实现修改
所以如果想删除数组中某一位置的元素，可以使用indexOf获取到下标，在执行arr.splice(index,1)操作
栈
栈（stack）是一种运算受限的线性表，可以在数组的任意位置插入和删除元素。但是有时候，我们为了实现某些功能，必须对这种任意性加以限制。栈和队列就是比较常见的受限的线性结构。
栈是一种线性表，LIFO（last in first out）先进后出
·栈只允许操作最末尾的数据，称之为栈顶操作
·栈允许进行增加或者删除，我们称之为压栈，出栈
-
向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
-
从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
我们来简单实现一个栈结构
栈常见的操作
push()添加一个新元素到栈顶位置。pop()移除栈顶的元素，同时返回被移除的元素。peek()返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）。isEmpty()如果栈里没有任何元素就返回true，否则返回false。size()返回栈里的元素个数。这个方法和数组的length属性类似。toString()将栈结构的内容以字符串的形式返回。
我们不难看出，JavaScript实现栈结构显得十分轻松，因为独特的数组的操纵方法
function Stack() {
this.arr = [];
this.push = function (value) {
this.arr.push(value);
};
this.pop = function () {
return this.arr.pop();
};
this.peek = function () {
return this.arr[this.arr.length - 1];
};
this.isEmpty = function () {
return this.arr.length === 0;
};
this.size = function () {
return this.arr.length;
};
this.toString = function () {
return this.arr.toString();
};
this.escStack = function () { //弹栈并且记录弹出的顺序和数据
let result = this.arr.slice(); //这里只考虑浅拷贝 拷贝第一层的数据，如果第一层数据存在引用类型，请替换为深拷贝
while (!this.isEmpty()) {
this.pop();
}
return result.reverse().join("");
};
}
let stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.arr); //[ 1, 2, 3 ]
stack.pop();
console.log(stack.peek()); //2
console.log(stack.size());//2
console.log(stack.arr);//[ 1, 2 ]
console.log(stack.toString());//1,2
深拷贝方法
function deepClone(target) {
let restult
if (typeof target === 'object') {
if (Array.isArray(target)) {
restult = []
for (const i in target) {
restult.push(deepClone(target[i]))
}
} else if (target == null) {
restult = null
} else if (target.constructor === RegExp || target.constructor === Date) {
restult = target
} else {
//说明是一个对象
restult = {}
for (const i in target) {
restult[i] = (deepClone(target[i]))
}
}
} else {
restult = target
}
return restult
}
利用栈结构的特性，我们试着写一个除二取余法实现十进制转化为二进制（逆序输出）
function moreTwo(numb) {
let stack = new Stack();
while (numb > 0) {
stack.push(numb % 2);
numb = Math.floor(numb / 2);
}
return stack.escStack();
}
console.log(moreTwo(10086)); //10011101100110
队列
队列（Queue）是一种运算受限的线性表，特点：先进先出 (FIFO：First In First Out)。
受限之处：
-
只允许在表的前端（front）进行删除操作。
-
只允许在表的后端（rear）进行插入操作。
-
类似于生活中排队
队列的实现
-
enqueue(element)向队列尾部添加一个（或多个）新的项。 -
dequeue()移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。 -
front()返回队列中的第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息与 Map 类的 peek 方法非常类似）。 -
isEmpty()如果队列中不包含任何元素，返回true，否则返回false。 -
size()返回队列包含的元素个数，与数组的 length 属性类似。 -
toString()将队列中的内容，转成字符串形式。不难发现，队列的实现也十分的轻松
function Queue() { this.arr = []; this.enqueue = function (value) { this.arr.push(value); }; this.dequeue = function () { return this.arr.shift(); }; this.front = function () { return this.arr[0]; }; this.isEmpty = function () { return this.arr.length === 0; }; this.size = function () { return this.arr.length; }; this.toString = function () { return this.arr.toString(); }; } const queue = new Queue(); // enqueue() 测试 queue.enqueue("a"); queue.enqueue("b"); queue.enqueue("c"); queue.enqueue("d"); console.log(queue.arr); // ["a", "b", "c", "d"] // dequeue() 测试 queue.dequeue(); queue.dequeue(); console.log(queue.arr); //["c", "d"] // front() 测试 console.log(queue.front()); // c // isEmpty() 测试 console.log(queue.isEmpty()); //false // size() 测试 console.log(queue.size()); //2 // toString() 测试 console.log(queue.toString()); // c d队列应用
击鼓传花小游戏，传入一人名数据和第几个就淘汰的数字，记录淘汰人员的数据和顺序，最后当场上只剩下一个人的时候，返回胜利者与淘汰队列。淘汰的需要移除队列
function Game(list, number) { let queue = new Queue(); let deletes = []; //记录失败的人和失败的人的顺序 for (let i = 0; i < list.length; i++) { //入队 queue.enqueue(list[i]); } while (queue.size() > 1) { //当场上只剩下一个人的时候游戏结束 for (let i = 0; i < number - 1; i++) { //将出队的人重新加入道队列中去 queue.enqueue(queue.dequeue()); } //一圈结束后，第number个人淘汰，并且将淘汰的人移除，并放入淘汰队列 deletes.push(queue.dequeue()); //删除 } //当场上只剩下最后一个人的时候，将胜利者和淘汰人员返回 return [queue.front(), deletes]; } const names = ["lily", "lucy", "tom", "tony", "jack"]; const result = Game(names, 4); console.log(`击鼓传花，胜利者${result[0]} 失败者顺序${result[1]}`); //击鼓传花，胜利者lily 失败者顺序tony,tom,jack,lucy优先队列
优先队列需要考虑的问题 元素不仅仅是一个数据，还包括优先级
再添加元素的过程中，会根据优先级的不同，添加的位置也不同
优先队列实现
function PriorityQueue() { this.queue = []; this.addEqeue = function (element, priority) { let obj = { element, priority }; for (let i = 0; i < this.queue.length; i++) { //找到第一个比新增数据权重要小的 if (this.queue[i].priority > obj.priority) { this.queue.splice(i, 0, obj); //添加到这个位置的下一个 return; } } this.queue.push(obj); //如果不存在则直接添加到末尾 }; // // 删除队列中优先级最高的元素 this.dequeue = function () { if (this.isEmpty()) { return "Underflow"; } return this.queue.shift(); }; // // 查看队列中优先级最高的元素 this.front = function () { if (this.isEmpty()) { return "No elements in Queue"; } return this.queue[0]; }; // // 检查队列是否为空 this.isEmpty = function () { return this.queue.length === 0; }; // // 清空队列 this.clear = function () { this.queue = []; }; // // 打印队列元素 this.printQueue = function () { let str = ""; for (let i = 0; i < this.queue.length; i++) { str += this.queue[i].element + " "; } return str; }; } let priorityQueue = new PriorityQueue(); priorityQueue.addEqeue("task1", 1); priorityQueue.addEqeue("task2", 2); priorityQueue.addEqeue("task3", 3); console.log(priorityQueue.printQueue()); // 应输出: task1 task2 task3 priorityQueue.addEqeue("task4", 1.5); console.log(priorityQueue.printQueue()); // 应输出: task1 task4 task2 task3 console.log("Dequeue: ", priorityQueue.dequeue()); // 应输出: Dequeue: { element: 'task1', priority: 1 } console.log(priorityQueue.printQueue()); // 应输出: task4 task2 task3俩表
链表
数组与链表的区别
数组的创建需要申请一段连续的内存空间 (一整块内存)，并且大小是固定的，当前数组不能满足容量需求时，需要扩容。 (一般情况下是申请一个更大的数组，比如 2 倍，然后将原数组中的元素复制过去)
在数组开头或中间位置插入数据的成本很高，需要进行大量元素的位移。
而链表呢
-
存储多个元素，另外一个选择就是使用链表。
-
不同于数组，链表中的元素在内存中不必是连续的空间。
-
链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用 (有些语言称为指针) 组成。
-
链表优点：
内存空间不必是连续的，可以充分利用计算机的内存，实现灵活的内存动态管理。
链表不必在创建时就确定大小，并且大小可以无限延伸下去。
链表在插入和删除数据时，时间复杂度可以达到 O(1)，相对数组效率高很多。
-
链表缺点：
访问任何一个位置的元素时，需要从头开始访问。(无法跳过第一个元素访问任何一个元素)
无法通过下标值直接访问元素，需要从头开始一个个访问，直到找到对应的元素。
虽然可以轻松地到达下一个节点，但是回到前一个节点是很难的。
常见操作
append(element)向链表尾部添加一个新的项。insert(position, element)向链表的特定位置插入一个新的项。get(position)获取对应位置的元素。indexOf(element)返回元素在链表中的索引。如果链表中没有该元素就返回 -1。update(position, element)修改某个位置的元素。removeAt(position)从链表的特定位置移除一项。remove(element)从链表中移除一项。isEmpty()如果链表中不包含任何元素，返回trun，如果链表长度大于 0 则返回false。size()返回链表包含的元素个数，与数组的 length 属性类似。toString()由于链表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。
单向链表
append方法
class LinkedList {
length = 0;
head = null;
Node = class {
data;
next = null;
constructor(data) {
this.data = data;
}
};
append(data) {
//默认往链表最后添加
let newNode = new this.Node(data);
if (this.length == 0) {
//当链表没有数据的时候，加入的第一个数据便是头部
this.head = newNode;
} else {
//否则的话，不断循环，直至找到最后一个节点，最后一个节点如果没有下一个节点的话为null
let currentHead = this.head;
while (currentHead.next != null) {
currentHead = currentHead.next;
}
currentHead.next = newNode; //将倒数第二个节点的next指向新添加的
}
this.length++; //长度增加
}
}
const linkedList = new LinkedList();
// 测试 append 方法
linkedList.append("A");
linkedList.append("B");
linkedList.append("C");
console.log(linkedList);
初始化的时候，链表没有数据，所以第一个加入的数据就替代了头部的
通过while循环，找到当前链表的最后一个节点，并将这个节点的next指向将要添加的新节点
最后一个节点指向null
一、链表
未完待续.....
转载自:https://juejin.cn/post/7366646873463832617