最全的手写JS面试题

黑夜尽头 | 2590 | 2022-03-14

这是我参与更文挑战的第 1 天,活动详情查看:更文挑战

前言

本文整理了前端面试高频出现的手写源码相关的题目 其中有小编面试亲自遇到的也有其他同学帮忙补充的 整体采用 es6 语法并且以简单易懂版进行实现 如果对答案有不一样见解的同学欢迎评论区补充讨论 虽然鲨鱼哥也很不喜欢内卷 但是在如今人人皆卷的大环境下 大家只有比别人更卷才能收获更好的未来 最后欢迎大家点击 链接 加入到鲨鱼哥的前端群 内推 讨论技术 摸鱼 求助 皆可~~

整理不易 如果觉得本文有帮助 记得点赞三连哦 十分感谢!


1 compose

题目描述:实现一个 compose 函数

// 用法如下: function fn1(x) { return x + 1; } function fn2(x) { return x + 2; } function fn3(x) { return x + 3; } function fn4(x) { return x + 4; } const a = compose(fn1, fn2, fn3, fn4); console.log(a(1)); // 1+4+3+2+1=11

实现代码如下:

function compose(...fn) { if (!fn.length) return (v) => v; if (fn.length === 1) return fn[0]; return fn.reduce( (pre, cur) => (...args) => pre(cur(...args)) ); }

2 settimeout 模拟实现 setinterval(带清除定时器的版本)

题目描述:setinterval 用来实现循环定时调用 可能会存在一定的问题 能用 settimeout 解决吗

实现代码如下:

function mySettimeout(fn, t) { let timer = null; function interval() { fn(); timer = setTimeout(interval, t); } interval(); return { cancel:()=>{ clearTimeout(timer) } } } // let a=mySettimeout(()=>{ // console.log(111); // },1000) // let b=mySettimeout(() => { // console.log(222) // }, 1000)

扩展:我们能反过来使用 setinterval 模拟实现 settimeout 吗?

const mySetTimeout = (fn, time) => { const timer = setInterval(() => { clearInterval(timer); fn(); }, time); }; // mySetTimeout(()=>{ // console.log(1); // },1000)

扩展思考:为什么要用 settimeout 模拟实现 setinterval?setinterval 的缺陷是什么?

答案请自行百度哈 这个其实面试官问的也挺多的 小编这里就不展开了

3 发布订阅模式

题目描述:实现一个发布订阅模式拥有 on emit once off 方法

实现代码如下:

class EventEmitter { constructor() { this.events = {}; } // 实现订阅 on(type, callBack) { if (!this.events[type]) { this.events[type] = [callBack]; } else { this.events[type].push(callBack); } } // 删除订阅 off(type, callBack) { if (!this.events[type]) return; this.events[type] = this.events[type].filter((item) => { return item !== callBack; }); } // 只执行一次订阅事件 once(type, callBack) { function fn() { callBack(); this.off(type, fn); } this.on(type, fn); } // 触发事件 emit(type, ...rest) { this.events[type] && this.events[type].forEach((fn) => fn.apply(this, rest)); } } // 使用如下 // const event = new EventEmitter(); // const handle = (...rest) => { // console.log(rest); // }; // event.on("click", handle); // event.emit("click", 1, 2, 3, 4); // event.off("click", handle); // event.emit("click", 1, 2); // event.once("dbClick", () => { // console.log(123456); // }); // event.emit("dbClick"); // event.emit("dbClick");

4 数组去重

实现代码如下:

function uniqueArr(arr) { return [...new Set(arr)]; }

5 数组扁平化

题目描述:实现一个方法使多维数组变成一维数组

最常见的递归版本如下:

function flatter(arr) { if (!arr.length) return; return arr.reduce( (pre, cur) => Array.isArray(cur) ? [...pre, ...flatter(cur)] : [...pre, cur], [] ); } // console.log(flatter([1, 2, [1, [2, 3, [4, 5, [6]]]]]));

扩展思考:能用迭代的思路去实现吗?

实现代码如下:

function flatter(arr) { if (!arr.length) return; while (arr.some((item) => Array.isArray(item))) { arr = [].concat(...arr); } return arr; } // console.log(flatter([1, 2, [1, [2, 3, [4, 5, [6]]]]]));

6 寄生组合继承

题目描述:实现一个你认为不错的 js 继承方式

实现代码如下:

function Parent(name) { this.name = name; this.say = () => { console.log(111); }; } Parent.prototype.play = () => { console.log(222); }; function Children(name) { Parent.call(this); this.name = name; } Children.prototype = Object.create(Parent.prototype); Children.prototype.constructor = Children; // let child = new Children("111"); // // console.log(child.name); // // child.say(); // // child.play();

7 实现有并行限制的 Promise 调度器

题目描述:JS 实现一个带并发限制的异步调度器 Scheduler,保证同时运行的任务最多有两个

addTask(1000,"1"); addTask(500,"2"); addTask(300,"3"); addTask(400,"4"); 的输出顺序是:2 3 1 4 整个的完整执行流程: 一开始12两个任务开始执行 500ms时,2任务执行完毕,输出2,任务3开始执行 800ms时,3任务执行完毕,输出3,任务4开始执行 1000ms时,1任务执行完毕,输出1,此时只剩下4任务在执行 1200ms时,4任务执行完毕,输出4

实现代码如下:

class Scheduler { constructor(limit) { this.queue = []; this.maxCount = limit; this.runCounts = 0; } add(time, order) { const promiseCreator = () => { return new Promise((resolve, reject) => { setTimeout(() => { console.log(order); resolve(); }, time); }); }; this.queue.push(promiseCreator); } taskStart() { for (let i = 0; i < this.maxCount; i++) { this.request(); } } request() { if (!this.queue || !this.queue.length || this.runCounts >= this.maxCount) { return; } this.runCounts++; this.queue .shift()() .then(() => { this.runCounts--; this.request(); }); } } const scheduler = new Scheduler(2); const addTask = (time, order) => { scheduler.add(time, order); }; addTask(1000, "1"); addTask(500, "2"); addTask(300, "3"); addTask(400, "4"); scheduler.taskStart();

8 new 操作符

题目描述:手写 new 操作符实现

实现代码如下:

function myNew(fn, ...args) { let obj = Object.create(fn.prototype); let res = fn.call(obj, ...args); if (res && (typeof res === "object" || typeof res === "function")) { return res; } return obj; } 用法如下: // // function Person(name, age) { // // this.name = name; // // this.age = age; // // } // // Person.prototype.say = function() { // // console.log(this.age); // // }; // // let p1 = myNew(Person, "lihua", 18); // // console.log(p1.name); // // console.log(p1); // // p1.say();

9 call apply bind

题目描述:手写 call apply bind 实现

实现代码如下:

Function.prototype.myCall = function (context, ...args) { if (!context || context === null) { context = window; } // 创造唯一的key值 作为我们构造的context内部方法名 let fn = Symbol(); context[fn] = this; //this指向调用call的函数 // 执行函数并返回结果 相当于把自身作为传入的context的方法进行调用了 return context[fn](...args); }; // apply原理一致 只是第二个参数是传入的数组 Function.prototype.myApply = function (context, args) { if (!context || context === null) { context = window; } // 创造唯一的key值 作为我们构造的context内部方法名 let fn = Symbol(); context[fn] = this; // 执行函数并返回结果 return context[fn](...args); }; //bind实现要复杂一点 因为他考虑的情况比较多 还要涉及到参数合并(类似函数柯里化) Function.prototype.myBind = function (context, ...args) { if (!context || context === null) { context = window; } // 创造唯一的key值 作为我们构造的context内部方法名 let fn = Symbol(); context[fn] = this; let _this = this; // bind情况要复杂一点 const result = function (...innerArgs) { // 第一种情况 :若是将 bind 绑定之后的函数当作构造函数,通过 new 操作符使用,则不绑定传入的 this,而是将 this 指向实例化出来的对象 // 此时由于new操作符作用 this指向result实例对象 而result又继承自传入的_this 根据原型链知识可得出以下结论 // this.__proto__ === result.prototype //this instanceof result =>true // this.__proto__.__proto__ === result.prototype.__proto__ === _this.prototype; //this instanceof _this =>true if (this instanceof _this === true) { // 此时this指向指向result的实例 这时候不需要改变this指向 this[fn] = _this; this[fn](...[...args, ...innerArgs]); //这里使用es6的方法让bind支持参数合并 } else { // 如果只是作为普通函数调用 那就很简单了 直接改变this指向为传入的context context[fn](...[...args, ...innerArgs]); } }; // 如果绑定的是构造函数 那么需要继承构造函数原型属性和方法 // 实现继承的方式: 使用Object.create result.prototype = Object.create(this.prototype); return result; }; //用法如下 // function Person(name, age) { // console.log(name); //'我是参数传进来的name' // console.log(age); //'我是参数传进来的age' // console.log(this); //构造函数this指向实例对象 // } // // 构造函数原型的方法 // Person.prototype.say = function() { // console.log(123); // } // let obj = { // objName: '我是obj传进来的name', // objAge: '我是obj传进来的age' // } // // 普通函数 // function normalFun(name, age) { // console.log(name); //'我是参数传进来的name' // console.log(age); //'我是参数传进来的age' // console.log(this); //普通函数this指向绑定bind的第一个参数 也就是例子中的obj // console.log(this.objName); //'我是obj传进来的name' // console.log(this.objAge); //'我是obj传进来的age' // } // 先测试作为构造函数调用 // let bindFun = Person.myBind(obj, '我是参数传进来的name') // let a = new bindFun('我是参数传进来的age') // a.say() //123 // 再测试作为普通函数调用 // let bindFun = normalFun.myBind(obj, '我是参数传进来的name') // bindFun('我是参数传进来的age')

10 深拷贝(考虑到复制 Symbol 类型)

题目描述:手写 new 操作符实现

实现代码如下:

function isObject(val) { return typeof val === "object" && val !== null; } function deepClone(obj, hash = new WeakMap()) { if (!isObject(obj)) return obj; if (hash.has(obj)) { return hash.get(obj); } let target = Array.isArray(obj) ? [] : {}; hash.set(obj, target); Reflect.ownKeys(obj).forEach((item) => { if (isObject(obj[item])) { target[item] = deepClone(obj[item], hash); } else { target[item] = obj[item]; } }); return target; } // var obj1 = { // a:1, // b:{a:2} // }; // var obj2 = deepClone(obj1); // console.log(obj1);

11 instanceof

题目描述:手写 instanceof 操作符实现

实现代码如下:

function myInstanceof(left, right) { while (true) { if (left === null) { return false; } if (left.__proto__ === right.prototype) { return true; } left = left.__proto__; } }

12 柯里化

题目描述:柯里化(Currying),又称部分求值(Partial Evaluation),是把接受多个参数的函数变换成接受一个单一参数(最初函数的第一个参数)的函数,并且返回接受余下的参数而且返回结果的新函数的技术。核心思想是把多参数传入的函数拆成单参数(或部分)函数,内部再返回调用下一个单参数(或部分)函数,依次处理剩余的参数。

实现代码如下:

function currying(fn, ...args) { const length = fn.length; let allArgs = [...args]; const res = (...newArgs) => { allArgs = [...allArgs, ...newArgs]; if (allArgs.length === length) { return fn(...allArgs); } else { return res; } }; return res; } // 用法如下: // const add = (a, b, c) => a + b + c; // const a = currying(add, 1); // console.log(a(2,3))

13 冒泡排序--时间复杂度 n^2

题目描述:实现一个冒泡排序

实现代码如下:

function bubbleSort(arr) { // 缓存数组长度 const len = arr.length; // 外层循环用于控制从头到尾的比较+交换到底有多少轮 for (let i = 0; i < len; i++) { // 内层循环用于完成每一轮遍历过程中的重复比较+交换 for (let j = 0; j < len - 1; j++) { // 若相邻元素前面的数比后面的大 if (arr[j] > arr[j + 1]) { // 交换两者 [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; } } } // 返回数组 return arr; } // console.log(bubbleSort([3, 6, 2, 4, 1]));

14 选择排序--时间复杂度 n^2

题目描述:实现一个选择排序

实现代码如下:

function selectSort(arr) { // 缓存数组长度 const len = arr.length; // 定义 minIndex,缓存当前区间最小值的索引,注意是索引 let minIndex; // i 是当前排序区间的起点 for (let i = 0; i < len - 1; i++) { // 初始化 minIndex 为当前区间第一个元素 minIndex = i; // i、j分别定义当前区间的上下界,i是左边界,j是右边界 for (let j = i; j < len; j++) { // 若 j 处的数据项比当前最小值还要小,则更新最小值索引为 j if (arr[j] < arr[minIndex]) { minIndex = j; } } // 如果 minIndex 对应元素不是目前的头部元素,则交换两者 if (minIndex !== i) { [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; } } return arr; } // console.log(quickSort([3, 6, 2, 4, 1]));

15 插入排序--时间复杂度 n^2

题目描述:实现一个插入排序

实现代码如下:

function insertSort(arr) { for (let i = 1; i < arr.length; i++) { let j = i; let target = arr[j]; while (j > 0 && arr[j - 1] > target) { arr[j] = arr[j - 1]; j--; } arr[j] = target; } return arr; } // console.log(insertSort([3, 6, 2, 4, 1]));

16 快排--时间复杂度 nlogn~ n^2 之间

题目描述:实现一个快排

实现代码如下:

function quickSort(arr) { if (arr.length < 2) { return arr; } const cur = arr[arr.length - 1]; const left = arr.filter((v, i) => v <= cur && i !== arr.length - 1); const right = arr.filter((v) => v > cur); return [...quickSort(left), cur, ...quickSort(right)]; } // console.log(quickSort([3, 6, 2, 4, 1]));

17 归并排序--时间复杂度 nlog(n)

题目描述:实现一个时间复杂度为 nlog(n)的排序算法

实现代码如下:

function merge(left, right) { let res = []; let i = 0; let j = 0; while (i < left.length && j < right.length) { if (left[i] < right[j]) { res.push(left[i]); i++; } else { res.push(right[j]); j++; } } if (i < left.length) { res.push(...left.slice(i)); } else { res.push(...right.slice(j)); } return res; } function mergeSort(arr) { if (arr.length < 2) { return arr; } const mid = Math.floor(arr.length / 2); const left = mergeSort(arr.slice(0, mid)); const right = mergeSort(arr.slice(mid)); return merge(left, right); } // console.log(mergeSort([3, 6, 2, 4, 1]));

18 二分查找--时间复杂度 log2(n)

题目描述:如何确定一个数在一个有序数组中的位置

实现代码如下:

function search(arr, target, start, end) { let targetIndex = -1; let mid = Math.floor((start + end) / 2); if (arr[mid] === target) { targetIndex = mid; return targetIndex; } if (start >= end) { return targetIndex; } if (arr[mid] < target) { return search(arr, target, mid + 1, end); } else { return search(arr, target, start, mid - 1); } } // const dataArr = [1, 2, 3, 4, 5, 6, 7, 8, 9]; // const position = search(dataArr, 6, 0, dataArr.length - 1); // if (position !== -1) { // console.log(`目标元素在数组中的位置:${position}`); // } else { // console.log("目标元素不在数组中"); // }

19 实现 LazyMan

题目描述:

实现一个LazyMan,可以按照以下方式调用: LazyMan(“Hank”)输出: Hi! This is Hank! LazyMan(“Hank”).sleep(10).eat(“dinner”)输出 Hi! This is Hank! //等待10秒.. Wake up after 10 Eat dinner~ LazyMan(“Hank”).eat(“dinner”).eat(“supper”)输出 Hi This is Hank! Eat dinner~ Eat supper~ LazyMan(“Hank”).eat(“supper”).sleepFirst(5)输出 //等待5秒 Wake up after 5 Hi This is Hank! Eat supper

实现代码如下:

class _LazyMan { constructor(name) { this.tasks = []; const task = () => { console.log(`Hi! This is ${name}`); this.next(); }; this.tasks.push(task); setTimeout(() => { // 把 this.next() 放到调用栈清空之后执行 this.next(); }, 0); } next() { const task = this.tasks.shift(); // 取第一个任务执行 task && task(); } sleep(time) { this._sleepWrapper(time, false); return this; // 链式调用 } sleepFirst(time) { this._sleepWrapper(time, true); return this; } _sleepWrapper(time, first) { const task = () => { setTimeout(() => { console.log(`Wake up after ${time}`); this.next(); }, time * 1000); }; if (first) { this.tasks.unshift(task); // 放到任务队列顶部 } else { this.tasks.push(task); // 放到任务队列尾部 } } eat(name) { const task = () => { console.log(`Eat ${name}`); this.next(); }; this.tasks.push(task); return this; } } function LazyMan(name) { return new _LazyMan(name); }

20 防抖节流

题目描述:手写防抖节流

实现代码如下:

// 防抖 function debounce(fn, delay = 300) { //默认300毫秒 let timer; return function () { const args = arguments; if (timer) { clearTimeout(timer); } timer = setTimeout(() => { fn.apply(this, args); // 改变this指向为调用debounce所指的对象 }, delay); }; } window.addEventListener( "scroll", debounce(() => { console.log(111); }, 1000) ); // 节流 // 设置一个标志 function throttle(fn, delay) { let flag = true; return () => { if (!flag) return; flag = false; timer = setTimeout(() => { fn(); flag = true; }, delay); }; } window.addEventListener( "scroll", throttle(() => { console.log(111); }, 1000) );

21 写版本号排序的方法

题目描述:有一组版本号如下['0.1.1', '2.3.3', '0.302.1', '4.2', '4.3.5', '4.3.4.5']。现在需要对其进行排序,排序的结果为 ['4.3.5','4.3.4.5','2.3.3','0.302.1','0.1.1']

实现代码如下:

arr.sort((a, b) => { let i = 0; const arr1 = a.split("."); const arr2 = b.split("."); while (true) { const s1 = arr1[i]; const s2 = arr2[i]; i++; if (s1 === undefined || s2 === undefined) { return arr2.length - arr1.length; } if (s1 === s2) continue; return s2 - s1; } }); console.log(arr);

22 LRU 算法

题目描述: LRU题目.png

实现代码如下:

// 一个Map对象在迭代时会根据对象中元素的插入顺序来进行 // 新添加的元素会被插入到map的末尾,整个栈倒序查看 class LRUCache { constructor(capacity) { this.secretKey = new Map(); this.capacity = capacity; } get(key) { if (this.secretKey.has(key)) { let tempValue = this.secretKey.get(key); this.secretKey.delete(key); this.secretKey.set(key, tempValue); return tempValue; } else return -1; } put(key, value) { // key存在,仅修改值 if (this.secretKey.has(key)) { this.secretKey.delete(key); this.secretKey.set(key, value); } // key不存在,cache未满 else if (this.secretKey.size < this.capacity) { this.secretKey.set(key, value); } // 添加新key,删除旧key else { this.secretKey.set(key, value); // 删除map的第一个元素,即为最长未使用的 this.secretKey.delete(this.secretKey.keys().next().value); } } } // let cache = new LRUCache(2); // cache.put(1, 1); // cache.put(2, 2); // console.log("cache.get(1)", cache.get(1))// 返回 1 // cache.put(3, 3);// 该操作会使得密钥 2 作废 // console.log("cache.get(2)", cache.get(2))// 返回 -1 (未找到) // cache.put(4, 4);// 该操作会使得密钥 1 作废 // console.log("cache.get(1)", cache.get(1))// 返回 -1 (未找到) // console.log("cache.get(3)", cache.get(3))// 返回 3 // console.log("cache.get(4)", cache.get(4))// 返回 4

23 Promise 以及相关方法的实现

题目描述:手写 Promise 以及 Promise.all Promise.race 的实现

实现代码如下:

class Mypromise { constructor(fn) { // 表示状态 this.state = "pending"; // 表示then注册的成功函数 this.successFun = []; // 表示then注册的失败函数 this.failFun = []; let resolve = (val) => { // 保持状态改变不可变(resolve和reject只准触发一种) if (this.state !== "pending") return; // 成功触发时机 改变状态 同时执行在then注册的回调事件 this.state = "success"; // 为了保证then事件先注册(主要是考虑在promise里面写同步代码) promise规范 这里为模拟异步 setTimeout(() => { // 执行当前事件里面所有的注册函数 this.successFun.forEach((item) => item.call(this, val)); }); }; let reject = (err) => { if (this.state !== "pending") return; // 失败触发时机 改变状态 同时执行在then注册的回调事件 this.state = "fail"; // 为了保证then事件先注册(主要是考虑在promise里面写同步代码) promise规范 这里模拟异步 setTimeout(() => { this.failFun.forEach((item) => item.call(this, err)); }); }; // 调用函数 try { fn(resolve, reject); } catch (error) { reject(error); } } // 实例方法 then then(resolveCallback, rejectCallback) { // 判断回调是否是函数 resolveCallback = typeof resolveCallback !== "function" ? (v) => v : resolveCallback; rejectCallback = typeof rejectCallback !== "function" ? (err) => { throw err; } : rejectCallback; // 为了保持链式调用 继续返回promise return new Mypromise((resolve, reject) => { // 将回调注册到successFun事件集合里面去 this.successFun.push((val) => { try { // 执行回调函数 let x = resolveCallback(val); //(最难的一点) // 如果回调函数结果是普通值 那么就resolve出去给下一个then链式调用 如果是一个promise对象(代表又是一个异步) 那么调用x的then方法 将resolve和reject传进去 等到x内部的异步 执行完毕的时候(状态完成)就会自动执行传入的resolve 这样就控制了链式调用的顺序 x instanceof Mypromise ? x.then(resolve, reject) : resolve(x); } catch (error) { reject(error); } }); this.failFun.push((val) => { try { // 执行回调函数 let x = rejectCallback(val); x instanceof Mypromise ? x.then(resolve, reject) : reject(x); } catch (error) { reject(error); } }); }); } //静态方法 static all(promiseArr) { let result = []; //声明一个计数器 每一个promise返回就加一 let count = 0; return new Mypromise((resolve, reject) => { for (let i = 0; i < promiseArr.length; i++) { //这里用 Promise.resolve包装一下 防止不是Promise类型传进来 Promise.resolve(promiseArr[i]).then( (res) => { //这里不能直接push数组 因为要控制顺序一一对应(感谢评论区指正) result[i] = res; count++; //只有全部的promise执行成功之后才resolve出去 if (count === promiseArr.length) { resolve(result); } }, (err) => { reject(err); } ); } }); } //静态方法 static race(promiseArr) { return new Mypromise((resolve, reject) => { for (let i = 0; i < promiseArr.length; i++) { Promise.resolve(promiseArr[i]).then( (res) => { //promise数组只要有任何一个promise 状态变更 就可以返回 resolve(res); }, (err) => { reject(err); } ); } }); } } // 使用 // let promise1 = new Mypromise((resolve, reject) => { // setTimeout(() => { // resolve(123); // }, 2000); // }); // let promise2 = new Mypromise((resolve, reject) => { // setTimeout(() => { // resolve(1234); // }, 1000); // }); // Mypromise.all([promise1,promise2]).then(res=>{ // console.log(res); // }) // Mypromise.race([promise1, promise2]).then(res => { // console.log(res); // }); // promise1 // .then( // res => { // console.log(res); //过两秒输出123 // return new Mypromise((resolve, reject) => { // setTimeout(() => { // resolve("success"); // }, 1000); // }); // }, // err => { // console.log(err); // } // ) // .then( // res => { // console.log(res); //再过一秒输出success // }, // err => { // console.log(err); // } // );

扩展思考:如何取消 promise

Promise.race()方法可以用来竞争 Promise 可以借助这个特性 自己包装一个 空的 Promise 与要发起的 Promise 来实现

function wrap(pro) { let obj = {}; // 构造一个新的promise用来竞争 let p1 = new Promise((resolve, reject) => { obj.resolve = resolve; obj.reject = reject; }); obj.promise = Promise.race([p1, pro]); return obj; } let testPro = new Promise((resolve, reject) => { setTimeout(() => { resolve(123); }, 1000); }); let wrapPro = wrap(testPro); wrapPro.promise.then((res) => { console.log(res); }); wrapPro.resolve("被拦截了");

24 实现一个 add 方法

题目描述:实现一个 add 方法 使计算结果能够满足如下预期: add(1)(2)(3)()=6 add(1,2,3)(4)()=10

其实就是考函数柯里化

实现代码如下:

function add(...args) { let allArgs = [...args]; function fn(...newArgs) { allArgs = [...allArgs, ...newArgs]; return fn; } fn.toString = function () { if (!allArgs.length) { return; } return allArgs.reduce((sum, cur) => sum + cur); }; return fn; }

25 动态规划求解硬币找零问题

题目描述:给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1

示例1: 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例2: 输入: coins = [2], amount = 3 输出: -1

实现代码如下:

const coinChange = function (coins, amount) { // 用于保存每个目标总额对应的最小硬币个数 const f = []; // 提前定义已知情况 f[0] = 0; // 遍历 [1, amount] 这个区间的硬币总额 for (let i = 1; i <= amount; i++) { // 求的是最小值,因此我们预设为无穷大,确保它一定会被更小的数更新 f[i] = Infinity; // 循环遍历每个可用硬币的面额 for (let j = 0; j < coins.length; j++) { // 若硬币面额小于目标总额,则问题成立 if (i - coins[j] >= 0) { // 状态转移方程 f[i] = Math.min(f[i], f[i - coins[j]] + 1); } } } // 若目标总额对应的解为无穷大,则意味着没有一个符合条件的硬币总数来更新它,本题无解,返回-1 if (f[amount] === Infinity) { return -1; } // 若有解,直接返回解的内容 return f[amount]; };

26 请实现 DOM2JSON 一个函数,可以把一个 DOM 节点输出 JSON 的格式

题目描述:

<div> <span> <a></a> </span> <span> <a></a> <a></a> </span> </div> 把上诉dom结构转成下面的JSON格式 { tag: 'DIV', children: [ { tag: 'SPAN', children: [ { tag: 'A', children: [] } ] }, { tag: 'SPAN', children: [ { tag: 'A', children: [] }, { tag: 'A', children: [] } ] } ] }

实现代码如下:

function dom2Json(domtree) { let obj = {}; obj.name = domtree.tagName; obj.children = []; domtree.childNodes.forEach((child) => obj.children.push(dom2Json(child))); return obj; }

扩展思考:如果给定的不是一个 Dom 树结构 而是一段 html 字符串 该如何解析?

那么这个问题就类似 Vue 的模板编译原理 我们可以利用正则 匹配 html 字符串 遇到开始标签 结束标签和文本 解析完毕之后生成对应的 ast 并建立相应的父子关联 不断的 advance 截取剩余的字符串 直到 html 全部解析完毕 感兴趣的可以看这里

27 类数组转化为数组的方法

题目描述:类数组拥有 length 属性 可以使用下标来访问元素 但是不能使用数组的方法 如何把类数组转化为数组?

实现代码如下:

const arrayLike=document.querySelectorAll('div') // 1.扩展运算符 [...arrayLike] // 2.Array.from Array.from(arrayLike) // 3.Array.prototype.slice Array.prototype.slice.call(arrayLike) // 4.Array.apply Array.apply(null, arrayLike) // 5.Array.prototype.concat Array.prototype.concat.apply([], arrayLike)

28 Object.is 实现

题目描述:

Object.is不会转换被比较的两个值的类型,这点和===更为相似,他们之间也存在一些区别。 1. NaN在===中是不相等的,而在Object.is中是相等的 2. +0和-0在===中是相等的,而在Object.is中是不相等的

实现代码如下:

Object.is = function (x, y) { if (x === y) { // 当前情况下,只有一种情况是特殊的,即 +0 -0 // 如果 x !== 0,则返回true // 如果 x === 0,则需要判断+0和-0,则可以直接使用 1/+0 === Infinity 和 1/-0 === -Infinity来进行判断 return x !== 0 || 1 / x === 1 / y; } // x !== y 的情况下,只需要判断是否为NaN,如果x!==x,则说明x是NaN,同理y也一样 // x和y同时为NaN时,返回true return x !== x && y !== y; };

29 AJAX

题目描述:利用 XMLHttpRequest 手写 AJAX 实现

实现代码如下:

const getJSON = function (url) { return new Promise((resolve, reject) => { const xhr = new XMLHttpRequest(); xhr.open("GET", url, false); xhr.setRequestHeader("Content-Type", "application/json"); xhr.onreadystatechange = function () { if (xhr.readyState !== 4) return; if (xhr.status === 200 || xhr.status === 304) { resolve(xhr.responseText); } else { reject(new Error(xhr.responseText)); } }; xhr.send(); }); };

30 分片思想解决大数据量渲染问题

题目描述:渲染百万条结构简单的大数据时 怎么使用分片思想优化渲染

实现代码如下:

let ul = document.getElementById("container"); // 插入十万条数据 let total = 100000; // 一次插入 20 条 let once = 20; //总页数 let page = total / once; //每条记录的索引 let index = 0; //循环加载数据 function loop(curTotal, curIndex) { if (curTotal <= 0) { return false; } //每页多少条 let pageCount = Math.min(curTotal, once); window.requestAnimationFrame(function () { for (let i = 0; i < pageCount; i++) { let li = document.createElement("li"); li.innerText = curIndex + i + " : " + ~~(Math.random() * total); ul.appendChild(li); } loop(curTotal - pageCount, curIndex + pageCount); }); } loop(total, index);

扩展思考:对于大数据量的简单 dom 结构渲染可以用分片思想解决 如果是复杂的 dom 结构渲染如何处理?

这时候就需要使用虚拟列表了 大家自行百度哈 虚拟列表和虚拟表格在日常项目使用还是很频繁的

31 将虚拟 Dom 转化为真实 Dom

题目描述:JSON 格式的虚拟 Dom 怎么转换成真实 Dom

{ tag: 'DIV', attrs:{ id:'app' }, children: [ { tag: 'SPAN', children: [ { tag: 'A', children: [] } ] }, { tag: 'SPAN', children: [ { tag: 'A', children: [] }, { tag: 'A', children: [] } ] } ] } 把上诉虚拟Dom转化成下方真实Dom <div id="app"> <span> <a></a> </span> <span> <a></a> <a></a> </span> </div>

实现代码如下:

// 真正的渲染函数 function _render(vnode) { // 如果是数字类型转化为字符串 if (typeof vnode === "number") { vnode = String(vnode); } // 字符串类型直接就是文本节点 if (typeof vnode === "string") { return document.createTextNode(vnode); } // 普通DOM const dom = document.createElement(vnode.tag); if (vnode.attrs) { // 遍历属性 Object.keys(vnode.attrs).forEach((key) => { const value = vnode.attrs[key]; dom.setAttribute(key, value); }); } // 子数组进行递归操作 vnode.children.forEach((child) => dom.appendChild(_render(child))); return dom; }

32 实现模板字符串解析功能

题目描述:

let template = '我是{{name}},年龄{{age}},性别{{sex}}'; let data = { name: '姓名', age: 18 } render(template, data); // 我是姓名,年龄18,性别undefined

实现代码如下:

function render(template, data) { let computed = template.replace(/\{\{(\w+)\}\}/g, function (match, key) { return data[key]; }); return computed; }

33 实现一个对象的 flatten 方法

题目描述:

const obj = { a: { b: 1, c: 2, d: {e: 5} }, b: [1, 3, {a: 2, b: 3}], c: 3 } flatten(obj) 结果返回如下 // { // 'a.b': 1, // 'a.c': 2, // 'a.d.e': 5, // 'b[0]': 1, // 'b[1]': 3, // 'b[2].a': 2, // 'b[2].b': 3 // c: 3 // }

实现代码如下:

function isObject(val) { return typeof val === "object" && val !== null; } function flatten(obj) { if (!isObject(obj)) { return; } let res = {}; const dfs = (cur, prefix) => { if (isObject(cur)) { if (Array.isArray(cur)) { cur.forEach((item, index) => { dfs(item, `${prefix}[${index}]`); }); } else { for (let k in cur) { dfs(cur[k], `${prefix}${prefix ? "." : ""}${k}`); } } } else { res[prefix] = cur; } }; dfs(obj, ""); return res; } flatten();

34 列表转成树形结构

题目描述:

[ { id: 1, text: '节点1', parentId: 0 //这里用0表示为顶级节点 }, { id: 2, text: '节点1_1', parentId: 1 //通过这个字段来确定子父级 } ... ] 转成 [ { id: 1, text: '节点1', parentId: 0, children: [ { id:2, text: '节点1_1', parentId:1 } ] } ]

实现代码如下:

function listToTree(data) { let temp = {}; let treeData = []; for (let i = 0; i < data.length; i++) { temp[data[i].id] = data[i]; } for (let i in temp) { if (+temp[i].parentId != 0) { if (!temp[temp[i].parentId].children) { temp[temp[i].parentId].children = []; } temp[temp[i].parentId].children.push(temp[i]); } else { treeData.push(temp[i]); } } return treeData; }

35 树形结构转成列表

题目描述:

[ { id: 1, text: '节点1', parentId: 0, children: [ { id:2, text: '节点1_1', parentId:1 } ] } ] 转成 [ { id: 1, text: '节点1', parentId: 0 //这里用0表示为顶级节点 }, { id: 2, text: '节点1_1', parentId: 1 //通过这个字段来确定子父级 } ... ]

实现代码如下:

function treeToList(data) { let res = []; const dfs = (tree) => { tree.forEach((item) => { if (item.children) { dfs(item.children); delete item.children; } res.push(item); }); }; dfs(data); return res; }

36 大数相加

题目描述:实现一个add方法完成两个大数相加

let a = "9007199254740991"; let b = "1234567899999999999"; function add(a ,b){ //... }

实现代码如下:

function add(a ,b){ //取两个数字的最大长度 let maxLength = Math.max(a.length, b.length); //用0去补齐长度 a = a.padStart(maxLength , 0);//"0009007199254740991" b = b.padStart(maxLength , 0);//"1234567899999999999" //定义加法过程中需要用到的变量 let t = 0; let f = 0; //"进位" let sum = ""; for(let i=maxLength-1 ; i>=0 ; i--){ t = parseInt(a[i]) + parseInt(b[i]) + f; f = Math.floor(t/10); sum = t%10 + sum; } if(f!==0){ sum = '' + f + sum; } return sum; }

鲨鱼哥的前端摸鱼技术群

欢迎大家技术交流 内推 摸鱼 求助皆可 - 链接

关联知识库

Javascript 系列
文章标签: 代码实现前端相关
推荐指数:

转载声明:

原作者: 鲨鱼哥

转载自: 《最全的手写JS面试题》,如有侵权,请联系本站删除。

3人已点赞

最全的手写JS面试题

没有更多了

关于作者 📝

黑夜尽头

大风起兮云飞扬 安得猛士兮走四方 wx: kr_39hd

等级 LV5

粉丝 42

获赞 281

经验 1694

关联知识库

Javascript 系列