面试中遇到的高频问题整理

1. JavaScript 相关

1.1 基础概念类

JavaScript 中的数据类型

  • 八大基本数据类型(含 ES6):Undefined Null Number String Boolean Object Symbol BitInt
  • 原始类型:String Number Boolean Null Undefined Symbol
  • 引用类型:Object Array Function RegExp Date

原型与原型链

重点:

  • 对原型与原型链的理解
  • 基于原型链的查找逻辑
    • 显式原型与隐式原型的区别
  • 为什么要设计原型与原型链机制

任务队列

参考文章

重点:

  • 为什么要设计异步
  • 任务队列的执行过程
  • 给一段代码,要求说出输出结果 练习题

new 一个对象发生了什么

  1. 创建一个新对象
  2. 新对象的隐式原型 __proto__ 指向构造函数的显示原型 prototype
  3. 将构造函数中的 this 指向新对象
  4. 执行构造函数
  5. 返回新对象(如果构造函数返回一个对象,返回该对象)

关联:[[面试中遇到的高频问题整理#实现 new 方法]]

宏任务与微任务

简单示例:

1
2
3
4
setTimeout(() => alert("timeout"));
Promise.resolve()
.then(() => alert("promise"));
alert("code");

执行顺序:

  1. code 首先显示,因为它是常规的同步调用。
  2. promise 第二个出现,因为 then 会通过微任务队列,并在当前代码之后执行。
  3. timeout 最后显示,因为它是一个宏任务。

要点:

  • 微任务会在执行任何其他事件处理,或渲染,或执行任何其他宏任务之前完成
  • 每个宏任务执行时都会去先检查微任务队列里是否有微任务,如果有则先清空微任务队列

参考示例

注意,new Promise 的处理函数中执行的代码也是同步执行的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
console.log("script start")

new Promise((resolve) => {
console.log("sync task")
resolve();
}).then(() => {
console.log("micro start")
})

console.log("script end")

/**
输出:
script start
sync task
script end
micro start
*/

如果题目中使用了 async 和 await,可以改写为 Promise 链,这样就不迷糊了,如:

1
2
3
4
5
6
7
8
9
async function async1() {
console.log('async1 start');
await async2();
console.log('async1 end');
}

async function async2() {
console.log('async2');
}

等同于:

1
2
3
4
5
6
7
8
9
10
11
function async1() {
console.log('async1 start');
return async2().then(function() {
console.log('async1 end');
});
}

function async2() {
console.log('async2');
return Promise.resolve();
}

JavaScript 作用域

词法作用域(也叫静态作用域)从字面意义上看是说作用域在词法化阶段(通常是编译阶段)确定而非执行阶段确定的。看例子:

1
2
3
4
5
6
7
8
9
10
let number = 42;
function printNumber() {
console.log(number);
}
function log() {
let number = 54;
printNumber();
}
// Prints 42
log();

上面代码可以看出无论 printNumber() 在哪里调用 console.log(number) 都会打印 42。动态作用域不同,console.log(number) 这行代码打印什么取决于函数 printNumber() 在哪里调用。

箭头函数的 this 指向

在非显示绑定和 new 绑定时,普通函数中的 this 总是指向调用该函数的对象,但是在剪头函数中, this 的指向是根据外层作用域来决定的,换句话说,就是箭头函数被定义时的上下文中(词法作用域内)的 this。此外箭头函数也无法使用 call apply bind 来显式绑定 this。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* 非严格模式
*/

var name = 'window'

var person1 = {
name: 'person1',
show1: function () {
console.log(this.name)
},
show2: () => console.log(this.name),
show3: function () {
return function () {
console.log(this.name)
}
},
show4: function () {
return () => console.log(this.name)
}
}
var person2 = { name: 'person2' }

person1.show1() // person1,隐式绑定,this指向调用者 person1
person1.show1.call(person2) // person2,显式绑定,this指向 person2

person1.show2() // window,箭头函数绑定,this指向外层作用域,即全局作用域
person1.show2.call(person2) // window,箭头函数绑定,this指向外层作用域,即全局作用域

person1.show3()() // window,默认绑定,这是一个高阶函数,调用者是window
// 类似于`var func = person1.show3()` 执行`func()`
person1.show3().call(person2) // person2,显式绑定,this指向 person2
person1.show3.call(person2)() // window,默认绑定,调用者是window

person1.show4()() // person1,箭头函数绑定,this指向外层作用域,即person1函数作用域
person1.show4().call(person2) // person1,箭头函数绑定,
// this指向外层作用域,即person1函数作用域
person1.show4.call(person2)() // person2

1.2 实现类

实现一个类型判断的方法

1
2
3
4
5
6
7
8
9
10
11
12
function getType(value){
var type = typeof value;
// 基本类型使用 typeof 的返回结果
if(type !== "object"){
return type;
}
// 如果是 object 才能使用 prototype.toString 方法
else{
// 引用类型通过正则匹配去掉前后多余字符
return Object.prototype.toString.call(value).replace(/^\[object (\S+)\]$/,"$1");
}
}

如何实现一个深拷贝

参考文章

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function isObject(obj) {
return typeof obj === "object" && obj !== null;
}

function deepClone(obj, map = new WeakMap()) {
if (!isObject(obj)) {
return obj;
}
// 判断当前对象是否已经被拷贝过,防止循环引用
if (map.has(obj)) {
return map.get(obj);
}
const newObj = Array.isArray(obj) ? [] : {};
map.set(obj, newObj);
[
...Object.keys(obj),
// Symbol 作为对象的 key 时,使用 for...in 和 Object.keys 都拿不到,必须使用 getOwnPropertySymbols 才能拿到
...Object.getOwnPropertySymbols(obj)
].forEach((key) => {
const value = obj[key];
newObj[key] = isObject(value) ? deepClone(value, map) : value;
});
return newObj;
}

重点:

  • 深拷贝的意义
  • 深拷贝与浅拷贝的区别
  • JSON.parse(JSON.stringify(obj)) 的缺陷 参考
  • 至少能够熟练实现对Object、Array、null、undefined这几种数据类型的拷贝,写出完整的拷贝方法是加分项

用 JS 实现一个继承

参考文章

重点:

  • 参考文章中的八种继承方案必须全部理解
  • 熟练掌握寄生组合式继承
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
* subInstance.__proto__ -> SubClass.prototype
* SubClass.prototype.__proto__ -> SuperClass.prototype
*/
function inherit(SubClass, SuperClass) {
const parent = Object.create(SuperClass.prototype);
for (let key in SubClass.prototype) {
Object.defineProperty(parent, key, {
value: SubClass.prototype[key],
});
}
SubClass.prototype = parent;
// 修正 constructor
SubClass.prototype.constructor = SubClass;
}

function Animal(name) {
this.name = name || "unknown";
}
Animal.prototype.eat = function () {
console.log("ku ku");
};

function Cat(name, age) {
Animal.call(this, name);
this.age = age || NaN;
}
Cat.prototype.bark = function () {
console.log("mew~");
};

inherit(Cat, Animal);

const cat = new Cat("YiDianDian", "2 month");
cat.eat();
cat.bark();
console.log({
name: cat.name,
age: cat.age,
}); // { name: 'YiDianDian', age: '2 month' }

console.log("=================");

console.log(cat instanceof Animal); // true
console.log(cat.constructor); // [Function: Cat]
console.log(cat.__proto__.__proto__ === Animal.prototype); // true
console.log(Cat.__proto__ === Animal); // false

call apply bind 的实现

参考文章

重点:

  • 先理解 call apply bind 的区别,然后再理解他们各自的使用场景,最后再去实现
  • bind 方法在柯里化函数中的实践 参考
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function call2(context, ...args) {
context = context || window;
// 利用当前函数中的 this 指向为函数的调用者,来拿到 call2 的调用函数
context.fn = this;
// 再次利用函数的调用者是函数中的 this,来将 context 绑定到调用函数上
context.fn(...args);
delete context.fn;
}
Function.prototype.call2 = call2;

// apply 与 call2 类似,不再演示

function bind2(context, ...bindArgs) {
const self = this;
function bindFunc(...args) {
const fullArgs = [...bindArgs, ...args];
if (this instanceof bindFunc) {
self.call2(this, ...fullArgs);
} else {
self.call2(context, ...fullArgs);
}
}
bindFunc.prototype = self.prototype;
return bindFunc;
}
Function.prototype.bind2 = bind2;

实现 Object.create

Object.create 会创建一个新的对象,并且将参数位的目标对象,与新创建的对象会进行原型链链接(newObject.__proto__ === targetObject)。

实现:

1
2
3
4
5
function createObject(proto) {
const Fn = function () {};
Fn.prototype = proto;
return new Fn();
}

实现 new 方法

1
2
3
4
5
6
7
8
function objectFactory(constructor, ...args) {
var obj = new Object(),
obj.__proto__ = constructor.prototype;
// 以上两步可以精简为:
// var obj = Object.create(constructor.prototype);
var ret = constructor.apply(obj, args);
return typeof ret === 'object' ? ret : obj;
};

实现 instanceof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function instOf(inst, cons) {
let parent = inst?.__proto__;
if (!parent) {
return false;
}
let isOnProto = false;
while (parent && !isOnProto) {
if (parent === cons?.prototype) {
isOnProto = true;
} else {
parent = parent?.__proto__;
}
}
return isOnProto;
}

class Animal {
constructor() {}
}

class Cat extends Animal {
constructor() {
super();
}
}

const cat = new Cat();

console.log(instOf(cat, Cat)); // true
console.log(instOf(cat, null)); // false

节流与防抖

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 节流
function throttle(fn, time) {
let timer = null;
return function (...args) {
if (!timer) {
fn.call(this, ...args);
timer = setTimeout(() => {
timer = null;
}, time);
}
};
}

// 防抖
function debounce(fn, time) {
let timer = null;
return function (...args) {
if (timer) {
clearTimeout(timer);
}
timer = setTimeout(() => {
fn.call(this, ...args);
timer = null;
}, time);
};
}

共同点:

  • 都需要使用闭包创建一个 timer 存放计时器
  • 都在定时器执行完毕时才将 timer 置空

不同点:

  • 在执行节流函数时如果检测到没有计时器就立即执行 fn,然而在执行防抖函数时是在定时器执行完毕后才执行 fn
  • 节流函数不会去主动结束已有的定时器,而防抖函数在执行后总是会清除上一个定时器

Promise 各个静态方法实现

Promise.all:Promise.all()方法接受一个数组为参数,数组中是promise,如果数组中的promise都是resolve状态,那么Promise.all()正常返回resolve,返回的数据为一个数组,就是参数中每个promise的结果组成的数组。如果promise.all()中任何一个是reject,那么promise.all()直接reject。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//  假设我们已经实现了_Promise  
Promise._all = (promiseList) => {
return new _Promise((resolve, reject) => {
if (!Array.isArray(promiseList)) {
reject(new TypeError('参数错误!'))
}
let count = 0
let valueList = new Array(promiseList.length)
promiseList.forEach((promise, index) => {
_Promise.resolve(promise).then(result => {
count++
valueList[index] = result // 将每次返回的结果搜集起来
if (count === promiseList.length) {
// 表示所有的promise都有结果,最终将所有的结果都resolve出去
resolve(valueList)
}
}, err => reject(err))
})
})
}

Promise.race:Promise.race() 静态方法接受一个 promise 可迭代对象作为输入,并返回一个 Promise。如果其中一个 promise 处于 fulfilled 或者 reject 后,Promise.race 所创建的 promise 会立刻被敲定,执行 then 或者 catch 逻辑。未敲定的 promise 仍会执行,但不会影响 Promise.race 所创建的 promise 了。

1
2
3
4
5
Promise._race = promises => new Promise((resolve, reject) => {
promises.forEach(promise => {
promise.then(resolve, reject)
})
})

Promise.allSettled:Promise.allSettled() 可以获取数组中每个 promise 的结果,无论成功或失败。

1
2
3
4
5
6
7
8
9
const rejectHandler = reason => ({status: "rejected", reason})
const resolveHandler = value => ({status: "fulfilled", value})
Promise.allSettled = promises =>
Promise.all(
promises.map((promise) =>
Promise.resolve(promise)
.then(resolveHandler, rejectHandler)
)
);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
MyPromise.allSettled = function(values) {
let promises = [].slice.call(values)
return new MyPromise((resolve, reject) => {
let result = [], count = 0
promises.forEach(promise => {
MyPromise.resolve(promise).then(value=>{
result.push({status: 'fulfilled', value})
}).catch(err=>{
result.push({status: 'rejected', value: err})
}).finally(()=>{
if(++count === promise.length) {
resolve(result)
}
})
})
})
}

2. CSS 相关

元素居中的方案

参考文章

重点:

  • 垂直居中
    • 绝对定位 + transform 的实现是重中之重
  • table 布局居中了解有这么个方案,但是不重要,没有实现意义

纯 CSS 绘制三角形

参考文章

CSS 选择器以及其优先级

参考文章

重点:

  • 优先级计算规则 参考
  • 掌握常用的选择器

伪类与伪元素

参考文章

重点:

  • 伪类与伪元素的区别

3. 网络原理

引用

HTTPS

从输入 URL 到页面展示到底发生了什么

参考文章

参考文章太多了,上面的是相对完整的,但是冗长,需要自己整理精简后理解,具体的概念去了解对应的专题。

不要仅局限于参考文章中列出的知识扩展,作者文字过于抽象(比如TCP三次握手),没到一个相关的知识扩展,建议去搜这个知识点相关更好更全的文章。

重点:

  • 大体描述整个过程
  • DNS lookup(向上查找)的过程
  • TPC 的三次握手四次挥手,熟练说出整个过程,并明白每个步骤的意义,每次交互发送的报文内容(如 SYN = 1, seq = x)记不住可以不记,最好记住发送报文后服务器与客户端各处的状态。
  • 命中协商缓存后的过程
  • 浏览器渲染页面的过程,渲染阻塞的问题 参考

这道题是个经典题目,因为涉及的知识面广,每一个步骤都可以深入提问,因此只了解大致过程并没有什么用,很容易被面试管逼问更深层的内容而回答不上来导致减分。

这道题的回答策略是先跟面试官简述整体的过程,让面试官知道你有一个清晰的思路并且整体流程是正确的,然后再 主动 展开详细阐述每个过程的具体经过。如果不能完全掌握这道题的话,一定要努力把自己所知道的一切都倾倒在这个题中,也就是说能回答的多详细就回答多详细(这样还能主动拉长面试时间),把话语权掌握在自己手中,千万不要等着面试管主动向你提问关于这道题更深的内容,这样很容易翻车。

4. 框架

面试题参考视频

Vue 响应式原理

Vue2响应式原理(必须掌握,代码跟着敲一遍)

视频参考笔记

Vue2 响应式原理基于 Object.defineProperty,Vue3 响应式原理基于 Proxy,两者思想都是一样的,只不过具体实现不一样而已,先搞懂 Vue2,Vue3 的原理就会很快理解。而且目前Object.definePropertyProxy 应用更广,了解 Vue2 原理有助于对 Object 的理解。

重点:

  • MVVM(数据双向绑定)的实现
  • watch、computed 的原理

为什么说 Vue 的响应式更新精确到组件级别而 React 不行

Vue 在组件的依赖发生变化时,就会重新渲染对应的组件,在渲染过程中遇到子节点时会进行 DOM Diff,但是遇到子组件时只会对组件上的 props、listeners 等属性进行更新,而不会深入到组件内部进行更新。假如父组件向子组件传入的 props 发生了变更,那么子组件的 watcher 就会被触发,进而更新子组件。

Vue 每个组件都有自己的渲染 watcher,它掌管了当前组件的视图更新,但是并不会掌管 ChildComponent 的更新。

而在 React 中,组件更新是自顶向下递归更新的,父组件的更新会引起子组件的重新渲染,因为 React 遵循 Immutable 的设计思想,永远不在原对象上修改属性,那么 Vue 的响应式依赖收集就无法实现,React 便无法得知子组件是否需要更新,因此只能将子组件全部重新渲染一遍,然后再使用 Diff 算法来决定哪一部分的视图需要更新。

参考文章

v-if 和 v-for 为什么不能一起使用

在 Vue 生成 DOM 树的算法中,v-for 的优先级高于 v-if,因此会先进行遍历出 DOM 节点,然后在判断元素是否显示,这会造成不必要的性能浪费。

参考

Vue2 相比 Vue3

特性:

  • 原生支持 TypeScript;
  • 新增了 Composition API,与 Option API 相比代码可读性更好,代码复用更简明,TypeScript 支持更好;
  • 支持多根节点;
  • 支持 Teleport;

性能提升:

  • Vue3 对不参与更新的元素,比如没有任何响应式数据参与的普通 DOM 节点,会在编译阶段进行静态提升,渲染时直接使用,并通过一个静态标记,不参与 diff 算法的对比中;
  • Vue2 绑定事件行为会被视为动态绑定,所以每次都会去追踪它的变化,而 Vue3 事件监听会被缓存;
  • SSR 优化,当静态内容大到一定量级时候,会用createStaticVNode方法在客户端去生成一个static node,这些静态node,会被直接innerHtml,就不需要创建对象,然后根据对象渲染;
  • 代码体积更小,支持 Tree shaking;
  • 使用 Proxy 实现响应式系统(无法兼容 IE),不需要在响应式对象创建时就进行深度遍历所有嵌套对象来挂载响应式,而是在嵌套对象被访问时才将其转化为一个响应式对象(Vue2 没有这么做是设计问题);

生命周期:

  • Vue3 没有 beforeCreatedcreated 生命周期函数;
  • setupbeforeCreated 前执行;
  • Vue3 中在 setup 调用的生命周期函数,如果在 options 中定义了相同类型的回调函数,那么 setup 中调用的声明函数更优先执行,比如 onMountedmounted 之前执行;

实现一个 Toast 弹窗组件

组件实现不再多讲,主要讲一下如何将 Toast 组件使用指令方式调用,如调用 showToast({...}) 后显示在页面上,并且返回一个 destory 方法用于手动销毁 Toast。

Vue3 中可以用 createVNode 创建组件 VNode 实例,然后使用 render 函数渲染到目标 DOM 上:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import { createVNode, h, render } from "vue";
import Toast from "./index.vue";
import { toastDefaultProps, type ToastProps } from "./const";

export const showToast = (options: ToastProps) => {
const opt = { ...toastDefaultProps, ...options };
const vnode = createVNode(Toast, opt);
const container = document.createElement("div");
render(vnode, container);
document.body.appendChild(container);

const destroy = () => {
render(null, container);
document.body.removeChild(container);
};

if (opt.delay) {
setTimeout(() => {
destroy();
}, opt.delay);
}

return {
destroy,
};
};

此外,还可以使用 createApp 的方式来挂载组件到 DOM 中:

1
2
3
4
5
6
7
8
9
10
11
12
export function useMountComponent(component: Component) {
const app = createApp(component);
const appDom = document.createElement("div");
document.body.appendChild(appDom);
return {
instance: app.mount(appDom),
unmount() {
app.unmount();
document.body.removeChild(appDom);
},
};
}

如果是 Vue2,可以使用 Vue.extend 的方式获得组件实例:

1
2
3
4
import Modal from './Modal.vue';
const ComponentClass = Vue.extend(Modal);
const instance = new ComponentClass({ el: document.createElement("div") });
document.body.appendChild(instance.$el);

性能优化手段

  • props 稳定性,尽量避免 props 频繁更新;
  • 使用 v-once 可以让组件跳过后续渲染;
  • 使用 v-memo 可以有条件的跳过某些大型 DOM 结构的更新,甚至连虚拟 DOM 的创建都会被跳过;
  • 计算属性稳定性,尽可能让 computed 返回一个值类型,而不是引用类型的数据,这样 computed 值会尽可能的减少非必要的副作用触发;
  • 使用虚拟列表;
  • 使用 shallowRefshallowReactive 来绕开深度响应;
  • 避免过多的组件抽象,渲染组件比渲染普通 DOM 节点要昂贵得多;

5. 算法

斐波那契数列

斐波那契数,指的是这样一个数列:1、1、2、3、5、8、13、21、……在数学上,斐波那契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=Fn-1+Fn-2(n>=2,n∈N*),用文字来说,就是斐波那契数列由 0 和 1 开始,之后的斐波那契数列系数就由之前的两数相加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function fib(num) {
if (num <= 1) {
return num;
}
return fib(num - 1) + fib(num - 2);
}

function perfFib(num) {
let a = 0,
b = 1;
for (let i = 0; i < num - 1; i++) {
const temp = b;
b = a + b;
a = temp;
}
return b;
}

fib 方法利用闭包方式实现,但是如果 num 值过大,会造成递归函数嵌套过深,导致堆债溢出。perfFib 方法不使用递归实现可以避免堆栈溢出问题。

深度优先 & 广度优先

深度优先:

1
2
3
4
5
6
7
8
9
10
let dfs = (node, nodeList = []) => {
if (node !== null) {
nodeList.push(node)
let children = node.children
for (let i = 0; i < children.length; i++) {
dfs(children[i], nodeList)
}
}
return nodeList
}

广度优先:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
let bfs = (node) => {
let nodes = []
let stack = []
if (node) {
stack.push(node)
while (stack.length) {
let item = stack.shift()
nodes.push(item)
// 队列,先进先出
// nodes = [] stack = [parent]
// nodes = [parent] stack = [child1,child2,child3]
// nodes = [parent, child1] stack = [child2,child3,child1-1,child1-2]
// nodes = [parent,child1,child2]
let children = item.children
for (let i = 0; i < children.length; i++) {
stack.push(children[i])
}
}
}
return nodes
}

扁平化数组

1
2
3
function flat(arr) {
return [].concat(...arr.map(item => Array.isArray(item) ? flat(item) : [item]))
}

求连续

随机生成一个长度为 10 的整数类型的数组,例如 [2, 10, 3, 4, 5, 11, 10, 11, 20],将其排列成一个新数组,要求新数组形式如下,例如 [[2, 3, 4, 5], [10, 11], [20]]

思路:对目标数组进行去重和排序后,遍历目标数组,在每次遍历时取结果数组 acc 的最后一位 lastArr(这是排的原因)及其最后一个元素 lastVal ,将当前项 cur 与其进行对比,如果紧邻则将其推入 lastArr 否则,向 acc 中新增一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function formArray(arr: any[]) {
const sortedArr = Array.from(new Set(arr)).sort((a, b) => a - b);

return sortedArr.reduce((acc, cur) => {
const lastArr = acc.slice().pop() || [];

const lastVal = lastArr.slice().pop();
if (lastVal!=null && cur-lastVal === 1) {
lastArr.push(cur);
} else {
acc.push([cur]);
}

return acc;
}, []);
}

字符串匹配

实现一个字符串匹配算法,从长度为 n 的字符串 S 中,查找是否存在字符串 T,T 的长度是 m,若存在返回所在位置。

使用正则表达式 match:

1
2
3
fucntion matchStr(str, targetStr){
return str.match(new RegExp(targetStr))?.index ?? -1
}

遍历字符串:

1
2
3
4
5
6
7
const find = (S, T) => {
if (S.length < T.length) return -1
for (let i = 0; i < S.length; i++) {
if (S.slice(i, i + T.length) === T) return i
}
return -1
}

移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

示例:

1
2
3
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

  1. 必须在原数组上操作,不能拷贝额外的数组。
  2. 尽量减少操作次数。

需要注意数组塌陷,并且不能遍历到已经移动到尾部的 0。

1
2
3
4
5
6
7
8
9
10
11
function sortZero(arr) {
let zeroCount = 0;
for (let i = 0; i < arr.length - zeroCount; i++) {
if (arr[i] === 0) {
arr.splice(i, 1);
arr.push(0);
i--;
zeroCount++;
}
}
}

数组转树

以下数据结构中,id 代表部门编号,name 是部门名称,parentId 是父部门编号,为 0 代表一级部门,现在要求实现一个 convert 方法,把原始 list 转换成树形结构,parentId 为多少就挂载在该 id 的属性 children 数组下,结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// 原始 list 如下
let list =[
{id:1,name:'部门A',parentId:0},
{id:2,name:'部门B',parentId:0},
{id:3,name:'部门C',parentId:1},
{id:4,name:'部门D',parentId:1},
{id:5,name:'部门E',parentId:2},
{id:6,name:'部门F',parentId:3},
{id:7,name:'部门G',parentId:2},
{id:8,name:'部门H',parentId:4}
];
const result = convert(list, ...);

// 转换后的结果如下
let result = [
{
id: 1,
name: '部门A',
parentId: 0,
children: [
{
id: 3,
name: '部门C',
parentId: 1,
children: [
{
id: 6,
name: '部门F',
parentId: 3
}, {
id: 16,
name: '部门L',
parentId: 3
}
]
},
{
id: 4,
name: '部门D',
parentId: 1,
children: [
{
id: 8,
name: '部门H',
parentId: 4
}
]
}
]
},
···
];

如果从上到下生成树,那么将会多次遍历原数组,时间复杂度为 O(2n),要想做到时间复杂度为 O(1) 那么整体思想就是去遍历一遍原数组在遍历的过程中去查找每个元素在树上的 parent,同时创建一个 map 来快速根据 parentId 来找到 parent 节点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function convert(list) {
const res = []
const map = list.reduce((res, v) => (res[v.id] = v, res), {})
for (const item of list) {
if (item.parentId === 0) {
res.push(item)
continue
}
if (item.parentId in map) {
const parent = map[item.parentId]
parent.children = parent.children || []
parent.children.push(item)
}
}
return res
}

路径查找

有一个树形结构的数据,要求给出一个节点的 id,输出这个节点在树上的路径:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
const data = [
{
id: "1",
name: "test1",
children: [
{
id: "11",
name: "test11",
children: [
{
id: "111",
name: "test111",
},
{
id: "112",
name: "test112",
},
],
},
{
id: "12",
name: "test12",
children: [
{
id: "121",
name: "test121",
},
{
id: "122",
name: "test122",
},
],
},
],
},
];

function findPath(data, targetVal, path = []) {
for (let i = 0; i < data.length; i++) {
const item = data[i];
// 记录当前的路径
path.push(item.id);
// dfs
if (item.children && item.children.length) {
const findTarget = findPath(item.children, targetVal, path);
// 找到目标时跳出递归
if (findTarget) {
return findTarget;
}
}
if (item.id === targetVal) {
// 找到目标时跳出当前循环
return path.slice();
}
// 回溯时要 pop 出当前的元素,让兄弟节点使用已有的路径
path.pop();
}
}

console.log(findPath(data, "122")); // [ '1', '12', '122' ]

递归反转字符串

用 JavaScript 写一个函数,输入 int 型,返回整数逆序后的字符串。如:输入整型 1234,返回字符串“4321”。要求必须使用递归函数调用,不能用全局变量,输入函数必须只有一个参数传入,必须返回字符串。

解析:将数字拆解为左右两个字符串,如 1234 拆解为 1234,让后将两个字符串调换位置,同时对 234 字符串进行递归调用当前函数,当处理的字符串只有一个字符时跳出递归。

1
2
3
4
5
6
7
8
9
function reverseNum(num) {
const numStr = "" + num;
if (numStr.length === 1) {
return numStr;
}
const left = numStr.slice(0, 1);
const right = numStr.slice(1);
return reverseNum(right) + left;
}

如果 reverseNum 递归时必须接收 Number,则可以使用除模运算来将数字 1234 拆解为 1234 进行反转。

6. 其他