前端算法知识零散学习（面试篇）

学习资料：
前端算法训练营
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）,就是采用队列的存取方式。简易理解为，主线程上优先执行同步任务，当遇到异步任务时，将其存入异步队列中，当主线程的同步任务执行完成，反过来按照顺序执行异步队列中的任务。异步队列就用到队列的存取方式。

为什么会有栈内存和堆内存之分？
通常是为了使程序在运行时占用内存最小，与垃圾回收机制有关。
当一个方法执行时，每个方法都会建立自己的内存栈，在这个方法中定义的变量都会逐个放入这块栈内存中，随着方法的执行结束，这个方法的内存栈也将自然销毁。因此在方法中定义的变量都是存在栈内存中。

当我们在程序中创建一个对象时，这个对象将被保存在运行时数据区中，以便反复利用，（因为对象创建成本比较高）这个运行时数据区就是堆内存。堆内存中的对象不会随着方法的结束而销毁，即使方法结束后，这个对象还可能被另一个引用变量所引用，则这个对象不会被销毁，只有当一个对象没有任何引用变量引用它时，系统的垃圾回收机制才会核实回收。

参考：
数据结构与算法（面试相关）
js中的栈、堆、队列、内存空间
前端进击的巨人（一）：执行上下文与执行栈，变量对象

常见算法题

目前这块还没想好怎么学，先每天写一道题吧（事实证明由于懒惰，好久好久不写题）。
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;
}
  1. 斐波那契数列：用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
}
  1. 求两个数中的最大公约数最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个(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;
}
  1. 冒泡排序 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;
}
  1. 数组去重
  • 利用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;
}
  1. 实现一个深拷贝
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
}
  1. 实现一个快速排序（递归版）
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);

目前算法题参考:https://www.cnblogs.com/djw12333/p/11647413.html

待续。。。

写在最后：文中内容大多为自己平时从各种途径学习总结，文中参考文章大多收录在我的个人博客里，欢迎阅览http://www.tianleilei.cn

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,921评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,635评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,393评论 0赞 338
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,836评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,833评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,685评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,043评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,694评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 42,671评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,670评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,779评论 1赞 332
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,424评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,027评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,984评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,214评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,108评论 2赞 351
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,517评论 2赞 343