?个人主页：前端青山
?系列专栏：JavaScript篇
?人终将被年少不可得之物困其一生
依旧青山,本期给大家带来JavaScript篇专栏内容:JavaScript全面指南
在现代Web开发中，JavaScript 是不可或缺的编程语言。掌握其核心功能和原理对于开发者至关重要。本文通过手写实现JavaScript的一些关键功能和算法，帮助读者深入理解其工作原理，提升编程技能。无论你是初学者还是有经验的开发者，都能从中受益。
目录
8、斐波那契数列
9、汉诺塔问题
10、合并两个 有序数组
11、数组中重复的数字
12、两个数组的交集 ，并集，补集，差集
13、旋转数组
14、两数之和
8、斐波那契数列
方法一：普通递归
代码优美逻辑清晰。但是有重复计算的问题，如：当n为5的时候要计算fibonacci(4) + fibonacci(3)，当n为4的要计算fibonacci(3) + fibonacci(2) ，这时fibonacci(3)就是重复计算了。运行 fibonacci(50) 会出现浏览器假死现象，毕竟递归需要堆栈，数字过大内存不够。
function fibonacci(n) { if (n == 1 || n == 2) { return 1 }; return fibonacci(n - 2) + fibonacci(n - 1);}fibonacci(30)
方法二：改进递归-把前两位数字做成参数避免重复计算
function fibonacci(n) { function fib(n, v1, v2) { if (n == 1) return v1; if (n == 2) return v2; else return fib(n - 1, v2, v1 + v2) } return fib(n, 1, 1)}fibonacci(30)
方法三：改进递归-利用闭包特性把运算结果存储在数组里，避免重复计算
var fibonacci = function () { let memo = [0, 1]; let fib = function (n) { if (memo[n] == undefined) { memo[n] = fib(n - 2) + fib(n - 1) } return memo[n] } return fib;}()fibonacci(30)
方法三1：改进递归-摘出存储计算结果的功能函数
var memoizer = function (func) { let memo = []; return function (n) { if (memo[n] == undefined) { memo[n] = func(n) } return memo[n] }};var fibonacci=memoizer(function(n){ if (n == 1 || n == 2) { return 1 }; return fibonacci(n - 2) + fibonacci(n - 1);})fibonacci(30)
循环
方法一：普通for循环
function fibonacci(n) { var n1 = 1, n2 = 1, sum; for (let i = 2; i < n; i++) { sum = n1 + n2 n1 = n2 n2 = sum } return sum}fibonacci(30)
方法二：for循环+解构赋值
var fibonacci = function (n) { let n1 = 1; n2 = 1; for (let i = 2; i < n; i++) { [n1, n2] = [n2, n1 + n2] } return n2}fibonacci(30)9、汉诺塔问题
经典的汉诺塔问题，将x塔座上n个从大到小的盘子移动到z塔座上，要求大盘子不能放在小盘子上面，可以借助y塔座，问最多需要多少次。
分析：当n=1时，可以直接将盘子从x塔座移动到z塔座； 当n>1时，要想把第n个盘子从x塔座移动到z塔座，则需要借助y塔座，即先将1~n-1盘子从x塔座移动到y塔座。然后再把第n个盘子从x塔座移动到z塔座，最后再把y塔座上1到n-1的盘子移动到z塔座上，就完成了。
那么如何将1到n-1的盘子从x移动到y，思路同上，即递归。
let c=0;let move=function(n,x,y,z){ let director=function(x,z,n){ c=c+1; console.log("第"+ c +"次移动,将第"+n+"个盘子从"+x+"移动到"+z); } if(n==1){ director(x,z,1); }else{ move(n-1,x,z,y); director(x,z,n); move(n-1,y,x,z); }}move(3,"x","y","z");10、合并两个 有序数组
这道题是我在腾讯面试的时候被问到的，当时的回答实在难以令人满意。这道题本来也不难，然后我就一步步尝试性地回答推进，首先，可以直接用数组方法concat（），当合并后数组并不关心大小排序时。接下来是，考虑合并后数组有序，这也是不难实现的，下面贴代码。
<!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <title>合并两个有序数组</title> <!-- 经常用到的数组操作方法说明：slice和splice方法参数必须是数字，不能是字母或代数式 。 slice方法并不修改原数组，如果想删除数组中的一段元素，应该使用splice方法 --></head><body> <script type="text/javascript"> //方法一：一种鸡肋方法，合并两个数组，然后调用sort方法 /*function merge(nums1, nums2) { for(var i=0;i<nums2.length;i++){ nums1.push(nums2[i]) } nums1.sort(function(a,b){//排序参数设置，实现从小到大排序 return a-b; }); return nums1; };*/ //方法二： function mergeArray(arr1,arr2){ var ind1=0; //标记arr1的对比元素的初始索引值 var ind2=0; //标记arr2的对比元素的初始索引值 var arr=[]; //作为输出的新数组 while(ind1<arr1.length && ind2<arr2.length){ //当arr1和arr2元素均未全部存入arr中，则从数组第一个元素开始进行比较，将较小的元素存入arr中 if(arr1[ind1]<=arr2[ind2]){ arr.push(arr1.slice(ind1)[0]); //若arr1元素小于arr2元素，则将arr1的元素存入arr中 ind1++;//已将元素push到输出数组中，将数组arr1的index指向移动到下一个 }else{ arr.push(arr2.slice(ind2)[0]); ind2++; } } //当不满足上述while条件（ind1<arr1.length && ind2<arr2.length）时,就直接将剩余数组元素拼接在输出数组arr后面 return arr.concat((ind1<arr1.length)?arr1.slice(ind1):arr2.slice(ind2));//这个地方也可以分开写 } var nums1=[1,2,3]; var nums2=[2,5,6]; //var arr=merge(nums1,nums2); //console.log(arr); console.log(mergeArray(nums1,nums2));//[1, 2, 2, 3, 5, 6] </script></body></html>11、数组中重复的数字
题目在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。 思路利用对象或者散列表或者下标检测 // 推荐解法function duplicate(numbers, duplication){// write code here//这里要特别注意~找到任意重复的一个值并赋值到duplication[0]//函数返回True/Falselet hash = []for (let i = 0; i < numbers.length; i++) { if (!hash[numbers[i]]) { hash[numbers[i]] = 1 } else { if (++hash[numbers[i]] === 2) { duplication[0] = numbers[i] return true } }}return false} // 解法1：下标检测function duplicate(numbers, duplication){// write code here//这里要特别注意~找到任意重复的一个值并赋值到duplication[0]//函数返回True/Falselet obj = {}for(let i = 0; i < numbers.length; i++) { if(numbers.indexOf(numbers[i]) !== i) { duplication[0] = numbers[i] return true }}return false} // 解法2：对象特性function duplicate(numbers, duplication){// write code here//这里要特别注意~找到任意重复的一个值并赋值到duplication[0]//函数返回True/Falselet obj = {}for (let i = 0; i < numbers.length; i++) { if (!obj[numbers[i]]) { obj[numbers[i]] = true } else { duplication[0] = numbers[i] return true }}return false} // 解法3：哈希散列法，其实原理和obj差不多function duplicate(numbers, duplication){// write code here//这里要特别注意~找到任意重复的一个值并赋值到duplication[0]//函数返回True/Falselet hash = []for (let i = 0; i < numbers.length; i++) { if (!hash[numbers[i]]) { hash[numbers[i]] = 1 } else { if (++hash[numbers[i]] === 2) { duplication[0] = numbers[i] return true } }}return false}
12、两个数组的交集 ，并集，补集，差集
一、简单数组 1、ES5：
const arr1 = [1,2,3,4,5], arr2 = [5,6,7,8,9];// 交集let intersection = arr1.filter(function (val) { return arr2.indexOf(val) > -1 })// 并集let union = arr1.concat(arr2.filter(function (val) { return !(arr1.indexOf(val) > -1) }))// 补集 两个数组各自没有的集合let complement = arr1.filter(function (val) { return !(arr2.indexOf(val) > -1) }).concat(arr2.filter(function (val) { return !(arr1.indexOf(val) > -1) }))// 差集 数组arr1相对于arr2所没有的let diff = arr1.filter(function (val) { return arr2.indexOf(val) === -1 })console.log('arr1: ', arr1);console.log('arr2: ', arr2);console.log('交集', intersection);console.log('并集', union);console.log('补集', complement);console.log('差集', diff);12345678910111213141516171819202122
ES6：
const arr1 = [1,2,3,4,5], arr2 = [5,6,7,8,9], _arr1Set = new Set(arr1), _arr2Set = new Set(arr2);// 交集let intersection = arr1.filter(item => _arr2Set.has(item))// 并集let union = Array.from(new Set([...arr1, ...arr2]))// 补集 两个数组各自没有的集合let complement = [...arr1.filter(item => !_arr2Set.has(item)), ...arr2.filter(item => !_arr1Set.has(item))]// 差集 数组arr1相对于arr2所没有的let diff = arr1.filter(item => !_arr2Set.has(item))console.log('arr1: ', arr1);console.log('arr2: ', arr2);console.log('交集', intersection);console.log('并集', union);console.log('补集', complement);console.log('差集', diff);1234567891011121314151617181920212223
JQ:
const arr1 = [1,2,3,4,5], arr2 = [5,6,7,8,9];// 交集let intersection = $(arr1).filter(arr2).toArray();// 并集let union = $.unique(arr1.concat(arr2))// 补集 两个数组各自没有的集合let complement = $(arr1).not(arr2).toArray().concat($(arr2).not(arr1).toArray())// 差集 数组arr1相对于arr2所没有的let diff = $(arr1).not(arr2).toArray()console.log('arr1: ', arr1);console.log('arr2: ', arr2);console.log('交集', intersection);console.log('并集', union);console.log('补集', complement);console.log('差集', diff);123456789101112131415161718192021
二、对象数组
// 形如如下数组let arr1 = [], arr2 = [];arr1 = [ { ID: 1, Name: 1, desc: 'Number' }, { ID: 2, Name: 2, desc: 'Number' }, { ID: 3, Name: 3, desc: 'Number' }, { ID: 4, Name: 4, desc: 'Number' }, { ID: 5, Name: 5, desc: 'Number' }]arr2 = [{ ID: 5, Name: 5, desc: 'Number' }, { ID: 6, Name: 6, desc: 'Number' }, { ID: 7, Name: 7, desc: 'Number' }, { ID: 8, Name: 8, desc: 'Number' }, { ID: 9, Name: 9, desc: 'Number' }]1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556// 交集let intersection = []for (let i = 0, len = arr1.length; i < len; i++) { for (let j = 0, length = arr2.length; j < length; j++) { if (arr1[i].ID === arr2[j].ID) { intersection.push(arr1[i]) } }}console.log('交集', intersection)// 并集let union = [...arr1, ...arr2]for (let i = 0, len = arr1.length; i < len; i++ ) { for (let j = 0, length = arr2.length; j < length; j++) { if (arr1[i].ID === arr2[j].ID) { union.splice(union.findIndex(item => item.ID === arr1[i].ID), 1) } }}console.log('并集', union)// 补集let complement = [...arr1, ...arr2]for (let i = 0, len = arr1.length; i < len; i++ ) { for (let j = 0, length = arr2.length; j < length; j++) { if (arr1[i].ID === arr2[j].ID) { complement.splice(complement.findIndex(item => item.ID === arr1[i].ID), 1) complement.splice(complement.findIndex(item => item.ID === arr2[j].ID), 1) } }}console.log('补集', complement)// 差集let diff = [...arr1]for (let i = 0, len = arr1.length; i < len; i++ ) { let flag = false for (let j = 0, length = arr2.length; j < length; j++) { if (arr1[i].ID === arr2[j].ID) { flag = true } } if (flag) { diff.splice(diff.findIndex(item => item.ID === arr1[i].ID), 1) }}console.log('差集', diff)
13、旋转数组
题目： 给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数。 输入：[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]
解题思路： 旋转数组实际上就是把数组的数字向后移动k位，末位的数字自动填充到前面的位置。
方法一： 可以看作是把后面的k位数字直接截取出来(this.slice(-k))，与前面的数字的数组(this.slice(0,this.length - k)拼接即可。
slice() 方法可从已有的数组中返回选定的元素。 slice() 参数使用负值则表示从数组的尾部选取元素。 slice()传start和end参数，则表示返回一个新的数组，包含从 start 到 end （不包括该元素）的 arrayObject 中的元素。 concat() 方法用于连接两个或多个数组。
function rotate(k) { if(k < 0 || k === 0 || k === this.length) { return this; } //旋转数组-方法1 return this.slice(-k).concat(this.slice(0,this.length - k));}Array.prototype.rotate = rotate;let arr = [1,2,3,4,5,6,7];console.log(arr.rotate(3));运行结果如图： 
方法二： 思路同方法1一样。使用扩展运算符…
splice() 方法向/从数组中添加/删除项目，然后返回被删除的项目。（该方法会改变原始数组) splice() 方法参数index，规定添加/删除项目的位置，使用负数可从数组结尾处规定位置。 扩展运算符… 把数组或类数组对象展开成一系列用逗号隔开的值
function rotate(k) { if(k < 0 || k === 0 || k === this.length) { return this; } //旋转数组-方法2 return [...this.splice(this.length - k),...this]}Array.prototype.rotate = rotate;let arr = [1,2,3,4,5,6,7];console.log(arr.rotate(3));运行结果如图
方法三： 遍历数组，执行k次删除数组的最后一个元素，并将返回的元素加在数组的头部。
备注： pop() 方法用于删除并返回数组的最后一个元素。 unshift() 方法可向数组的开头添加一个或更多元素，并返回新的长度。
function rotate(k) { if(k < 0 || k === 0 || k === this.length) { return this; } //旋转数组-方法3 for(let i = 0;i < k;i ++) { this.unshift(this.pop()); } return this;}Array.prototype.rotate = rotate;let arr = [1,2,3,4,5,6,7];console.log(arr.rotate(3));运行结果如图 
方法四： 创建一个k位的空数组，遍历空数组，删除原数组的最后一个元素，并将返回的元素加在数组的头部。(思路同方法3)
new Array(k).fill(’’)表示初始化一个长度为k的空数组，并用fill()传的指定的参数value填充空数组。
function rotate(k) { if(k < 0 || k === 0 || k === this.length) { return this; } //旋转数组-方法4 new Array(k).fill('').forEach(()=> { this.unshift(this.pop()); }) return this;}Array.prototype.rotate = rotate;let arr = [1,2,3,4,5,6,7];console.log(arr.rotate(3));运行结果如图
14、两数之和
题目如下：
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例
给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]
leetCood地址：两数之和
题目不难理解，首先一上来我们马上就能想到使用两个循环解决的办法。
遍历所有组合，找到符合要求的组合就行。
双层循环
代码如下：
const twoSum = (nums, target) => { let arr = []; for(let i = 0; i < nums.length; i++) { for(let j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] === target) { arr = [i, j]; break; } } } return arr;};两个循环，时间复杂度为O(N*N)。
leetCode测试数据如下：
我的提交执行用时已经战胜 17.42 % 的 javascript 提交记录
在第二个循环中，我们只是要寻找目标值是否在数组里，因此可想到javascript中的一个方法----indexOf。
indexOf 用法
代码可改写如下：
const twoSum = (nums, target) => { let a, b; for(let i = 0; i < nums.length; i++) { b = nums.indexOf(target - nums[i]); if(b > -1 && b !== i) { a = i; break; } } return [a, b];};但是 Array 的 indexOf 方法实际上是对数组再遍历一次，虽然在写法上有优化，但是实际时间复杂度还是O(N*N)。
在时间复杂度上做优化，我们需要解决一个问题，如何快速地在数组中检索值？使用 indexOf 其实已经在数据中检索特定值的思路上了。只不过 indexOf 内部还是对数组进行循环检索，因此并没有达到更快的要求。在这方面， hash表 可以帮助到我们。
什么意思呢？比如我们有一个对象 obj = { ..., a: 1} ，当我们取值 Obj.a 时，是个直接寻址的过程，因此效率是很高的。回到题目，在这个思路上改进我们的代码：
使用对象索引
const twoSum = (nums, target) => { let mapObj = {}; let res = []; nums.forEach((e, i) => mapObj[e] = i); for(let i=0;i<nums.length;i++) { let j = mapObj[targer - nums[i]]; if(j && j !== i) { res = [i, j]; break; } } return res;};我们创建一个对象，并给它赋值，对象的键值是我们想要检索的值，对象的值是在数组中的索引。
虽然多了创建对象这一过程，但是我们少了一层循环。
然后我们来看执行效率：
我的提交执行用时已经战胜 86.24 % 的 javascript 提交记录。
从 17.42 % 到 86.24 %，可以说是个质的飞跃。
es6 中，给我们提供了一个新对象 Map，在这里就可以拍上用途。
使用 map
const twoSum = (nums, target) => { let map = new Map(); let res = []; nums.forEach((e, i) => map.set(e, i)); for(let i=0;i<nums.length;i++) { let j = map.get[targer - nums[i]]; if(j && j !== i) { res = [i, j]; break; } } return res;};最终使用 Map 优化的代码，让我们战胜了 97.21 % 的提交。