前端算法题.md

前段算法题汇总

前言：尝试自己根据思路去使用js实现的算法，发现对于算法有这么几个问题：

  • 算法是严谨的，一般都是设计到循环，所以要思考到循环中的特殊情况以及循环条件。
  • 不能钻牛角尖，无从下笔时，在纸上写思路，根据思路一步一步实现，在实现的过程中，如果遇到问题，不要慌忙推翻之前的思路，细想之后再改善，大的思路如果不是有很大的问题，先不要推翻，不然很容易陷入到取舍两难的境地。
  • 注意算法的调试方法，尤其是输出，断点的灵活应用。

1、数组去重

数组去重的几种方法请参照数组操作方法

2、js脚本整理文件

整理前：

1
2
3
4
111.232.213 ascqwdwd
111.232.213 qwdqwdqw
122.31.34.1 wdojqwodjqwp  
232.34.13.3 adhwdhwqhd

整理后：

1
2
3
'111.232.213': [ 'ascqwdwd', 'qwdqwdqw' ],
'122.31.34.1': [ 'wdojqwodjqwp' ],
'232.34.13.3': [ 'adhwdhwqhd' ]

3、求1000以内所有的质数

对于求质数，和判断一个数是不是质数，原理是一样，区别在于求质数是对一群数进行判断，复杂度提高，如果只是判断一个数是不是质数，不要考虑复杂度，直接从2到这个数的平方根开始循环看能不能整除。
对于求多少以内的质数，也可以这样，但是这样的时间复杂度就提高了，网上有说几种不同的境界，这里就不介绍，我才用的筛选法，很明显，对于明显不是质数的数，没有做运算，节省的时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/** 求num中所有质数
 * 对比各种求质数的算法，试除法、筛选法两种时间复杂度较低，
 * 本方法是自己优化的筛选法，因为2,3是比较小的两个质数，大部分数都是他们的倍数，明显不是质数，
 * 所以使用2,3为基数，先筛选走这些非质数，然后在从5 7等向上筛选，这种方法明显循环次数要少。时间复杂度我也不知道该怎么计算。
 * **/
function prime(num) {
    //定义基数数组baseArr，用来存放较小的质数，res存放筛选结果，base存放[2,3]
    let baseArr = [], res = [], base = [];
    num = ~~num;  //取整
    //对2,3 特殊对待
    if (num < 4) {
        if (num === 1)
            alert('请输入大于1的整数')
        if (num === 2)
            base.push(2);
        else
            base.push(2, 3)
    }
    //筛选剩下的
    else {
        baseArr.push(2, 3);
        base.push(2, 3);
        for (let i = 2; i <= num; i++) {  //将2,3的倍数剔除，其余的放入res进行下一轮筛选
            if (i % 2 !== 0 && i % 3 !== 0) {
                res.push(i);
            }
        }
        for (let j = 0; j <= baseArr.length - 1; j++) {  //以大于3最小的质数开始筛选，
            for (let i = 1; i < res.length; i++) {
                if (res[i] % res[j] === 0 && i !== j) {  //除自身外，其他的是质数的倍数的数被剔除
                    res.splice(i, 1);
                }
            }
            if (res[j] < Math.sqrt(num)) {  //确保基数质数肯定小于sqrt(num)
                baseArr.push(res[j]);   //添加一个新的基数质数。
            }
        }
    }
    return base.concat(res)  //将特殊的[2,3]加入返回。
}
console.log(prime(100));
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
// baseArr = [2,3,5,7]

4、不借助临时变量，进行两个整数的交换

1
2
3
4
5
6
function exchange(a,b){
    b=a-b;
    a=a-b;
    b=a+b;
    return [a,b]
}

5、找出数组最大的差值

1
2
3
4
function maxDiff(array) {
    return Math.max.apply(array,array) - Math.min.apply(array,array);
}
console.log(maxDiff(arr));

6、