https://github.com/Advanced-Frontend/Daily-Interview-Question/blob/master/datum/summary.md¶
统计信息：字数 44764 阅读90分钟
第 71 - 80 题¶
第 71 题： 实现一个字符串匹配算法，从长度为 n 的字符串 S 中，查找是否存在字符串 T，T 的长度是 m，若存在返回所在位置。¶
解析：第 71 题
// 因为 T 的 length 是一定的，所以在循环S的的时候 ，循环当前项 i 后面至少还有 T.length 个元素
const find = (S, T) => {
if (S.length < T.length) return -1;
for (let i = 0; i < S.length - T.length ; i++) {
if (S.substr(i, T.length) === T) return i ;
};
return -1;
};
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
}
第 72 题： 为什么普通 for 循环的性能远远高于 forEach 的性能，请解释其中的原因。¶
解析：第 72 题
- for 循环没有任何额外的函数调用栈和上下文；
- forEach函数签名实际上是
array.forEach(function(currentValue, index, arr), thisValue)
它不是普通的 for 循环的语法糖，还有诸多参数和上下文需要在执行的时候考虑进来，这里可能拖慢性能；
在10万这个级别下， forEach 的性能是 for的十倍
for: 2.263ms
forEach: 0.254ms
在100万这个量级下， forEach 的性能是和for的一致
for: 2.844ms
forEach: 2.652ms
在1000万级以上的量级上 ， forEach 的性能远远低于for的性能
for: 8.422ms
forEach: 30.328m
第 73 题： 介绍下 BFC、IFC、GFC 和 FFC¶
BFC（Block formatting contexts）：块级格式上下文 页面上的一个隔离的渲染区域，那么他是如何产生的呢？可以触发BFC的元素有float、position、overflow、display：table-cell/ inline-block/table-caption ；BFC有什么作用呢？比如说实现多栏布局’
IFC（Inline formatting contexts）：内联格式上下文 IFC的line box（线框）高度由其包含行内元素中最高的实际高度计算而来（不受到竖直方向的padding/margin影响)IFC中的line box一般左右都贴紧整个IFC，但是会因为float元素而扰乱。float元素会位于IFC与与line box之间，使得line box宽度缩短。 同个ifc下的多个line box高度会不同 IFC中时不可能有块级元素的，当插入块级元素时（如p中插入div）会产生两个匿名块与div分隔开，即产生两个IFC，每个IFC对外表现为块级元素，与div垂直排列。 那么IFC一般有什么用呢？ 水平居中：当一个块要在环境中水平居中时，设置其为inline-block则会在外层产生IFC，通过text-align则可以使其水平居中。 垂直居中：创建一个IFC，用其中一个元素撑开父元素的高度，然后设置其vertical-align:middle，其他行内元素则可以在此父元素下垂直居中。
GFC（GrideLayout formatting contexts）：网格布局格式化上下文 当为一个元素设置display值为grid的时候，此元素将会获得一个独立的渲染区域，我们可以通过在网格容器（grid container）上定义网格定义行（grid definition rows）和网格定义列（grid definition columns）属性各在网格项目（grid item）上定义网格行（grid row）和网格列（grid columns）为每一个网格项目（grid item）定义位置和空间。那么GFC有什么用呢，和table又有什么区别呢？首先同样是一个二维的表格，但GridLayout会有更加丰富的属性来控制行列，控制对齐以及更为精细的渲染语义和控制。
FFC（Flex formatting contexts）:自适应格式上下文 display值为flex或者inline-flex的元素将会生成自适应容器（flex container），可惜这个牛逼的属性只有谷歌和火狐支持，不过在移动端也足够了，至少safari和chrome还是OK的，毕竟这俩在移动端才是王道。Flex Box 由伸缩容器和伸缩项目组成。通过设置元素的 display 属性为 flex 或 inline-flex 可以得到一个伸缩容器。设置为 flex 的容器被渲染为一个块级元素，而设置为 inline-flex 的容器则渲染为一个行内元素。伸缩容器中的每一个子元素都是一个伸缩项目。伸缩项目可以是任意数量的。伸缩容器外和伸缩项目内的一切元素都不受影响。简单地说，Flexbox 定义了伸缩容器内伸缩项目该如何布局。
解析：第 73 题
第 74 题： 使用 JavaScript Proxy 实现简单的数据绑定¶
解析：第 74 题
<body>
hello,world
<input type="text" id="model">
<p id="word"></p>
</body>
<script>
const model = document.getElementById("model")
const word = document.getElementById("word")
var obj= {};
const newObj = new Proxy(obj, {
get: function(target, key, receiver) {
console.log(`getting ${key}!`);
return Reflect.get(target, key, receiver);
},
set: function(target, key, value, receiver) {
console.log('setting',target, key, value, receiver);
if (key === "text") {
model.value = value;
word.innerHTML = value;
}
return Reflect.set(target, key, value, receiver);
}
});
model.addEventListener("keyup",function(e){
newObj.text = e.target.value
})
</script>
第 75 题：数组里面有10万个数据，取第一个元素和第10万个元素的时间相差多少¶
解析：第 75 题
数组可以直接根据索引取的对应的元素，所以不管取哪个位置的元素的时间复杂度都是 O(1)
得出结论：消耗时间几乎一致，差异可以忽略不计
JavaScript 没有真正意义上的数组，所有的数组其实是对象，其“索引”看起来是数字，其实会被转换成字符串，作为属性名（对象的 key）来使用。所以无论是取第 1 个还是取第 10 万个元素，都是用 key 精确查找哈希表的过程，其消耗时间大致相同。 @lvtraveler 请帮忙测试下稀松数组。
第 76 题：输出以下代码运行结果¶
// example 1
var a={}, b='123', c=123;
a[b]='b';
a[c]='c';
console.log(a[b]);
---------------------
// example 2
var a={}, b=Symbol('123'), c=Symbol('123');
a[b]='b';
a[c]='c';
console.log(a[b]);
---------------------
// example 3
var a={}, b={key:'123'}, c={key:'456'};
a[b]='b';
a[c]='c';
console.log(a[b]);
这题考察的是对象的键名的转换。
- 对象的键名只能是字符串和 Symbol 类型。
- 其他类型的键名会被转换成字符串类型。
- 对象转字符串默认会调用 toString 方法。
// example 1
var a={}, b='123', c=123;
a[b]='b';
// c 的键名会被转换成字符串'123'，这里会把 b 覆盖掉。
a[c]='c';
// 输出 c
console.log(a[b]);
// example 2
var a={}, b=Symbol('123'), c=Symbol('123');
// b 是 Symbol 类型，不需要转换。
a[b]='b';
// c 是 Symbol 类型，不需要转换。任何一个 Symbol 类型的值都是不相等的，所以不会覆盖掉 b。
a[c]='c';
// 输出 b
console.log(a[b]);
// example 3
var a={}, b={key:'123'}, c={key:'456'};
// b 不是字符串也不是 Symbol 类型，需要转换成字符串。
// 对象类型会调用 toString 方法转换成字符串 [object Object]。
a[b]='b';
// c 不是字符串也不是 Symbol 类型，需要转换成字符串。
// 对象类型会调用 toString 方法转换成字符串 [object Object]。这里会把 b 覆盖掉。
a[c]='c';
// 输出 c
console.log(a[b]);
第 77 题：算法题「旋转数组」¶
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1：
输入: [1, 2, 3, 4, 5, 6, 7] 和 k = 3 输出: [5, 6, 7, 1, 2, 3, 4] 解释: 向右旋转 1 步: [7, 1, 2, 3, 4, 5, 6] 向右旋转 2 步: [6, 7, 1, 2, 3, 4, 5] 向右旋转 3 步: [5, 6, 7, 1, 2, 3, 4] 1 2 3 4 5 6 示例 2：
输入: [-1, -100, 3, 99] 和 k = 2 输出: [3, 99, -1, -100] 解释: 向右旋转 1 步: [99, -1, -100, 3] 向右旋转 2 步: [3, 99, -1, -100] 1 2 3 4 5 解析：第 77 题
因为步数有可能大于数组长度，所以要先取余
function rotate(arr, k) {
const len = arr.length
const step = k % len
return arr.slice(-step).concat(arr.slice(0, len - step))
}
// rotate([1, 2, 3, 4, 5, 6], 7) => [6, 1, 2, 3, 4, 5]
第 78 题：Vue 的父组件和子组件生命周期钩子执行顺序是什么¶
解析：第 78 题
- 加载渲染过程
父beforeCreate->父created->父beforeMount->子beforeCreate->子created->子beforeMount->子mounted->父mounted - 子组件更新过程
父beforeUpdate->子beforeUpdate->子updated->父updated - 父组件更新过程
父beforeUpdate->父updated -
销毁过程
父beforeDestroy->子beforeDestroy->子destroyed->父destroyed -
父组建： beforeCreate -> created -> beforeMount
- 子组件： -> beforeCreate -> created -> beforeMount -> mounted
- 父组件： -> mounted
- 总结：从外到内，再从内到外
第 79 题：input 搜索如何防抖，如何处理中文输入¶
解析：第 79 题
防抖就不说了，主要是这里提到的中文输入问题，其实看过elementui框架源码的童鞋都应该知道，elementui是通过compositionstart & compositionend做的中文输入处理：
相关代码：
<input
ref="input"
@compositionstart="handleComposition"
@compositionupdate="handleComposition"
@compositionend="handleComposition"
>
这3个方法是原生的方法，这里简单介绍下，官方定义如下compositionstart 事件触发于一段文字的输入之前（类似于 keydown 事件，但是该事件仅在若干可见字符的输入之前，而这些可见字符的输入可能需要一连串的键盘操作、语音识别或者点击输入法的备选词）
简单来说就是切换中文输入法时在打拼音时(此时input内还没有填入真正的内容)，会首先触发compositionstart，然后每打一个拼音字母，触发compositionupdate，最后将输入好的中文填入input中时触发compositionend。触发compositionstart时，文本框会填入 “虚拟文本”（待确认文本），同时触发input事件；在触发compositionend时，就是填入实际内容后（已确认文本）,所以这里如果不想触发input事件的话就得设置一个bool变量来控制。
根据上图可以看到
输入到input框触发input事件 失去焦点后内容有改变触发change事件 识别到你开始使用中文输入法触发**compositionstart **事件 未输入结束但还在输入中触发**compositionupdate **事件 输入完成（也就是我们回车或者选择了对应的文字插入到输入框的时刻）触发compositionend事件。
那么问题来了 使用这几个事件能做什么？
因为input组件常常跟form表单一起出现，需要做表单验证
为了解决中文输入法输入内容时还没将中文插入到输入框就验证的问题
我们希望中文输入完成以后才验证
第 80 题：介绍下 Promise.all 使用、原理实现及错误处理¶
解析：第 80 题
一、Promise概念¶
Promise是JS异步编程中的重要概念，异步抽象处理对象，是目前比较流行Javascript异步编程解决方案之一。Promise.all()接受一个由promise任务组成的数组，可以同时处理多个promise任务，当所有的任务都执行完成时，Promise.all()返回resolve，但当有一个失败(reject)，则返回失败的信息，即使其他promise执行成功，也会返回失败。和后台的事务类似。和rxjs中的forkJoin方法类似，合并多个 Observable 对象 ，等到所有的 Observable 都完成后，才一次性返回值。
二、Promise.all如何使用¶
对于 Promise.all(arr) 来说，在参数数组中所有元素都变为决定态后，然后才返回新的 promise。
// 以下 demo，请求两个 url，当两个异步请求返还结果后，再请求第三个 url
const p1 = request(`http://some.url.1`)
const p2 = request(`http://some.url.2`)
Promise.all([p1, p2])
.then((datas) => { // 此处 datas 为调用 p1, p2 后的结果的数组
return request(`http://some.url.3?a=${datas[0]}&b=${datas[1]}`)
})
.then((data) => {
console.log(msg)
})
三、Promise.all原理实现¶
function promiseAll(promises){
return new Promise(function(resolve,reject){
if(!Array.isArray(promises)){
return reject(new TypeError("argument must be anarray"))
}
var countNum=0;
var promiseNum=promises.length;
var resolvedvalue=new Array(promiseNum);
for(var i=0;i<promiseNum;i++){
(function(i){
Promise.resolve(promises[i]).then(function(value){
countNum++;
resolvedvalue[i]=value;
if(countNum===promiseNum){
return resolve(resolvedvalue)
}
},function(reason){
return reject(reason)
)
})(i)
}
})
}
var p1=Promise.resolve(1),
p2=Promise.resolve(2),
p3=Promise.resolve(3);
promiseAll([p1,p2,p3]).then(function(value){
console.log(value)
})
四、Promise.all错误处理¶
有时候我们使用Promise.all()执行很多个网络请求，可能有一个请求出错，但我们并不希望其他的网络请求也返回reject，要错都错，这样显然是不合理的。如何做才能做到promise.all中即使一个promise程序reject，promise.all依然能把其他数据正确返回呢?
1、全部改为串行调用（失去了node 并发优势）¶
2、当promise捕获到error 的时候，代码吃掉这个异常，返回resolve，约定特殊格式表示这个调用成功了¶
var p1 =new Promise(function(resolve,reject){
setTimeout(function(){
resolve(1);
},0)
});
var p2 = new Promise(function(resolve,reject){
setTimeout(function(){
resolve(2);
},200)
});
var p3 = new Promise(function(resolve,reject){
setTimeout(function(){
try{
console.log(XX.BBB);
}
catch(exp){
resolve("error");
}
},100)
});
Promise.all([p1, p2, p3]).then(function (results) {
console.log("success")
console.log(results);
}).catch(function(r){
console.log("err");
console.log(r);
});
第 81 - 90 题¶
第 81 题：打印出 1 - 10000 之间的所有对称数¶
例如：121、1331 等
解析：第 81 题
第 81 题：打印出 1 - 10000 之间的所有对称数
例如：121、1331 等
[...Array(10000).keys()].filter((x) => {
return x.toString().length > 1 && x === Number(x.toString().split('').reverse().join(''))
})
第 82 题：周一算法题之「移动零」¶
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 1 2 说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
解析：第 82 题
新增：解决了有连续的0无法实现功能的问题。
function zeroMove(array) {
let len = array.length;
let j = 0;
for(let i=0;i<len-j;i++){
if(array[i]===0){
array.push(0);
array.splice(i,1);
i --;
j ++;
}
}
return array;
}
第 83 题：var、let 和 const 区别的实现原理是什么¶
解析：第 83 题
var的话会直接在栈内存里预分配内存空间，然后等到实际语句执行的时候，再存储对应的变量，如果传的是引用类型，那么会在堆内存里开辟一个内存空间存储实际内容，栈内存会存储一个指向堆内存的指针
let的话，是不会在栈内存里预分配内存空间，而且在栈内存分配变量时，做一个检查，如果已经有相同变量名存在就会报错
const的话，也不会预分配内存空间，在栈内存分配变量时也会做同样的检查。不过const存储的变量是不可修改的，对于基本类型来说你无法修改定义的值，对于引用类型来说你无法修改栈内存里分配的指针，但是你可以修改指针指向的对象里面的属性
第 84 题：请实现一个 add 函数，满足以下功能。¶
add(1); // 1
add(1)(2); // 3
add(1)(2)(3)；// 6
add(1)(2, 3); // 6
add(1, 2)(3); // 6
add(1, 2, 3); // 6
解析：第 84 题
function add() {
let args = [].slice.call(arguments);
let fn = function(){
let fn_args = [].slice.call(arguments)
return add.apply(null,args.concat(fn_args))
}
fn.toString = function(){
return args.reduce((a,b)=>a+b)
}
return fn
}
实现 1：
function currying(fn, length) {
length = length || fn.length; // 注释 1
return function (...args) { // 注释 2
return args.length >= length // 注释 3
? fn.apply(this, args) // 注释 4
: currying(fn.bind(this, ...args), length - args.length) // 注释 5
}
}
实现 2：
const currying = fn =>
judge = (...args) =>
args.length >= fn.length
? fn(...args)
: (...arg) => judge(...args, ...arg)
其中注释部分
- 注释 1：第一次调用获取函数 fn 参数的长度，后续调用获取 fn 剩余参数的长度
- 注释 2：currying 包裹之后返回一个新函数，接收参数为 ...args
- 注释 3：新函数接收的参数长度是否大于等于 fn 剩余参数需要接收的长度
- 注释 4：满足要求，执行 fn 函数，传入新函数的参数
- 注释 5：不满足要求，递归 currying 函数，新的 fn 为 bind 返回的新函数（bind 绑定了 ...args 参数，未执行），新的 length 为 fn 剩余参数的长度
第 85 题：react-router 里的 标签和 标签有什么区别¶
如何禁掉 标签默认事件，禁掉之后如何实现跳转。
先看Link点击事件handleClick部分源码
if (_this.props.onClick) _this.props.onClick(event);
if (!event.defaultPrevented && // onClick prevented default
event.button === 0 && // ignore everything but left clicks
!_this.props.target && // let browser handle "target=_blank" etc.
!isModifiedEvent(event) // ignore clicks with modifier keys
) {
event.preventDefault();
var history = _this.context.router.history;
var _this$props = _this.props,
replace = _this$props.replace,
to = _this$props.to;
if (replace) {
history.replace(to);
} else {
history.push(to);
}
}
Link做了3件事情：
- 有onclick那就执行onclick
- click的时候阻止a标签默认事件（这样子点击
<a href="/abc">123</a>就不会跳转和刷新页面） - 再取得跳转href（即是to），用history（前端路由两种方式之一，history & hash）跳转，此时只是链接变了，并没有刷新页面
解析：第 85 题
第 86 题：（京东、快手）周一算法题之「两数之和」¶
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 1 2 3 4 解析：第 86 题
function anwser (arr, target) {
let map = {}
for (let i = 0; i < arr.length; i++) {
map[arr[i]] = i
}
for (let i = 0; i < arr.length; i++) {
var d = target - arr[i]
if (map[d]) {
return [i, map[d]]
}
}
return new Error('404 not found')
}
第 87 题：在输入框中如何判断输入的是一个正确的网址。¶
解析：第 87 题
function isUrl(url) {
try {
new URL(url);
return true;
}catch(err){
return false;
}}
function isUrl(url) {
try {
new URL(url);
return true;
}catch(err){
return false;
}}
第 88 题：实现 convert 方法，把原始 list 转换成树形结构，要求尽可能降低时间复杂度¶
以下数据结构中，id 代表部门编号，name 是部门名称，parentId 是父部门编号，为 0 代表一级部门，现在要求实现一个 convert 方法，把原始 list 转换成树形结构，parentId 为多少就挂载在该 id 的属性 children 数组下，结构如下：
// 原始 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
}
]
}
]
},
···
];
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
}
第 89 题：设计并实现 Promise.race()¶
解析：第 89 题
Promise._race = promises => new Promise((resolve, reject) => {
promises.forEach(promise => {
promise.then(resolve, reject)
})
})
第 90 题：实现模糊搜索结果的关键词高亮显示¶
解析：第 90 题
考虑节流、缓存。其实还可以上列表diff+定时清理缓存
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>auto complete</title>
<style>
bdi {
color: rgb(0, 136, 255);
}
li {
list-style: none;
}
</style>
</head>
<body>
<input class="inp" type="text">
<section>
<ul class="container"></ul>
</section>
</body>
<script>
function debounce(fn, timeout = 300) {
let t;
return (...args) => {
if (t) {
clearTimeout(t);
}
t = setTimeout(() => {
fn.apply(fn, args);
}, timeout);
}
}
function memorize(fn) {
const cache = new Map();
return (name) => {
if (!name) {
container.innerHTML = '';
return;
}
if (cache.get(name)) {
container.innerHTML = cache.get(name);
return;
}
const res = fn.call(fn, name).join('');
cache.set(name, res);
container.innerHTML = res;
}
}
function handleInput(value) {
const reg = new RegExp(`\(${value}\)`);
const search = data.reduce((res, cur) => {
if (reg.test(cur)) {
const match = RegExp.$1;
res.push(`<li>${cur.replace(match, '<bdi>$&</bdi>')}</li>`);
}
return res;
}, []);
return search;
}
const data = ["上海野生动物园", "上饶野生动物园", "北京巷子", "上海中心", "上海黄埔江", "迪士尼上海", "陆家嘴上海中心"]
const container = document.querySelector('.container');
const memorizeInput = memorize(handleInput);
document.querySelector('.inp').addEventListener('input', debounce(e => {
memorizeInput(e.target.value);
}))
</script>
</html>
第 91 - 100 题¶
第 91 题：介绍下 HTTPS 中间人攻击¶
解析：第 91 题
https协议由 http + ssl 协议构成，具体的链接过程可参考SSL或TLS握手的概述
中间人攻击过程如下：
- 服务器向客户端发送公钥。
- 攻击者截获公钥，保留在自己手上。
- 然后攻击者自己生成一个【伪造的】公钥，发给客户端。
- 客户端收到伪造的公钥后，生成加密hash值发给服务器。
- 攻击者获得加密hash值，用自己的私钥解密获得真秘钥。
- 同时生成假的加密hash值，发给服务器。
- 服务器用私钥解密获得假秘钥。
- 服务器用加秘钥加密传输信息
防范方法：
- 服务端在发送浏览器的公钥中加入CA证书，浏览器可以验证CA证书的有效性
第 92 题：已知数据格式，实现一个函数 fn 找出链条中所有的父级 id¶
const value = '112'
const fn = (value) => {
...
}
fn(value) // 输出 [1， 11， 112]
- bfs利用队列实现，循环中做的是push => shift => push => shift
- dfs利用栈实现，循环中做的是push => pop => push => pop
刚刚好，中间仅仅差了一个数组方法：
function bfs(target, id) {
const quene = [...target]
do {
const current = quene.shift()
if (current.children) {
quene.push(...current.children.map(x => ({ ...x, path: (current.path || current.id) + '-' + x.id })))
}
if (current.id === id) {
return current
}
} while(quene.length)
return undefined
}
function dfs(target, id) {
const stask = [...target]
do {
const current = stask.pop()
if (current.children) {
stask.push(...current.children.map(x => ({ ...x, path: (current.path || current.id) + '-' + x.id })))
}
if (current.id === id) {
return current
}
} while(stask.length)
return undefined
}
// 公共的搜索方法，默认bfs
function commonSearch(target, id, mode) {
const staskOrQuene = [...target]
do {
const current = staskOrQuene[mode === 'dfs' ? 'pop' : 'shift']()
if (current.children) {
staskOrQuene.push(...current.children.map(x => ({ ...x, path: (current.path || current.id) + '-' + x.id })))
}
if (current.id === id) {
return current
}
} while(staskOrQuene.length)
return undefined
}
解析：第 92 题
第 93 题：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log(m+n))。¶
示例 1：
nums1 = [1, 3]
nums2 = [2]
1
2
中位数是 2.0
示例 2：
nums1 = [1, 2]
nums2 = [3, 4]
1
2
中位数是(2 + 3) / 2 = 2.5
解析：第 93 题
加了注释，好理解一点，时间复杂度O(log(n+m))：
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
let m = nums1.length
let n = nums2.length
let k1 = Math.floor((m + n + 1) / 2)
let k2 = Math.floor((m + n + 2) / 2)
return (findMedianSortedArraysCore(nums1, 0, nums2, 0, k1) + findMedianSortedArraysCore(nums1, 0, nums2, 0, k2)) / 2
};
/**
*
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number} i
* @param {number} j
* @param {number} k
* @return {number}
*/
const findMedianSortedArraysCore = (nums1, i, nums2, j, k) => {
// 如果数组起始位置已经大于数组长度-1
// 说明已经是个空数组
// 直接从另外一个数组里取第k个数即可
if (i > nums1.length - 1) {
return nums2[j + k - 1]
}
if (j > nums2.length - 1) {
return nums1[i + k - 1]
}
// 如果k为1
// 就是取两个数组的起始值里的最小值
if (k === 1) {
return Math.min(nums1[i], nums2[j])
}
// 取k2为(k/2)或者数组1的长度或者数组2的长度的最小值
// 这一步可以避免k2大于某个数组的长度（长度为从起始坐标到结尾）
let k2 = Math.floor(k / 2)
let length1 = nums1.length - i
let length2 = nums2.length - j
k2 = Math.min(k2, length1, length2)
let value1 = nums1[i + k2 - 1]
let value2 = nums2[j + k2 - 1]
// 比较两个数组的起始坐标的值
// 如果value1小于value2
// 就舍弃nums1前i + k2部分
// 否则舍弃nums2前j + k2部分
if (value1 < value2) {
return findMedianSortedArraysCore(nums1, i + k2, nums2, j, k - k2)
} else {
return findMedianSortedArraysCore(nums1, i, nums2, j + k2, k - k2)
}
}
第 94 题：vue 在 v-for 时给每项元素绑定事件需要用事件代理吗？为什么？¶
解析：第 94 题
说一下我个人理解，先说结论，可以使用
事件代理作用主要是 2 个
- 将事件处理程序代理到父节点，减少内存占用率
- 动态生成子节点时能自动绑定事件处理程序到父节点
这里我生成了十万个 span 节点，通过 performance monitor 来监控内存占用率和事件监听器的数量，对比以下 3 种情况
- 不使用事件代理，每个 span 节点绑定一个 click 事件，并指向同一个事件处理程序
<div>
<span
v-for="(item,index) of 100000"
:key="index"
@click="handleClick">
{{item}}
</span>
</div>
- 不使用事件代理，每个 span 节点绑定一个 click 事件，并指向不同的事件处理程序
<div>
<span
v-for="(item,index) of 100000"
:key="index"
@click="function () {}">
{{item}}
</span>
</div>
- 使用事件代理
<div @click="handleClick">
<span
v-for="(item,index) of 100000"
:key="index">
{{item}}
</span>
</div>
可以看到使用事件代理无论是监听器数量和内存占用率都比前两者要少
同时对比 3 个图中监听器的数量以及我以往阅读 vue 源码的过程中，并没有发现 vue 会自动做事件代理，但是一般给 v-for 绑定事件时，都会让节点指向同一个事件处理程序（第二种情况可以运行，但是 eslint 会警告），一定程度上比每生成一个节点都绑定一个不同的事件处理程序性能好，但是监听器的数量仍不会变，所以使用事件代理会更好一点
第 95 题：模拟实现一个深拷贝，并考虑对象相互引用以及 Symbol 拷贝的情况¶
解析：第 95 题
一个不考虑其他数据类型的公共方法，基本满足大部分场景
function deepCopy(target, cache = new Set()) {
if (typeof target !== 'object' || cache.has(target)) {
return target
}
if (Array.isArray(target)) {
target.map(t => {
cache.add(t)
return t
})
} else {
return [...Object.keys(target), ...Object.getOwnPropertySymbols(target)].reduce((res, key) => {
cache.add(target[key])
res[key] = deepCopy(target[key], cache)
return res
}, target.constructor !== Object ? Object.create(target.constructor.prototype) : {})
}
}
主要问题是
- symbol作为key，不会被遍历到，所以stringify和parse是不行的
- 有环引用，stringify和parse也会报错
我们另外用getOwnPropertySymbols可以获取symbol key可以解决问题1，用集合记忆曾经遍历过的对象可以解决问题2。当然，还有很多数据类型要独立去拷贝。比如拷贝一个RegExp，lodash是最全的数据类型拷贝了，有空可以研究一下
另外，如果不考虑用symbol做key，还有两种黑科技深拷贝，可以解决环引用的问题，比stringify和parse优雅强一些
function deepCopyByHistory(target) {
const prev = history.state
history.replaceState(target, document.title)
const res = history.state
history.replaceState(prev, document.title)
return res
}
async function deepCopyByMessageChannel(target) {
return new Promise(resolve => {
const channel = new MessageChannel()
channel.port2.onmessage = ev => resolve(ev.data)
channel.port1.postMessage(target)
}).then(data => data)
}
无论哪种方法，它们都有一个共性：失去了继承关系，所以剩下的需要我们手动补上去了，故有Object.create(target.constructor.prototype)的操作
或者
const symbolName = Symbol();
const obj = {
objNumber: new Number(1),
number: 1,
objString: new String('ss'),
string: 'stirng',
objRegexp: new RegExp('\\w'),
regexp: /w+/g,
date: new Date(),
function: function () {},
array: [{a: 1}, 2],
[symbolName]: 111
}
obj.d = obj;
const isObject = obj => obj !== null && (typeof obj === 'object' || typeof obj === 'function');
const isFunction = obj => typeof obj === 'function'
function deepClone (obj, hash = new WeakMap()) {
if (hash.get(obj)) {
// 环处理
return hash.get(obj);
}
if (!isObject(obj)) {
return obj;
}
if (isFunction(obj)) {
// function返回原引用
return obj;
}
let cloneObj;
const Constructor = obj.constructor;
switch (Constructor) {
case Boolean:
case Date:
return new Date(+obj);
case Number:
case String:
case RegExp:
return new Constructor(obj);
default:
cloneObj = new Constructor();
hash.set(obj, cloneObj);
}
[...Object.getOwnPropertyNames(obj), ...Object.getOwnPropertySymbols(obj)].forEach(k => {
cloneObj[k] = deepClone(obj[k], hash);
})
return cloneObj;
}
const o = deepClone(obj)
console.log(o.objNumber === obj.objNumber);
console.log(o.number === obj.number);
console.log(o.objString === obj.objString);
console.log(o.string === obj.string);
console.log(o.objRegexp === obj.objRegexp);
console.log(o.regexp === obj.regexp);
console.log(o.date === obj.date);
console.log(o.function === obj.function);
console.log(o.array[0] === obj.array[0]);
console.log(o[symbolName] === obj[symbolName]);
第 96 题：介绍下前端加密的常见场景和方法¶
解析：第 96 题
首先，加密的目的，简而言之就是将明文转换为密文、甚至转换为其他的东西，用来隐藏明文内容本身，防止其他人直接获取到敏感明文信息、或者提高其他人获取到明文信息的难度。 通常我们提到加密会想到密码加密、HTTPS 等关键词，这里从场景和方法分别提一些我的个人见解。
场景-密码传输¶
前端密码传输过程中如果不加密，在日志中就可以拿到用户的明文密码，对用户安全不太负责。 这种加密其实相对比较简单，可以使用 PlanA-前端加密、后端解密后计算密码字符串的MD5/MD6存入数据库；也可以 PlanB-直接前端使用一种稳定算法加密成唯一值、后端直接将加密结果进行MD5/MD6，全程密码明文不出现在程序中。
PlanA 使用 Base64 / Unicode+1 等方式加密成非明文，后端解开之后再存它的 MD5/MD6 。
PlanB 直接使用 MD5/MD6 之类的方式取 Hash ，让后端存 Hash 的 Hash 。
场景-数据包加密¶
应该大家有遇到过：打开一个正经网站，网站底下蹦出个不正经广告——比如X通的流量浮层，X信的插入式广告……（我没有针对谁） 但是这几年，我们会发现这种广告逐渐变少了，其原因就是大家都开始采用 HTTPS 了。 被人插入这种广告的方法其实很好理解：你的网页数据包被抓取->在数据包到达你手机之前被篡改->你得到了带网页广告的数据包->渲染到你手机屏幕。 而 HTTPS 进行了包加密，就解决了这个问题。严格来说我认为从手段上来看，它不算是一种前端加密场景；但是从解决问题的角度来看，这确实是前端需要知道的事情。
Plan 全面采用 HTTPS
场景-展示成果加密¶
经常有人开发网页爬虫爬取大家辛辛苦苦一点一点发布的数据成果，有些会影响你的竞争力，有些会降低你的知名度，甚至有些出于恶意爬取你的公开数据后进行全量公开……比如有些食谱网站被爬掉所有食谱，站点被克隆；有些求职网站被爬掉所有职位，被拿去卖信息；甚至有些小说漫画网站赖以生存的内容也很容易被爬取。
Plan 将文本内容进行展示层加密，利用字体的引用特点，把拿给爬虫的数据变成“乱码”。 举个栗子：正常来讲，当我们拥有一串数字“12345”并将其放在网站页面上的时候，其实网站页面上显示的并不是简单的数字，而是数字对应的字体的“12345”。这时我们打乱一下字体中图形和字码的对应关系，比如我们搞成这样：
图形：1 2 3 4 5 字码：2 3 1 5 4
这时，如果你想让用户看到“12345”，你在页面中渲染的数字就应该是“23154”。这种手段也可以算作一种加密。 具体的实现方法可以看一下《Web 端反爬虫技术方案》。
参考¶
HTTPS 到底加密了什么？ Web 端反爬虫技术方案 可以说的秘密-那些我们该讨论的前端加密方法 前端加密那点事 关于反爬虫，看这一篇就够了
第 97 题：React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ，那么 O(n^3) 和 O(n) 是如何计算出来的？¶
解析：第 97 题
关于O(n^3)怎么计算出来的¶
问题描述¶
原问题标题“React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ，那么 O(n^3) 和 O(n) 是如何计算出来的？ ”
- 这里的n指的是页面的VDOM节点数，这个不太严谨。如果更严谨一点，我们应该应该假设 变化之前的节点数为m，变化之后的节点数为n。
- React 和 Vue 做优化的前提是“放弃了最优解“，本质上是一种权衡，有利有弊。
倘若这个算法用到别的行业，比如医药行业，肯定是不行的，为什么？
React 和 Vue 做的假设是：
- 检测VDOM的变化只发生在同一层
- 检测VDOM的变化依赖于用户指定的key
如果变化发生在不同层或者同样的元素用户指定了不同的key或者不同元素用户指定同样的key， React 和 Vue都不会检测到，就会发生莫名其妙的问题。
但是React 认为， 前端碰到上面的第一种情况概率很小，第二种情况又可以通过提示用户，让用户去解决，因此 这个取舍是值得的。 没有牺牲空间复杂度，却换来了在大多数情况下时间上的巨大提升。 明智的选择！
基本概念¶
首先大家要有个基本概念。
其实这是一个典型的最小编辑距离的问题，相关算法有很多，比如Git中 ，提交之前会进行一次对象的diff操作，就是用的这个最小距离编辑算法。
leetcode 有原题目, 如果想明白这个O(n^3)， 可以先看下这个。
对于树，我们也是一样的，我们定义三种操作，用来将一棵树转化为另外一棵树：
- 删除：删除一个节点，将它的children交给它的父节点
- 插入：在children中 插入一个节点
- 修改：修改节点的值
事实上，从一棵树转化为另外一棵树，我们有很多方式，我们要找到最少的。
直观的方式是用动态规划，通过这种记忆化搜索减少时间复杂度。
算法¶
由于树是一种递归的数据结构，因此最简单的树的比较算法是递归处理。
详细描述这个算法可以写一篇很长的论文，这里不赘述。 大家想看代码的，这里有一份 我希望没有吓到你。
确切地说，树的最小距离编辑算法的时间复杂度是O(n^2m(1+logmn)),
我们假设m 与 n 同阶， 就会变成 O(n^3)。
题外话¶
大家如果对数据结构和算法感兴趣，可以关注下我的leetcode题解
第 98 题：（京东）写出如下代码的打印结果¶
function changeObjProperty(o) {
o.siteUrl = "http://www.baidu.com"
o = new Object()
o.siteUrl = "http://www.google.com"
}
let webSite = new Object();
changeObjProperty(webSite);
console.log(webSite.siteUrl);
解析：第 98 题
http://www.baidu.com 函数的形参是值传递的
感觉这么说不准确。对象传值传的是引用，但是引用是copy给函数形参。
// 这里把o改成a
// webSite引用地址的值copy给a了
function changeObjProperty(a) {
// 改变对应地址内的对象属性值
a.siteUrl = "http://www.baidu.com"
// 变量a指向新的地址 以后的变动和旧地址无关
a = new Object()
a.siteUrl = "http://www.google.com"
a.name = 456
}
var webSite = new Object();
webSite.name = '123'
changeObjProperty(webSite);
console.log(webSite); // {name: 123, siteUrl: 'http://www.baidu.com'}
第 99 题：（bilibili）编程算法题¶
用 JavaScript 写一个函数，输入 int 型，返回整数逆序后的字符串。如：输入整型 1234，返回字符串“4321”。要求必须使用递归函数调用，不能用全局变量，输入函数必须只有一个参数传入，必须返回字符串。
解析：第 99 题
function fun(num){
let num1 = num / 10;
let num2 = num % 10;
if(num1<1){
return num;
}else{
num1 = Math.floor(num1)
return `${num2}${fun(num1)}`
}
}
var a = fun(12345)
console.log(a)
console.log(typeof a)
第 100 题：（京东）请写出如下代码的打印结果¶
function changeObjProperty(o) {
o.siteUrl = "http://www.baidu.com"
o = new Object()
o.siteUrl = "http://www.google.com"
}
let webSite = new Object();
changeObjProperty(webSite);
console.log(webSite.siteUrl);
function Foo() {
Foo.a = function() {
console.log(1)
}
this.a = function() {
console.log(2)
}
}
Foo.prototype.a = function() {
console.log(3)
}
Foo.a = function() {
console.log(4)
}
Foo.a();
let obj = new Foo();
obj.a();
Foo.a();
输出顺序是 4 2 1 .
function Foo() {
Foo.a = function() {
console.log(1)
}
this.a = function() {
console.log(2)
}
}
// 以上只是 Foo 的构建方法，没有产生实例，此刻也没有执行
Foo.prototype.a = function() {
console.log(3)
}
// 现在在 Foo 上挂载了原型方法 a ，方法输出值为 3
Foo.a = function() {
console.log(4)
}
// 现在在 Foo 上挂载了直接方法 a ，输出值为 4
Foo.a();
// 立刻执行了 Foo 上的 a 方法，也就是刚刚定义的，所以
// # 输出 4
let obj = new Foo();
/* 这里调用了 Foo 的构建方法。Foo 的构建方法主要做了两件事：
1. 将全局的 Foo 上的直接方法 a 替换为一个输出 1 的方法。
2. 在新对象上挂载直接方法 a ，输出值为 2。
*/
obj.a();
// 因为有直接方法 a ，不需要去访问原型链，所以使用的是构建方法里所定义的 this.a，
// # 输出 2
Foo.a();
// 构建方法里已经替换了全局 Foo 上的 a 方法，所以
// # 输出 1