javascript 算法 面试题1

1.数组排序，写一个冒泡排序，会吗？
原理：遍历数组每一项与数组剩余项目比较，然后进行后续逻辑操作

var arr1 = [1,8,8123,1881,54,613,14];
function bubbleSort(arr){
    for(var i=0; i<arr.length; i++){ 
      for(var j=0; j<arr.length-i; j++){
        if(arr[j]>arr[j+1]){
          var temp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = temp;
        }
      }
    }
    return arr; 
}
console.log(bubbleSort(arr1));  //[ 1, 8, 14, 54, 613, 1881, 8123 ]

2.数组排序，写一个快速排序，会吗？
原理：抽出数组的中间一项，做参照对象，大的放其右侧，反之放其左侧；然后对这个逻辑进行递归

var arr1 = [1,8,8123,1881,54,613,14];
function quickSort(arr){
    if(arr.length<2){ return arr; };
    var midIndex = Math.floor(arr.length/2);
    var midVal = arr.splice(midIndex,1)[0];
    var lArr = [];
    var rArr = [];

    for(var i=0; i<arr.length; i++){
        if(arr[i]>midVal){
            rArr.push(arr[i]);
        }else{
            lArr.push(arr[i]);
        }
    }

    return quickSort(lArr).concat(midVal,quickSort(rArr));
}
console.log(quickSort(arr1));

快速排序优化版本

function bubbleSort (arr) {
  for (let i = 0; i < arr.length; i++) {
    let flag = true;
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        flag = false;
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
    if (flag) break;
  }
  return arr;
}

3.递归是什么，组成部分有什么呢？
递归是一个函数，其内部执行自身
递归包含：边界条件、递归返回段、递归前进段

4.写一个100加和的递归，如何？

var res = 0;
function addfn(num){
    if(num>100){ return res; } //边界条件，递归返回段
    res+=num;
    num++;
    return addfn(num); //递归前进段
}
console.log(addfn(0)); //初始值0 ; 返回结果5050

5.显示当前网页中使用的标签数量和种类，会吗？

var allEle = document.getElementsByTagName('*');
var tagArr = Array.from(allEle).map(item=>{ return item.tagName })
var resArr = new Set([...tagArr]);
console.log(resArr.size); //数量
console.log(Array.from(resArr).join(',')); //种类

5.穷举法写一个函数，计算1-100之间的素数，会吗？
穷举法（穷举法也称为枚举法）
穷举法的基本思想是根据题目的部分条件确定答案的大致范围，
并在此范围内对所有可能的情况逐一验证，直到全部情况验证完毕。
若某个情况验证符合题目的全部条件，则为本问题的一个解；
若全部情况验证后都不符合题目的全部条件，则本题无解。

质数（素数）
指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。

答：

function findNum(lth){
    var lth = lth || 100; //默认查找100以内质数
    var res = [];
    for(var i=1; i<=lth; i++){
        var tempNum = 0;
        for(var j=1; j<=lth; j++){
            if(i%j==0){
                tempNum++;
            }
        }
        if(tempNum == 2){  //能整除，要么整除1，要么整除自己
            res.push(i);
        }
    }
    return res;
};
console.log(findNum());

5-2.同样是算法题，一个三位数，个位大于百位，百位大于十位，且组成这个三位数的三个数字，相加结果与相乘结果想用，求这个三位数是什么，会吗？

function findNum(){
    //console.time("test")
    var time1 = (new Date()).getTime();
    var res = [];
    var num = 0;
    for(var x=0; x<=9; x++){
        for(var y=0; y<=7; y++){
            for(var z=0; z<=8; z++){
                if((x+y+z)==x*y*z && x>z && z>y){
                    res.push(z*100 + 10*y + x);
                }
                num++;
            }
        }
    }
    //console.timeEnd("test")
    var time2 = (new Date()).getTime();
    console.log(`计算了${num}次,计算${time2-time1}毫秒`);
    return res;
};
console.log(findNum());