常见面试算法题

算法常常被拿来考察程序员的编程功底，即便是前端，找工作的时候一些大厂也会出几道算法题来刁难一下你，毕竟好的工作资源相对较少，想要从一众求职者中脱颖而出，只掌握了大家都会的技能是不够的。面试官要从应聘者中挑出最优秀的人，也就要用更难的题来筛选。所以即使前端用到算法的地方屈指可数，想要提升自己，得到更好的机会，就得去学习更底层的知识。

持续更新。。。

大数相加

描述

对于两个超过了JS安全范围的整数，用加法求和并不能得到准确的结果，现在希望写一种方式能够对两个超过了JS安全范围的整数求和得到准确的结果。

思路

将大数保存到两个数组中，然后按位从底到高依次累加进位，将每一位的计算结果保存到一个新的数组中，一开始根据自己的理解实现了一个版本，数组迭代都用的索引，写起来繁琐，而且极其容易出错，代码如下：

function addbig(a,b){
  let arrA = Array.from(a+“”);
  let arrB = Array.from(b+“”);
  let la = arrA.length;
  let lb = arrB.length;
  let lm = Math.max(la,lb);
  let delta = 0;
  let result = [];
  for(var i = 0;i<lm;i++){
    var a = getItem(arrA,i);
    var b = getItem(arrB,i);
    var sum = a + b + delta;
    result[lm-1-i] = sum<10?sum:sum-10;
    delta = sum<10?0:1;
  }
  if(delta>0){
    result.unshift(1);
  }
  return Number.parseInt(result.join(''));
}
function getItem(arr,index){
  let n = arr.length;
  if(index < n){
    return Number.parseInt(arr[n-1-index])
  }
  return 0;
}

后来使用 JavaScript Array 原生接口来代替一些循环迭代，用 + 操作符代替parseInt的类型转换，巧用 / 和 % 运算符来取整和求余，优化后的代码只剩不到二十行，简洁清晰

function addbig(a,b){
  let arrA = Array.from(a.toString());
  let arrB = Array.from(b.toString());
  let i = Math.max(arrA.length,arrB.length);
  let delta = 0;
  let result = [];
  while(i>0){
    var sum = (+arrA.pop() || 0) + (+arrB.pop()||0) + delta;
    result.unshift(sum % 10);
    delta = parseInt(sum/10);
    i--;
  }
  if(delta){
    result.unshift(delta);
  }
  return +result.join('');
}

再次优化，将取两个数值字符串中最大长度变成取最小长度，可以减少遍历次数

function addbig(a,b){
  let arrA = Array.from(a.toString());
  let arrB = Array.from(b.toString());
  let i = Math.min(arrA.length,arrB.length);
  let delta = 0;
  let result = [];
  while(i--){
    var sum = (+arrA.pop() || 0) + (+arrB.pop()||0) + delta;
    result.unshift(sum % 10);
    delta = parseInt(sum/10);
  }
  result.unshift(+arrA.join('') || +arrB.join('')+delta);
  return +result.join('');
}