Skip to content

Latest commit

 

History

History
344 lines (308 loc) · 7.99 KB

前端常见算法题.md

File metadata and controls

344 lines (308 loc) · 7.99 KB

一、函数求和

要求写一个sum函数,实现如下功能(提示:涉及到JavaScript精度丢失问题):

sum(1,2,3,4)       // 输出 10
sum(5,null,-5)     // 输出 0
sum(0.2,0.3)       // 输出 0.5
sum('1.0', false, 1, true, 1, 'A', 1, 'B', 1, 'C', 'D', 1, 'E', 1, 'F', 1, 'G')  // 输出 9

解决方法:

function sum() {
    var arg = [].slice.call(arguments) //将具有length属性的对象转成数组
    var sum = arg.reduce((prev, next) => {
        if (isNaN(next)) { //如果是非法数字返回true
            return prev
        }
        var pointprev = prev.toString().split('.')[1] ? prev.toString().split('.')[1].length : 0
        var pointnext = next.toString().split('.')[1] ? next.toString().split('.')[1].length : 0
        times = Math.pow(10, Math.max(pointprev, pointnext))
        return (prev * times + next * times) / times
    })
    return sum
}

补充:

 产生精度丢失的原因:计算机执行的是二进制算术,当十进制转换二进制时,出现精度误差。
 解决办法:(1)对于整数只要计算结果不超过Math.pow(2,25)就不会丢失精度
          (2)对于小数,把小数放大小数位数 * 10 倍数,在缩小同样的倍数,使用 Math.pow() 方法

二、判断对象是否为空

function isEmptyObject(obj){
    for(var key in obj){
        return false
    }
    return true
}

三、求add(1)(2)(3),其中调用次数未限定

//在function前面加上+号时,就变成了一个函数表达式
console.log(+add(1, 2)(3)); //6
console.log(+add(1)(2)(3)(4)); //10
function add() {
    var sum = 0;
    var arr = [].slice.call(arguments);
    sum = arr.reduce((prev, next) => {
        return prev + next;
    })
    var tmp = function() {
        var arr = [].slice.call(arguments);
        var total = arr.reduce((prev, next) => {
            return prev + next;
        });
        sum = sum + total;
        return tmp;
    };
    tmp.valueOf = function() {
        return sum;
    };
    return tmp;
}

四、判断一个单词是否是回文

function checkPalindrom(str){
    return str == str.split('').reverse().join('')
}

五、获取 100 以内的质数

console.log(prime(1000))

function prime(n) {
    var arr = [];
    for (var i = 2; i < n; i++) {
        for (var j = 2; j < Math.sqrt(i); j++) {
            if (i % j === 0) {
                break;
            }
        }
        if (j > Math.sqrt(i)) {
            arr.push(i);
        }
    }
    return arr;
}

六、3sum 问题

function sum(nums) {
  var result = []
  nums.sort(sortNumber)
  for (var i = 0; i < nums.length; i++) {
    var m = i + 1
    var j = nums.length - 1
    while (m < j) {
      var sum = nums[i] + nums[m] + nums[j]
      if (sum > 0) {
        j--
      }
      if (sum === 0) {
        var temp = [nums[i], nums[m], nums[j]]
        result.push(JSON.stringify(temp))
        j--
      }
      if (sum < 0) {
        j = nums.length - 1
        m++
      }
    }
  }
  var tempArr = []
  var oSet = new Set(result)
  for(var x of oSet){
    tempArr.push(JSON.parse(x))
  }
   return tempArr;
}

function sortNumber(a, b) {
  return a - b
}

七、将数组中的元素随机移入b中

var a = [7, 47, 5, 12, 3, 8, 18]
var b = []
var num = a.length - 1
console.log(out(a))

function out(a) {
    var set1 = new Set()
    while (set1.size < num) {
        var index = Math.round(Math.random() * num)
        if (!set1.has(a[index]) && index < a.length) {
            b.push(a[index])
            set1.add(a[index], 0)
            a.splice(index, 1)
        }
    }
    return b
}

八、不借助临时变量,交换两个数据

console.log(swap(3, 4))

//1.加减法
function swap(a, b) {
  b = b - a
  a = a + b
  b = a - b
  return [a, b]
}

//2.ES6 的解构赋值
var a= 3,b=4
var {a,b} = {b,a}

九、找出下列数组的最大差值

function maxValue(arr) {
  arr.sort(function (a, b) {
    return a - b
  })
  return (arr[arr.length-1] - arr[0])
}

十、数组去重

   //ES 6
    var arr1 = ['d', '1', 2, '1', 'dd', '1', 'he', 'd']
    var arr2 = [
        [0, 0, 0],
        [0, 0, 0]
    ]
    console.log(unique2(arr2))

    function unique1(arr) {
        let map = new Map()
        console.log(map)
        return arr.filter(a =>
            !map.has(a) && map.set(a, 0) //返回map中没有该键的项,没有该键时把他放到Map中
        )
    }

    function unique2(arr) {
        return Array.from(new Set(arr))
    }
    //去重,不考虑元素顺序
    //在使用sort()进行排序的时候会调用toString()函数将其值转换成字符串在进行比较,是按ASCII进行比较的,所以不适用数组中有不同类型的元素
    function unique3(arr) {
        arr.sort()
        console.log(arr);
        let newArr = [arr[0]]
        for (var i = 1; i < arr.length; i++) {
            console.log('i:' + i + '——' + 'newArr.length:' + newArr.length)
            if (arr[i] !== newArr[newArr.length - 1]) {
                newArr.push(arr[i])
            }
        }
        return newArr
    }

    function unique4(arr) {
        var newarr = []
        for (var i = 0; i < arr.length; i++) {
            if (newarr.indexOf(arr[i]) === -1) {
                newarr.push(arr[i])
            }
        }
        console.log(newarr)
        return newarr
    }


    function unique5(arr) {
        var newarr = []
        var obj = {}
        for (var i = 0; i < arr.length; i++) {
            var type = typeof arr[i]
            console.log(type)
            if (!obj[arr[i]]) { //如果对象中没有该键
                obj[arr[i]] = [type];
                newarr.push(arr[i])
            } else if (obj[arr[i]].indexOf(type) < 0) {
                obj[arr[i]].push(type);
                newarr.push(arr[i]);
            }
        }
        console.log(newarr)
        console.log(obj)
        return newarr
    }

    //获取没重复的最右一值放入新数组。(检测到有重复值时终止当前循环同时进入顶层循环的下一轮判断)推荐
    function unique6(array) {
        var r = [];
        for (var i = 0; i < array.length; i++) {
            for (var j = i + 1; j < array.length; j++) {
                console.log('不相等' + j);
                console.log('i' + i)
                if (array[i] === array[j]) {
                    j = ++i;
                    console.log('相等' + j);
                }
            }
            console.log(array[i])
            r.push(array[i]);
        }
        console.log(r)
        return r;
    }

十一、冒泡排序

var arr = [3, 1, 4, 3, 2, 7, 6]

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

十二、给一个字符串,找出出现次数最多的元素

function theMost(arr) {
  var total = {}
  if (arr.length == 0) {
    return
  }
  var element = arr.charAt(0)  // 返回指定位置的字符
  var maxCount = 1
  for (var i = 0; i < arr.length; i++) {
    var key = arr.charAt(i) + ""
    if (total.hasOwnProperty(key)) {
      total[key]++
    } else {
      total[key] = 1
    }
    if (total[key] > maxCount) {
      maxCount = total[key]
      element = key
    }
  }
  return element
}

十三、找出下列正数组的最大差值

输入 [10,5,11,7,8,9]

输出 6
function getMax(arr) {
  var max = Math.max.apply(null, arr)
  var min = Math.min.apply(null, arr)
  var temp = Number(max) - Number(min)
  return temp
}

十四、随机生成指定长度的字符串

function randomString(n) {
  let str = 'abcdefghijklmnopqrstuvwxyz9876543210'
  let length = str.length
  let result = ''
  for (let i = 0; i < n; i++) {
    result = result + str.charAt(Math.round(Math.random() * length))
  }
  return result
}

十五、两道算法