JavaScript进阶：手写代码挑战(四)

时间：02-21来源：作者：点击数：13

在现代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地址：两数之和（Link:https://leetcode-cn.com/problems/two-sum/）

题目不难理解，首先一上来我们马上就能想到使用两个循环解决的办法。

遍历所有组合，找到符合要求的组合就行。

双层循环

代码如下：

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;
};