我的春招之前端面试常见手写算法题(很详细！！！)

卷帘依旧
874 阅读10分钟

我的春招从3月份持续到4月底，身边的同学陆陆续续拿到offer，参加了远程实习，我却还0 offer 0 job，绝望的心情可想而知，但还是坚持到了最后，收到作业帮第一个oc之后情况渐渐明朗起来，之后也有收到其它公司的offer，付出总算是有了结果。所以我把自己总结的一些面试题写到个人博客上，记录下自己的求职点滴，也希望自己的经历能够帮助到同样挣扎在前端路上的你。

这篇文章里总结了前端面试中一些常见的常考的算法题，个人总结，如有疏漏，请大家不吝赐教

如果这篇文章对你有帮助，欢迎关注、点赞、评论、转发😁

1. 手撕快排(★★★★★)

真的hin常见，我面试的过程中遇到过很多次，美团、百度面试中都遇到了

function quickSort(arr) {
    quick_sort_helper(arr, 0, arr.length - 1)
}

function quick_sort_helper(arr, l, r) {
    if (l < r) {
        var mid = partition(arr, l, r);
        quick_sort_helper(arr, 0, mid-1);
        quick_sort_helper(arr, mid+1, r);
    }
}

function partition(arr, l, r) {
    var target = arr[l];
    var i = l, j = r;

    while (i < j) {
        while (j > i && arr[j] >= target) j--;
        arr[i] = arr[j];
        while (j > i && arr[i] <= target) i++;
        arr[j] = arr[i];
    }

    arr[i] = target;
    return i;
}

arr = [1,3,2,8,5]
quickSort(arr);
console.log(arr)

[1,2,3,5,8]

2. javascript中的继承(★★★★★)

继承方式 优点 缺陷
原型链继承 能够实现函数复用 1.引用类型的属性被所有实例共享；2.创建子类时不能向超类传参
借用构造函数 1. 避免了引用类型的属性被所有实例共享; 2. 可以在子类中向超类传参 方法都在构造函数中定义了，每次创建实例都会创建一遍方法，无法实现函数复用
组合继承 融合了原型链继承和构造函数的优点，是Javascript中最常用的继承模式 创建子类会调用两次超类的构造函数
原型继承 在没有必要兴师动众地创建构造函数，而只是想让一个对象与另一个对象保持类似的情况下，原型式继承完全可以胜任 引用类型的属性会被所有实例共享
寄生式继承 可以增强对象 使用寄生式继承来为对象添加函数，会由于不能做到函数复用造成效率降低，这一点与构造函数模式类似；同时存在引用类型的属性被所有实例共享的缺陷
寄生组合继承 复制了超类原型的副本，而不必调用超类构造函数 ( 既能够实现函数复用，又能避免引用类型实例被子类共享，同时创建子类只需要调用一次超类构造函数) 没有缺点

具体可查看 js继承的实现

3. 防抖和节流(★★★★)

防抖

function debounce(handler, delay) {
    var time;
    delay = delay || 1000
    return function(){
        var _args = arguments
        var _self = this

        time && clearTimeout(time)
        time = setTimeout(() => {
            handler.call(_self, _args)
        }, delay)
    }
}

节流

function throttle(handler, delay) {
    var lastTime = Date.now()
    var id;
    return function(){
        var _args = arguments
        var _self = this

        var curTime = Date.now()
        console.log('curTime - lastTime=',curTime - lastTime)
        if (curTime - lastTime >= delay) {
            if (id){
                clearTimeout(id);
            }
            handler.apply(_self, _args)
            lastTime = Date.now()
        } else {
            id && clearTimeout(id);//把上一次的定时器清除
            id = setTimeout(() => {
                handler.apply(_self, _args)
            }, 2000);
        }
    }
}

4. 深拷贝(★★★)

function deepClone(obj) {
    let types = new Set(['boolean', 'string', 'number', 'undefined']);
    let _type = typeof obj;
    if (_type in types || obj === null) {
        return obj;
    }

    let objClone = Array.isArray(obj) ? [] : {};
    for(let key in obj) {
        if (obj.hasOwnProperty(key)) {
            objClone[key] = (typeof(obj[key]) === 'object') ? deepClone(obj[key]) : obj[key]
        }
    }

    return objClone;
}

let a = {
    name: 'lucy',
    others: {
        title: 'student',
        level: 666
    }
}
let b = deepClone(a);
a.others.title = 'teacher';
console.log(b.others.title) // student

5. 元素水平垂直居中(★★★★★★)

太太太太太常见的面试题了，腾讯、百度、富途。。。，被问到过好多次了，需要重点掌握

  • 1.flex布局
<style>
.main {
    display: flex;
    justify-content: center;
    align-items: center;
}
</style>

<div class="main">
    <div class="center"></div>
</div>
  • 2.相对定位
<style>
.center {
    position: relative;
    top: 50%;
    left: 50%;
    transform: translate(-50%, -50%);
}
</style>

<div class="main">
    <div class="center"></div>
</div>
  • 3.绝对定位
<style>
.main {
    position: relative;
}
.center {
    position: absolute;
    top: 50%;
    left: 50%;
    transform: translate(-50%, -50%);
}
</style>

<div class="main">
    <div class="center"></div>
</div>
  • 4.如果元素宽高已知，则2,3中的transform可以换成margin: -0.5*height 0 0 -0.5*width，也就是通过设置margin为负值来实现反向移动
  • 5.通过margin实现水平居中，通过relative定位实现垂直居中
<style>
.center {
    position: relative;
    top: 50%;
    margin: 0 auto;
    transform: translateY(-50%);
}
</style>

<div class="main">
    <div class="center"></div>
</div>

6. 两栏布局(★★★)

两栏布局：左侧宽度固定，右侧自适应

DOM结构：

<div class="main">
    <div class="left">左边</div>
    <div class="right">右边</div>
</div>
  • 方式一
.left {
    float: left;
    width: 300px;
    background-color: rebeccapurple;
}

.right {
    background-color: rgb(206, 65, 225);
}
  • 方式二
.main1 {
    display: flex;
}

.left1 {
    width: 300px;
    flex-shrink: 0;
    flex-grow: 0;
    background-color: rgb(153, 129, 51);
}

.right1 {
    flex: 1;
    background-color: royalblue;
}
  • 方式三
.main2 {
    position: relative;
    width: 100%;
}

.left2 {
    position: absolute;
    width: 300px;
    left: 0;
    background-color: rgb(51, 153, 97);
}

.right2 {
    position: absolute;
    right: 0;
    left: 300px;
    background-color: rgb(166, 65, 225);
}

7. 三栏布局(★)

我在面试中没遇到过考察三栏布局的，但还是放到这里供大家参考吧

  • 圣杯布局

    • 7-1 浮动实现
    <!DOCTYPE html>
    <html lang="en">
    <head>
        <meta charset="UTF-8">
        <title>Document</title>
        <style type="text/css">
        *{
            margin: 0;
            padding: 0;
            font-size: 45px
        }
        #container .column {
            float: left;
        }
        #container {
            background-color: yellowgreen;
            padding-left: 200px;
            padding-right: 400px;
        }
        #center{
            background: red;
            width: 100%
        }
        #left{
           background: pink ;
           width: 200px;
           margin-left: -100%;
           position: relative;
           right: 200px;
        }
        #right{
           background: blue ;
           width: 400px;
           margin-right: -400px;
        }
        .header, .footer {
            width: 100%;
            background-color: #c1c1c1;
            clear: both;
        }
    </style>
    </head>
    <body>
        <div class="header">header</div>
        <div id="container">
            <div id="center" class="column">中间</div>
            <div id="left" class="column">左边</div>
            <div id="right" class="column">右边</div>
        </div>
        <div class="footer">footer</div>
    </body>
    </html>
    • 7-2 绝对定位
    <!DOCTYPE html>
    <html lang="en">
    <head>
        <meta charset="UTF-8">
        <title>Document</title>
        <style type="text/css">
            * {
                margin: 0;
                padding: 0;
                color: black;
                font-size: 45px
            }
    
            .main {
                background: red;
                position: relative;
                padding-left: 200px;
                padding-right: 200px;
            }
    
            .center {
                width: 100%;
                background: pink
            }
    
            .left {
                background: yellow;
                width: 200px;
                position: absolute;
                left: 0;
                top: 0;
            }
    
            .right {
                background: blue;
                width: 200px;
                position: absolute;
                top: 0;
                right: 0
            }
        </style>
    </head>
    <body>
        <div class="main">
            <div class="center">中间</div>
            <div class="left">左</div>
            <div class="right">右</div>
        </div>
    </body>
    </html>
    • 7-3 flex实现
    <!DOCTYPE html>
    <html lang="en">
    <head>
        <meta charset="UTF-8">
        <title>Document</title>
        <style type="text/css">
        *{
            margin: 0;
            padding: 0;
            color: black;
            font-size: 45px
        }
    
        body {
            display: flex;
            flex-direction: column;
        }
        header, footer {
            flex: 0 0 50px;
            background-color: pink;
        }
        .main {
            display: flex;
            flex: 1;
            background-color: yellowgreen;
        }
        .left, .right {
            flex-shrink: 0;
            flex-flow: 0;
        }
        .left {
            width: 200px;
            background-color: red;
            order: -1;
        }
        .center {
            width: 100%;
            background-color: blue;
        }
        .right {
            width: 400px;
            background-color: green;
        }
        
    </style>
    </head>
    <body>
        <header>头部</header>
        <div class="main">
            <div class="center">中间</div>
            <div class="left">左</div>
            <div class="right">右</div>
        </div>
        <footer>底部</footer>
    </body>
    </html>

  • 双飞翼布局

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>双飞翼布局</title>
</head>
<style>
    *{
        margin: 0;
        padding: 0;
        color: black;
        font-size: 45px
    }

    .col {
        float: left;
    }

    .main {
        width: 100%;
        background-color: yellowgreen;
    }
    .center {
        margin-left: 200px;
        margin-right: 400px;
    }
    .left {
        width: 200px;
        margin-left: -100%;
        background-color: rebeccapurple;
    }
    .right {
        width: 400px;
        margin-left: -400px;
        background-color: blue;
    }
</style>
<body>
    <div class="container">
        <div class="main col">
            <div class="center">中间</div>
        </div>
        <div class="left col">左边</div>
        <div class="right col">右边</div>
    </div>
</body>
</html>

圣杯布局 V.S. 双飞翼布局

  • 双飞翼布局使用margin，圣杯布局使用padding

  • 圣杯布局缺陷：会发生变形（main小于left时）

  • 双飞翼布局缺陷：多了一层DOM节点

8. 实现一个简单的观察者模式(★★★★)

class Subject {
    constructor(){
        this.state = 0
        this.observers = []
    }

    getState(){
        return this.state
    }

    setState(state){
        this.state = state
        this.notifyAllObservers()
    }

    attach(observer) {
        this.observers.push(observer)
    }

    notifyAllObservers(){
        this.observers.forEach(observer => {
            observer.update()
        })
    }
}

class Observer{
    constructor(name, subject) {
        this.name = name
        this.subject = subject
        this.subject.attach(this)
    }

    update(){
        console.log(`${this.name} update, state: ${this.subject.getState()}`)
    }
}

let s = new Subject()
let o1 = new Observer('o1', s)
let o2 = new Observer('o2', s)
let o3 = new Observer('o3', s)

s.setState(1)
s.setState(2)
s.setState(3)

o1 update, state: 1
o2 update, state: 1
o3 update, state: 1
o1 update, state: 2
o2 update, state: 2
o3 update, state: 2
o1 update, state: 3
o2 update, state: 3
o3 update, state: 3

9. 实现一个发布订阅模式(★★★★)

class Event{
    constructor(){
        
    }

    handlers = {};

    on(type, handler){
        if (!(type in this.handlers)) {
            this.handlers[type] = [];
        }
        this.handlers[type].push(handler);
    }

    emit(type, ...params){
        if (!(type in this.handlers)) {
            return new Error('未注册!')
        }

        this.handlers[type].forEach(handler => {
            handler(...params);
        });
    }

    // 移除
    remove(type, handler){
        if (!(type in this.handlers)) {
            return new Error('无效事件');
        }

        if (!handler) { // 没有指明handler，移除type
            delete this.handlers[type];
        } else {
            const idx = this.handlers[type].findIndex(ele => ele === handler);
            if (idx === undefined) {
                return new Error('no')
            }
            this.handlers[type].splice(idx, 1);
            if (this.handlers[type].length === 0) {
                delete this.handlers[type];
            }
        }
    }
}

function load(params){
    console.log('load', params)
}

function foo(params){
    console.log('foo...', params)
}

var event = new Event();
event.on('load', load);
event.on('load', foo);

// 触发
event.emit('load', 'load触发')

// 移除foo
event.remove('load', foo);
event.emit('load')

> "load" "load触发"
> "foo..." "load触发"
> "load" "params"

10. 数组去重

// 方法一：indexOf
arr = [2,3,4,5,3,4,2,6,4]
 
function removeDup(arr) {
    arrNew = []
    for(let item of arr) {
        if (arrNew.indexOf(item) === -1) {
            arrNew.push(item)
        }
    }
    return arrNew
}
arr = removeDup(arr)
console.log(arr)
 
// 方法二：indexOf --ES5常用 --O(n^2)事件复杂度
arr = [2,3,4,5,3,4,2,6,4]
function removeDup_1(arr) {
    for(let i = 1; i < arr.length; i++) {
        for(let j = i - 1; j >= 0; j--) {
            if (arr[i] == arr[j]) {
                arr.splice(i, 1) // 删除操作会改变数组长度
                i = i - 1 // 每次删除一个数字，都应该将指针前移
            }
        }
    }
}
removeDup_1(arr)
console.log(arr)
 
// 方法3：filter+indexOf
arr = [2,3,4,5,3,4,2,6,4]
function removeDup_2(arr) {
    return arr.filter((item, index, arr) => {
        return arr.indexOf(item, 0) === index // 判断item第一次出现的位置与当前位置是否一致
    })
}
arr = removeDup_2(arr)
console.log(arr)
 
//方法4：Set
arr = [2,3,4,5,3,4,2,6,4]
arr = [...new Set(arr)]
//或
arr = Array.from(new Set(arr))
 
//方法5：Map
arr = [2,3,4,5,3,4,2,6,4]
function removeDup_3(arr) {
    let map = new Map()
    let arrN = []
 
    for(let item of arr) {
        if (!map.has(item)) {
            map.set(item, true) // map没有该key值
            arrN.push(item)
        }
    }
 
    return arrN
}
 
arr = removeDup_3(arr)
console.log(arr)
 
// 方法6--利用排序
function removeDup(arr) {
    arr.sort() // sort()函数默认按照字符编码的顺序进行排序，会对元素进行字符串转换；如果想按其它标准排序，则需要提供比较函数
 
    let arrN = [arr[0]]
 
    for(let i = 1; i < arr.length; i++) {
        if (arr[i] !== arr[i-1]) {
            arrN.push(arr[i])
        }
    }
 
    return arrN;
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}]
arr = removeDup(arr) 
console.log(arr)

11. 数组扁平化

  • 1.正则表达式
var arr=[1, [3, [2, 3, [6, 5]]]];
var str = JSON.stringify(arr)
var res = str.replace(/\[|\]/g,'')
res = '['+res+']'
res = JSON.parse(res)
console.log(res)
  • 2.调用数组内置的方法 flat()
var arr=[1, [3, [2, 3, [6, 5]]]];
var res = arr.flat(Infinity)
console.log(res)
  • 3.递归实现
function flatArr(arr, res) {
    for(let item of arr) {
        if (typeof item === 'number') {
            res.push(item)
        } else {
            flatArr(item, res)
        }
    }
}

var arr1=[1, [3, [2, 3, [6, 5]]]];
var res = [];
flatArr(arr1, res);
console.log(res)
  • 4.用 reduce 函数实现
var arr1=[1, [3, [2, 3, [6, 5]]]];
var myFlatten =  arr => arr.reduce((res, cur) => {
    return res.concat(Array.isArray(cur) ? myFlatten(cur) : cur)
},[])
console.log(myFlatten(arr1))
avatar
文章
阅读
粉丝