面试的一些 JavaScript 算法

面试题

排序算法

• 冒泡排序

const arr = [16, 31, 12, 1, 9, 23, 10]
function bubbleSort (arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j+1])
        // 为了避免引入一个中间变量
        // 这里用了 ES6 的结构赋值
        [ arr[j], arr[j+1] ] = [ arr[j+1], arr[j] ]
    }
  }
  return arr
}
bubbleSort(arr) // [1, 9, 10, 12, 16, 23, 31]

• 快速排序

const arr = [16, 31, 12, 1, 9, 23, 10]
function quickSort (arr) {
  if (arr.length <= 1) return arr
  const middleIndex = Math.floor(arr.length / 2)
  const middle = arr.splice(middleIndex, 1)
  const left = []
  const right = []
  arr.forEach(v => {
    if (v < middle[0]) left.push(v)
    else right.push(v)
  })
  return quickSort(left).concat(middle, quickSort(right))
}
quickSort(arr) // [1, 9, 10, 12, 16, 23, 31]

• 不指定算法的数组排序

   // 从小到大
  const arr = [16, 31, 12, 1, 9, 23, 10]
  // 这里用了箭头函数，写起来比较短
  arr.sort((a, b) => a - b)
  // 从大到小
  const arr = [16, 31, 12, 1, 9, 23, 10]
  arr.sort((a, b) => b - a)

找出整型数组中乘积最大的三个数

const unsortedArray = [-10, 7, 29, 30, 5, -10, -70]
// 乘积最大的只有可能是两种情况：
// 1. 最大的三个数的乘积
// 2. 最大的数和最小的两个数的乘积
function multiply (unsortedArr) {
  // 从小到大排序
  const arr = unsortedArr.sort((a, b) => a - b)
  const length = arr.length
  // 计算两种情况的值
  result1 = arr[length - 1] * arr[length - 2] * arr[length - 3]
  result2 = arr[0] * arr[1] * arr[length - 1]
  return result1 > result2 ? result1 : result2
}
multiply(unsortedArray) // 21000

数组去重

给定某无序数组，要求去除数组中的重复数字并且返回新的无重复数组。

const arr = [1, 2, '1', null, undefined, null, undefined]
// ES6 Set 和 Spread 操作符
function uniqueArray (arr) {
  return [...new Set(arr)]
}
// ES5
function uniqueArray (arr) {
  return arr.filter((v, i) => arr.indexOf(v) === i)
}
uniqueArray(arr) // [1, 2, '1', null, undefined]

回文字符串的判定

function isPalindrome(word) {
  return word === word.split('').reverse().join('')
}
isPalindrome('racecar') // true

函数柯里化

此处输入链接的描述

function sum() {
  var num = arguments[0];
  console.log(num)
  if(arguments.length === 2) {
    return arguments[0] + arguments[1]
  } else {
    return function(sec) {
       return num + sec;
    }
  }
}

斐波那契数列(1,1,2,3,5,8)

//第n项对应的数值。
function com(n) {
  if (n <= 0) return 0;
  if (n == 1) return 1;
  return com(n - 1) + com(n - 2);
}
//前n项之和。
function sum(n) {
  if (n == 1) return 1;
  if (n < 1) return 0;
  return com(n) + sum(n -1);
}

深拷贝

function deepClone(initalObj, finalObj) {    
  var obj = finalObj || {};    
  for (var i in initalObj) {        
    if (typeof initalObj[i] === 'object') {
      obj[i] = (initalObj[i].constructor === Array) ? [] : {};            
      arguments.callee(initalObj[i], obj[i]);
    } else {
      obj[i] = initalObj[i];
    }
  }    
  return obj;
}
var str = {};
var obj = { a: {a: "hello", b: 21} };
deepClone(obj, str);
console.log(str.a);
--------------
function deepClone(initalObj, finalObj) {    
  var obj = finalObj || {};    
  for (var i in initalObj) {        
    var prop = initalObj[i];        // 避免相互引用对象导致死循环，如initalObj.a = initalObj的情况
    if(prop === obj) {            
      continue;
    }        
    if (typeof prop === 'object') {
      obj[i] = (prop.constructor === Array) ? [] : {};            
      arguments.callee(prop, obj[i]);
    } else {
      obj[i] = prop;
    }
  }    
  return obj;
}
var str = {};
var obj = { a: {a: "hello", b: 21} };
deepClone(obj, str);
console.log(str.a);