前端面试经典算法题

/* function TreeNode(x) {this.val = x;this.left = null;this.right = null;} */function Mirror(root){if(root===null) {return;}if(root.left === null && root.right === null) {return;}let pTe.

祥哥的说

7181人浏览 · 2021-02-21 20:05:41

祥哥的说 · 2021-02-21 20:05:41 发布

文章目录

一、二叉树相关题目

二、超出数组长度一半的数组元素

在这里插入图片描述

function MoreThanHalfNum_Solution(numbers)
{
   let out = 0;
   let obj = {};
   let length = numbers.length / 2;
   numbers.forEach(item => {
       !obj[item] ? obj[item] = 1 : obj[item]++
   });
   for(let [key, value] of Object.entries(obj)) {
       if(value > length ) {
           out = key;
       }
   }
    return out;
}

三、斐波那契、跳台阶

在这里插入图片描述

在这里插入图片描述


function Fibonacci(n)
{
   if(n==0||n==1) {
       return n;
   }
    let a=0,b=1,c;
    for(let i=2;i<=n;i++){
        c = a+b;
        a = b;
        b = c;
    }
    return c;
}

在这里插入图片描述
https://www.cnblogs.com/evenleee/p/8474465.html

在这里插入图片描述

四、 js 模拟call、apply、bind实现

https://www.cnblogs.com/mengfangui/p/10502962.html

1、 js 模拟call

//f.call(o)其原理就是先通过 o.m = f 将 f作为o的某个临时属性m存储，然后执行m，执行完毕后将m属性删除。
// o.m=f;
// o.m();
// delete o.m;

Function.prototype.myCall = function (context) {
  var context = context || window
  // 给 context 添加一个属性
  context.fn = this
  // 将 context 后面的参数取出来
  var args = [...arguments].slice(1)
  var result = context.fn(...args)
  // 删除 fn
  delete context.fn
  return result
}

2、js模拟apply

Function.prototype.myApply = function (context) {
  var context = context || window
  context.fn = this

  var result
  // 需要判断是否存储第二个参数
  // 如果存在，就将第二个参数展开
  if (arguments[1]) {
    result = context.fn(...arguments[1])
  } else {
    result = context.fn()
  }

  delete context.fn
  return result
}

3、js模拟bind

模拟bind函数：

var sun={
	name:"aaa"
}
var rrr={
	name:"ddd",
	show:function(age){
		console.log(this.name,age);
	}
}
// 在函数原型上加上一个新方法
Function.prototype.newbind = function(context) {
	// 作用域缓存
    let me = this;
    // 获取函数的传递参数，下面使用时，要除去第一个参数项，该项为指定的对象
    let args = Array.from(arguments);
    return function() {
        return me.apply(context, args.slice(1));
    }
}
rrr.show.newbind(sun,23)(); //VM684:7 aaa 23

五、手写防抖函数和节流函数

在这里插入图片描述

// 防抖
// 防抖的应用：输入框输入
// 核心思路：只在500ms毫秒之后开始处理事件，只要在500ms内有触发，就会清空定时器，重新计时，或者到500ms，处理完事件之后清空，
function debounce(fn, delay = 500) {
    let timer = null
    return function () {
        if (timer) {
            clearTimeout(timer)
        }
        timer = setTimeout(() => {
            fn();
            timer = null
        }, delay)
    }
}

input1.addEventListener('keyup', debounce(function (e) {
    console.log(e.target)
    console.log(input1.value)
}, 500))

节流：
在这里插入图片描述

// 节流
// 应用：连续触发的事件，需要定间隔定频率触发
// 核心思想：只要在100ms内，那我就直接把你return出去，没到100ms我就重新再设置一个100ms的间隔来执行
function throttle(fn, delay = 100) {
    let timer = null

    return function () {
        if (timer) {
            return
        }
        timer = setTimeout(() => {
            fn.apply(this, arguments)
            timer = null
        }, delay)
    }
}

div1.addEventListener('drag', throttle(function (e) {
    console.log(e.offsetX, e.offsetY)
}))

div1.addEventListener('drag', function(event) {

})

六、数组扁平化处理

1、递归实现

function flat(arr){
    // 是否还有嵌套数组
    const isDeep = arr.some(item => item instanceof Array);
    if(!isDeep) {
        return arr;
    }
    // 数组扁平化处理
    const res = [].concat(...arr);
    //递归的使用，函数开始一定要有条件判断，用来终止递归行为
    return flat(res);
}

const res =flat([1,2,3,[4,5],[6,[7,8]]]);
console.log(res);

2、利用循环：

function flatten(arr) {
    while(arr.some(item => Array.isArray(item))){

        arr = [].concat(...arr);
    }
    return arr;

}
flatten([1,2,[3,4]]);

七、数组去重

let arr=[1,2,3,4,4,5,6,6];
function demo(arr) {
    let test = new Set(arr);
    return [...test]
}
demo(arr);

八、 JavaScript - promise.all()及实现

官方使用方法：

const promise1 = Promise.resolve(3);
const promise2 = 42;
const promise3 = new Promise((resolve, reject) => {
  setTimeout(resolve, 100, 'foo');
});

Promise.all([promise1, promise2, promise3]).then((values) => {
  console.log(values);
});
// expected output: Array [3, 42, "foo"]

手写promise.all()方法：
promise.all方法特性：

输入是数组，输出是也是promise，只不过这个promise的resolve状态会拿到传入promise运行的结果值。
promise.all()返回值是new Promise
需要用一个数组存放每一个promise的结果值
遍历参数数组，判断是否是promise，是的话执行得到结果后压入结果数组；否则直接放入结果数组。
当每个都成功执行后，resolve（result）
当有一个失败，reject

测试有瑕疵，第三个数据出不来，参考修改https://www.jianshu.com/p/c8af0c130ccb
// 是否是promise
function isPromise(obj){
    return !!obj && (typeof obj === 'object' || typeof obj === 'function') && typeof obj.then === 'function';  
}

function newPromiseAll(arr) {
    let result=[];
    return new Promise((resolve, reject)=>{

        arr.forEach(item => {
            if(isPromise(item)){
                item.then(res=>{
                    result.push(res);
                    if(result.length = arr.length){
                        resolve(result);
                    }
                }).catch(err=>reject(err))
            } else {
                result.push(item);
            }
        });
    });

}

var p1 = Promise.resolve(3);
var p2 = 1337;
var p3 = new Promise((resolve, reject) => {
  setTimeout(resolve, 100, 'foo');
}); 
newPromiseAll([p1, p2, p3]).then(values => { 
  console.log('valurs----', values);
});

九、用reduce实现map函数

reduce相关：
在这里插入图片描述

var numbers = [65, 44, 12, 4];
numbers.reduce((total, item)=>{
   return total + item;
},0);
--》125

实现：

Array.prototype.newMap=function(fn, callthis){
    let arr = [];
    this.reduce((first,item,index,initarr)=>{
            return arr.push(fn.call(callthis, item, index, initarr));
        },null);
    return arr;
}
let sun = [2,3];
sun.newMap(item => item*2);

分析：map的入参是第一个是回调函数，第二个this指向，如果不写指向全局
既然是模拟map，那么它的返回值其实就是一个数组
this.reduce的this指向调用者这里是sun数组
reduce的回调函数中参数，第一个是reduce相关的累计值，后面的是数组相关内容， reduce的返回值会替换掉传入的参数

十、快手-原型链

Function.prototype.a = () => alert(1)
Object.prototype.b = () => alert(2);
function A() {}
const a = new A();

a.a();   //1
a.b();   //2

考察内容：原型链
当时给的结果如上，答案错误。正确答案：a.a()会报错，找不到所谓的a方法，a.b() // 2
原因分析：a是通过构造函数创建的实例，typeof a打印出来的是object类型。a.a()查找过程，先看a的实例上是否有a方法，结果没有，那顺着原型链往上找，a的隐式原型是构造函数A的显示原型，这个显示原型中没有构造函数中定义的a方法，那么接着往上找，A显示原型的隐式原型就是Object的构造函数的显示原型。

Object.prototype.b = () => alert(2);
Function.prototype.a = () => alert(1)
function A() {}
var a = new A();
var c = ()=>{}; //如果c是一个函数，调用c.a（）时，会直接只用函数原型上的方法
console.log('11',a.b()); //2
console.log('22',c.a()); //1

十一、实现一个发布订阅模式

参考：https://www.cnblogs.com/lxfbk/p/12401055.html

var event = {

    list: {}, // 任务调度中心

    // 订阅者注册事件及处理函数
    on: function(key, fn) {
        // 订阅者之前没有订阅过该事件类型，给该事件类型建立一个数组来存放回调
        if(!this.list[key]) {
            this.list[key] = []
        }
        this.list[key].push(fn);
    },
    
    //发布者发布事件内容
    emit: function(){
        let key = arguments[0];
        let fns = this.list[key];
        // 发布了一个没人订阅过的事件类型，直接返回
        if(!fns || fns.length === 0){
            return;
        }
        // 发布者去触发发布类型下的所有订阅事件
        fns.forEach((fn)=>{
            fn.apply(this, [...arguments].slice(1));
        });
    },

    //订阅者取消订阅
    off: function(key, fn){
        let fns = this.list[key];
        // 订阅者之前根本没有订阅该类型，那么取消时，也就查不到，直接返回false
        if(!fns){
            return false;
        }
        // 如果只传入了key，没有回调事件，那说明要取消key对应消息的全部订阅
        if(!fn){
            fns = [];
        }
        fns.forEach((item, index)=> {
            if(item === fn) {
                fns.splice(index, 1);
            }
        })
        
    }
}

// 小红订阅如下消息
event.on('red',function(size){
    console.log("尺码是："+size);  
});
event.on('red',function(size){
    console.log("我是小红，我又订阅了一个red：----"+size);  
});
// 小花订阅如下消息
event.on('block',function(size){
    console.log("再次打印尺码是："+size); 
});

event.emit("red",40);
event.off("block",42);

VM60784:50 尺码是：40
VM60784:53 我是小红，我又订阅了一个red：----40

十二、百度

1、去除两端空格
(1) str.trim();
(2) str.replace(/(^\s*)|(\s*$)/g, ‘’);
(3)手写实现

function test(str){

    let first = 0;
    let last = 0;
    let strlength = str.length;
    for(let i=0; i<strlength; i++){
        if(str[i] !== ' ') {
            first = i;
            break;
        };
    }
    for(let j=strlength-1; j>=0;j--){
        if(str[j] !== ' ') {
            last = j;
           break;
        }
    }
    console.log('iiii=---jjjj', first, last);

    return str.slice(first, last+1);
}
test(' jjkfadf  dfj  ');
 iiii=---jjjj 1 12
"jjkfadf  dfj"

2、深拷贝

function deepcopy(obj){
    let res;
    if(typeof obj === 'object'){
        res = obj.constructor === Array ? [] : {};
        for(let key in obj){
            if(typeof obj[key] === 'object'){
                res[key] = deepcopy(obj[key]);
            }
            else {
                res[key] = obj[key];
            }
        }
        
    }
    else{
        res = obj;
    }
    return res;
}
var sun = {
    a: 1,
    b: {
        c: 2
    }
};

let haha = deepcopy(sun);
haha.a=99;
console.log(sun);
console.log(haha);

在这里插入图片描述

3、一分钟内的相同请求只取第一次，再请求取缓存
4、回文字符串判断

reverse（）翻转

function test(str) {
    var newstr = str.split('').reverse().join('');
    return newstr === str;
    
}
test('aba');

相应位置元素对比判断

function fn(str){
    var len = str.length;
    var flag = true;
    for(var i = 0;i < parseInt(len/2);i++){    //不去判断中间那个字符
        if(str[i] != str[len-1-i]){
            flag = false;
            break;
        }
    }
    return flag;
}

console.log(fn("121")); // true

技术共进，成长同行——讯飞AI开发者社区

技术共进，成长同行——讯飞AI开发者社区

更多推荐

机器学习与人工智能

python# 创建基类# 定义一对多关系# 定义多对一关系# 定义多对多关系（通过关联表）# 关联表（用于多对多关系）SQLAlchemy ORM提供了强大而灵活的数据库操作方式，通过本文的介绍，您应该能够：安装和配置SQLAlchemy定义数据模型和关系执行基本的CRUD操作构建复杂查询管理数据库事务遵循最佳实践SQLAlchemy还有更多高级特性，如混合属性、事件监听、自定义查询等，值得进一

讯飞AI开发者社区

cover

【数据结构】图的遍历

讯飞AI开发者社区

cover

【论文】AI技术对幼儿园课程建构的影响研究（一）

讯飞AI开发者社区

所有评论(0)

查看更多评论

祥哥的说

已为社区贡献2条内容