二分查找数组中出现的第一个元素
代码如下：
代码语言：javascript复制function binarySearch(array, target) {
function getFirstItem(idx) {
while(idx >= 0 && array[idx] === target) {
idx -= 1;
}
return idx 1;
}
function search(left, right) {
while(left <= right) {
let mid = Math.floor((left right) / 2);
if(array[mid] === target) {
// 看看 mid 的左边元素是不是与 target 相等（因此要找第一个出现的元素）
return getFirstItem(mid - 1);
} else if(array[mid] > target) {
right = mid - 1;
} else {
left = mid 1;
}
}
return -1;
}
return search(0, array.length - 1);
}
防抖、节流
防抖：
代码语言：javascript复制function debounce(fn, delay) {
let timer = null;
return function(...args) {
let self = this;
clearTimeout(timer);
timer = setTimeout(function() {
fn.apply(self, args);
}, delay);
}
}
节流：
代码语言：javascript复制function throttle(fn, delay) {
let timer = null;
return function(...args) {
let self = this;
// 首次调用不延迟
if(!timer) {
fn.apply(self, args);
}
if(timer) return;
timer = setTimeout(function() {
fn.apply(self, args);
timer = null;
}, delay);
}
}
防抖和节流的不同
防抖动是将多次执行变为最后一次执行，节流是将多次执行变成每隔一段时间执行。
判断一个链表是否有环
使用快慢指针：
代码语言：javascript复制function hasCycle(node) {
if(!node || !node.next) {
return false;
}
let slow = node;
let fast = node.next;
while(slow !== fast) {
// 如果没有环，则快指针会抵达终点
if(!fast || !fast.next) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
// 如果有环，那么快指针会追上慢指针
return true;
}
使用 Map 或者 Set：
代码语言：javascript复制function hasCycle(node) {
let cache = new Map(),
temp = node;
while(temp) {
cache.set(temp, true);
temp = temp.next;
if(cache.get(temp)) {
return true;
}
}
return false;
}
HTML 模板解析
题目如下：
代码语言：javascript复制<script id="test" type="text/html">
<h1>{{title}} world!</h1>
<div>
<h3>My name is {{data.name}}</h3>
<h4>I'm {{data.age}}</h4>
</div>
</script>
<script>
const user = {
title: 'hello',
data: {
name: 'XiaoMing',
age: 20
}
};
// template 会把数据填充到模板里
const html = template('test', user);
</script>
可以使用正则表达式来实现：
代码语言：javascript复制function template(id, data) {
let content = document.getElementById(id).innerHTML;
// 匹配 {{...}}
const templateReg = /{{s*(. )s*}}/g;
// 匹配 a.b[1] 形式的数组
const arrayReg = /(w )s*[(d )]/g;
// 主项就行匹配
let templateData = templateReg.exec(content);
while(templateData) {
// 拿到整体的模板 {{...}} 和 其中的属性
let [templateStr, protoStr] = templateData;
// 分离属性链
let protoArr = protoStr.split('.');
let tempData = data;
// 遍历
protoArr.forEach(proto => {
// 看看有没有数组
let execArr = arrayReg.exec(proto);
if(execArr) {
let [, protoName, index] = execArr;
tempData = tempData[protoName][index];
} else {
tempData = tempData[proto];
}
});
content = content.replace(templateStr, tempData);
templateData = templateReg.exec(content);
}
return content;
}
两秒后获取数组中的下一个元素
代码如下：
代码语言：javascript复制function run(array, callback) {
let len = array.length, idx = 0;
function play() {
if(idx < len) {
callback(array[idx], idx);
idx = 1;
setTimeout(play, 2000);
}
}
setTimeout(play, 2000);
}
const ary = [
'hello',
'world',
'你好呀~',
'My name is Ming'
];
run(ary, function(item) {
console.log(item);
});
DOM Diff
Tree Diff
- 将新旧两棵树逐层对比，找出哪些节点需要更新；
- 如果节点是组件就进行 Component Diff；
- 如果节点是标签就进行 Element Diff；
Component Diff
- 如果节点是组件，就先看组件类型；
- 类型不同直接替换（删除旧的）；
- 类型相同则只更新属性；
- 然后深入组件做 Tree Diff（递归）；
Element Diff
- 如果节点是原生标签，则看标签名；
- 标签名不同直接替换，相同只更新属性；
- 然后进入标签后代做 Tree Diff（递归）
作用域和作用域链
运行期上下文：当函数执行时，会创建一个称为执行上下文的内部对象。一个执行期上下文定义了一个函数执行时的环境，函数每次执行时对应的执行上下文都是独一无二的，所以多次调用一个函数会导致创建多个执行期上下文，当函数执行完毕，它所产生的执行上下文被销毁。
执行上下文包含三个部分：
- 变量对象（VO，存储着变量和函数声明）；
- 作用域链；
- this 指向
作用域：上下文中声明的变量和函数的作用范围。分为块级作用域和函数作用域。
每个 JavaScript 函数都是一个对象，对象中有些属性我们可以访问，但有些不可以，这些属性仅供 JavaScript 引擎存取，[[scope]] 就是其中之一。
[[scope]] 指的是我们所说的作用域，其中存储了执行期上下文的集合。
作用域链：[[scope]] 中存储的执行期上下文对象的集合，这个集合呈链式调用，我们把这种链式链接叫做作用域链。
代码执行过程
- 创建全局上下文；
- 全局执行上下文逐行自上而下执行，遇到函数时，函数执行上下文被 push 到执行栈顶层；
- 函数执行上下文被激活，开始执行函数中的代码，全局执行上下文被挂起；
- 函数执行完毕，函数执行上下文 pop 移除出执行栈，控制权交还给全局上下文，继续执行下面的代码。
ES5 和 ES6 中的继承
ES5 版：
代码语言：javascript复制function Super(age, gender) {
this.age = age;
this.gender = gender;
}
Super.prototype.sayAge = function() {
return this.age;
}
function Sub(name, age, gender) {
this.name = name;
Super.call(this, age, gender);
}
Sub.prototype = Object.create(Super.prototype);
Sub.prototype.constructor = Sub;
Sub.prototype.sayName = function() {
return this.name;
}
let sub = new Sub('ming', 18, 'male');
console.log(sub.sayName());
console.log(sub.sayAge());
ES6 版：
代码语言：javascript复制class Super{
constructor(age, gender) {
this.age = age;
this.gender = gender;
}
sayAge() {
return this.age;
}
}
class Sub extends Super{
constructor(name, age, gender) {
this.name = name;
super(age, gender);
}
sayName() {
return this.name;
}
}
Promise 版 Ajax
代码语言：javascript复制function ajax(url, options) {
options = Object.assign({
method: 'GET',
headers: {},
data: null
}, options);
return new Promise((resolve, reject) => {
let { method, data, headers } = options;
let xhr = new XMLHttpRequest();
xhr.open(method, url, true);
for(let header in headers) {
xhr.setRequestHeader(header, headers[header]);
}
// readyState 的值发生变化时，触发这个事件
xhr.onreadystatechange = function() {
if(xhr.readyState === 4) {
if(xhr.status === 200 || xhr.status === 304) {
resolve(xhr.response);
} else {
reject(xhr);
}
}
}
xhr.onerror = function(e) {
reject(e);
}
xhr.send(data);
});
}
全排列
输入一个没有重复数字的序列，返回其所有可能的全排列。
代码语言：javascript复制function permute(nums) {
function fn(list, tempList, nums) {
if(tempList.length === nums.length) return list.push([...tempList]);
for(let i = 0;i < nums.length;i ) {
if(tempList.includes(nums[i])) continue;
tempList.push(nums[i]);
fn(list, tempList, nums);
tempList.pop();
}
}
let result = [];
fn(result, [], nums);
return result;
}
