前端算法知识零散学习（面试篇）
学习资料：
前端算法训练营
https://leetcode-cn.com/
https://u.geekbang.org/lesson/47?article=213891
Javascript中的栈（stack）、队列（queue）、堆（heap）
栈（stack）
栈的特点是“LIFO,即后进先出（Last in first out）”。数据存储时只能从顶部逐个存入，取出时也需从顶部逐个取出。
图示：
栈示意图
理解：栈就像一个竖着放置的烧杯，往里面装一层一层的东西，需要使用的时候只能从上层一层的拿。即先进后出，后进先出。
JavaScript中数组模拟栈：
var arr = [0,1,2,3,4]
//存入数据
arr.push(5) //arr = [0,1,2,3,4,5]
//取出数据
arr.pop() // arr = [0,1,2,3,4]
队列（queue）
队列的特点是“FIFO,即先进先出（First in first out）”。
数据存取时从队尾插入，从队头取出。
队列与栈的区别：
栈的存入和取出都在顶部一个口，而队列存入与取出分两个，一个入口，一个出口。
队列示意图
理解：队列就像一个横着放置的水管一样，水从一头流向另一头，先进水管的水先流出来，后进的水后流出来。即先进先出，后进后出。
JavaScript数组模拟队列：
var arr = [0,1,2,3,4]
// 进队列（队尾）
arr.push(5) // arr = [0,1,2,3,4,5]
//出队列（队头）
arr.shift(); // arr = [1,2,3,4,5]
堆（heap）
堆的特点是“无序”的key-value“键值对”存储方式。
图示：
堆就像一个书架，当我们需要某一本书时，通过知道书名，拿着书名在书架中查找对应的书，类似于在键值对中拿key找对应的value。
堆的存取方式跟顺序没有关系，不局限出入口。
栈、堆、队列在JavaScript中的应用
1. 代码运行方式（栈应用）
JavaScript中函数的执行过程，其实就是一个入栈出栈的过程：
1. 当脚本要调用一个函数时，JS解析器就把该函数推入栈中（push）并执行。
2. 当函数运行结束后，JS解析器将它从栈中推出（pop）
function foo () {
function bar () {
return 'I am bar';
}
return bar();
}
foo();
函数执行入栈出栈示意图
2. 内存存储（栈、堆）
JavaScript中变量类型有两种：
基础类型：Number, Boolean, String, Null, Undefined, Symbol
引用类型：Object
JS中的基础数据类型存在栈中，引用类型存在堆中，JS不允许直接访问堆中的位置，因此，在栈中有一个指向堆的地址，可以通过该地址去操作堆中的引用数据。
数据存储
3. 事件轮询（队列）
JavaScript时间轮询机制（Event Loop）,就是采用队列的存取方式。简易理解为，主线程上优先执行同步任务，当遇到异步任务时，将其存入异步队列中，当主线程的同步任务执行完成，反过来按照顺序执行异步队列中的任务。异步队列就用到队列的存取方式。
为什么会有栈内存和堆内存之分？
通常是为了使程序在运行时占用内存最小，与垃圾回收机制有关。
当一个方法执行时，每个方法都会建立自己的内存栈，在这个方法中定义的变量都会逐个放入这块栈内存中，随着方法的执行结束，这个方法的内存栈也将自然销毁。因此在方法中定义的变量都是存在栈内存中。
当我们在程序中创建一个对象时，这个对象将被保存在运行时数据区中，以便反复利用，（因为对象创建成本比较高）这个运行时数据区就是堆内存。堆内存中的对象不会随着方法的结束而销毁，即使方法结束后，这个对象还可能被另一个引用变量所引用，则这个对象不会被销毁，只有当一个对象没有任何引用变量引用它时，系统的垃圾回收机制才会核实回收。
常见算法题
目前这块还没想好怎么学，先每天写一道题吧（事实证明由于懒惰，好久好久不写题）。
1. 验证一个数是否是素数（素数：质数又称素数，一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数）
//answer1
function IsPrime(num){
if(!(typeof num == "number") || num<=1){
console.log(new Error("请输入一个大于1的数字"))
return
}
var count = 0;
var i = num;
while(i>0){
if(num%(i--) === 0){
count++;
}
}
if(count>2){
return false
}else{
return true
}
}
这样做开销很大，不是比较好的办法。
下面这种先判断特殊情况，2和3之后对偶数进行处理（所有偶数都不是素数），之后取数字的平方根，判断这个数能否被3-平方根之间的任一整数整除，如果不能则为素数，否则不是素数，被除数可以没每次递增2（排除偶数）这样就可以减少很多计算。
//answer2
function IsPrime(){
if(num == 2 || num == 3){
return true;
}
if(num%2 === 0){
return false;
}
var divisor = 3; //被除数
var sqrt = Math.sqrt(num);
whild(sqrt > divisor){
if(num % divisor === 0){
return false
}else{
divisor +=2
}
}
return true;
}
-
斐波那契数列：用js函数实现获取斐波那契数列第N个值。
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=1，F(1)=1, F(n)=F(n-1)+F(n-2)（n>2，n∈N*）
递归版：
function Fibonacci(n){
if(n<=1){
return 1
}
return Fibonacci(n-1)+Fibonacci(n-2)
}
循环版：
function Fibonacci(n){
if(n<2){
return 1;
}
var nac1 = 1;
var nac2 = 1;
var temp = 0;
for(var i = 2; i<=n; i++){
temp = nac1;
nac1 = nac2;
nac2 = temp + nac2;
}
return nac2
}
循环+解构赋值版：
function Fibonacci(n){
if(n<2){
return 1;
}
var nac1 = 1;
var nac2 = 1;
for(var i = 2; i<=n; i++){
[nac1,nac2]=[nac2,nac1+nac2]
}
return nac2
}
- 求两个数中的最大公约数最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个(12,16)=4
//Greatest Common Divisor(GCD)
function getGcd(a,b){
if(a < 2 || b < 2){
return 1;
}
var divisor = 2;
var res = 1;
while(a>divisor && b>divisor){
if(a%divisor === 0 && b%divisor === 0){
res = divisor;
}
divisor++;
}
return res;
}
- 冒泡排序 2020-06-04(面试，感觉好累)
function BubleSort(arr){
var len = arr.length;
for(var i = 1; i<len; i++){
for(var j = 0; j<len-i; j++){
if(arr[j]>arr[j+1]){
arr[j+1] = [arr[j],arr[j] = arr[j+1]][0]
}
}
}
return arr;
}
- 数组去重
- 利用Set数据类型
function uniqArray(arr){
let set = new Set(arr);
let uniq = Array.from(set);
return uniq;
}
- 利用对象key值不能重复
function uniqArray(arr){
let obj = {};
for(var i = 0; i<arr.length; i++){
obj[arr[i]] = i;
}
let uniq = Object.keys(obj);
return uniq;
}
- 双层for循环，不生成新数组
function uniq(arr) {
for(let i = 0; i < arr.length; i++){
for(let j = i+1; j < arr.length; j++){
if(arr[i] === arr[j]){
arr.splice(j, 1);
j--;
}
}
}
return arr;
}
- 检索新数组中是否包含项
function uniqArray(arr) {
let uniq = [];
arr.forEach((item,index) => {
if(!(uniq.includes(item))){
uniq.push(item);
}
})
return uniq;
}
- 实现一个深拷贝
function deepClone(origin){
let target = {};
for(let key in origin){
if(typeof origin[key] === 'object'){
target[key] = deepClone(origin[key])
}else{
target[key] = origin[key]
}
}
return target
}
- 实现一个快速排序（递归版）
function quickArray(array){
if(array.length <= 0) {
return array;
}
let left = [];
let right = [];
let medium = array.shift();
for(let i = 0; i < array.length; i++ ) {
if(array[i] < medium) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return quickArray(left).concat(medium, quickArray(right));
}
let arr = [3,1,6,4,8,6,0,332,33,66,45,64,100];
let sortresult = quickArray(arr);
待续。。。
写在最后：文中内容大多为自己平时从各种途径学习总结，文中参考文章大多收录在我的个人博客里，欢迎阅览http://www.tianleilei.cn
