在现代Web开发中，JavaScript 是不可或缺的编程语言。掌握其核心功能和原理对于开发者至关重要。本文通过手写实现JavaScript的一些关键功能和算法，帮助读者深入理解其工作原理，提升编程技能。无论你是初学者还是有经验的开发者，都能从中受益
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/False
let 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/False
let 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/False
let 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/False
let 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 % 的提交。
