# 手写常见的JS面试题 11-20
# 11、instanceOf
function instanceOf(left, right) {
while (true) {
if (!left.__proto__) return false;
if (left.__proto__ === right.prototype) return true;
left = left.__proto__;
}
}
# 12、柯里化
题目描述:柯里化（Currying），又称部分求值（Partial Evaluation）， 是把接受多个参数的函数变换成接受一个单一参数（最初函数的第一个参数）的函数， 并且返回接受余下的参数而且返回结果的新函数的技术。 核心思想是把多参数传入的函数拆成单参数（或部分）函数，内部再返回调用下一个单参数（或部分）函数，依次处理剩余的参数。
function currying(fn, ...arg) {
const len = fn.length;
const allArgs = [...arg];
const res = function () {
allArgs = [...allArgs, ...arguments];
if (allArgs.length === len) {
return fn(...allArgs);
} else {
return res;
}
}
return res;
}
# 13、冒泡排序-时间复杂度n^2
冒泡排序的过程，就是从第一个元素开始，重复比较相邻的两个项，若第一项比第二项更大，则交换两者的位置；反之不动。 每一轮操作，都会将这一轮中最大的元素放置到数组的末尾。假如数组的长度是 n，那么当我们重复完 n 轮的时候，整个数组就有序了。
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
}
最优解法
function betterBubbleSort(arr) {
const len = arr.length
for (let i = 0; i < len; i++) {
// 区别在这里，我们加了一个标志位
let flag = false
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
// 只要发生了一次交换，就修改标志位
flag = true
}
}
// 若一次交换也没发生，则说明数组有序，直接放过
if (flag == false) return arr;
}
return arr
}
# 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
}
# 15、插入排序 n^2
插入排序的核心思想是“找到元素在它前面那个序列中的正确位置”。 具体来说，插入排序所有的操作都基于一个这样的前提：当前元素前面的序列是有序的。 基于这个前提，从后往前去寻找当前元素在前面那个序列里的正确位置。
function insetSort(arr) {
const len = arr.length;
let temp;
for (let i = 0; i < len; i++) {
let j = i;
temp = arr[j];
while (j > 0 && arr[j - 1] > temp) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp;
}
return arr;
}
# 16、归并排序 O(nlog(n))
归并排序是对分治思想的典型应用，它按照如下的思路对分治思想“三步走”的框架进行了填充：
- 分解子问题：将需要被排序的数组从中间分割为两半，然后再将分割出来的每个子数组各分割为两半，重复以上操作，直到单个子数组只有一个元素为止。
- 求解每个子问题：从粒度最小的子数组开始，两两合并、确保每次合并出来的数组都是有序的。（这里的“子问题”指的就是对每个子数组进行排序）。
- 合并子问题的解，得出大问题的解：当数组被合并至原有的规模时，就得到了一个完全排序的数组
function mergeSort(arr) {
const len = arr.length
// 处理边界情况
if (len <= 1) {
return arr
}
// 计算分割点
const mid = Math.floor(len / 2)
// 递归分割左子数组，然后合并为有序数组
const leftArr = mergeSort(arr.slice(0, mid))
// 递归分割右子数组，然后合并为有序数组
const rightArr = mergeSort(arr.slice(mid, len))
// 合并左右两个有序数组
arr = mergeArr(leftArr, rightArr)
// 返回合并后的结果
return arr
}
function mergeArr(arr1, arr2) {
// 初始化两个指针，分别指向 arr1 和 arr2
let i = 0, j = 0
// 初始化结果数组
const res = []
// 缓存arr1的长度
const len1 = arr1.length
// 缓存arr2的长度
const len2 = arr2.length
// 合并两个子数组
while (i < len1 && j < len2) {
if (arr1[i] < arr2[j]) {
res.push(arr1[i])
i++
} else {
res.push(arr2[j])
j++
}
}
// 若其中一个子数组首先被合并完全，则直接拼接另一个子数组的剩余部分
if (i < len1) {
return res.concat(arr1.slice(i))
} else {
return res.concat(arr2.slice(j))
}
}
# 17、快速排序 nlog(n);
function quickSore(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, i) => v > cur);
return [...quickSore(left), cur, ...quickSore(right)];
}
# 18、二分法查找-时间复杂度log2(n);
如何确定一个数在一个有序数组中的位置
function search(arr, target) {
let left = 0, right = arr.length;
while (left <= right) {
const middle = Math.floor((left + right) / 2);
if (arr[middle] === target) return middle;
if (arr[middle] > target) {
right = middle - 1;
} else {
left = middle + 1;
}
}
return -1;
}
// const dataArr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
// const position = search(dataArr, 6);
// 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();
}, 0)
}
eat(name) {
const task = () => {
console.log(`Eat ${name}`);
this.next();
}
this.stacks.push(task);
return this;
}
sleep(delay) {
this.seleepWrapper(delay, false);
return this;
}
sleepFirst(time) {
this._sleepWrapper(time, true);
return this;
}
static seleepWrapper(delay, isFirst) {
const task = () => {
setTimeout(() => {
console.log(`Wake up after ${delay}`)
this.next();
}, delay * 1000);
}
if (isFirst) {
this.tasks.unshift(task);
} else {
this.tasks.push(task);
}
}
next() {
const task = this.tasks.shift(); // 取第一个任务执行
task && task();
}
}
function LazyMan(name) {
return new _LazyMan(name);
}
# 20、防抖、节流
function debounce(fn, delay = 300) {
let timer = null;
return function () {
if (timer) clearTimeout(timer);
timer = setTimeout(() => {
fn.apply(this, arguments);
}, delay)
}
}
function throttle(fn, delay = 300) {
let flag = true;
return function () {
if (!flag) return;
flag = false;
setTimeout(() => {
fn.apply(this, arguments);
flag = true;
}, delay);
}
}