前端面试中的算法题（一）

1.驼峰转下划线

function toLine(str) {
  return str.replace(/\B([A-Z])/g, '_$1').toLowerCase()
}

toLine('getInfoById')
// 'get_info_by_id'

toLine('GetInfoById')
// 'get_info_by_id'

2.下划线转驼峰

function toHump(str) {
  return str.replace(/\_(\w)/g, function(match, p1){
    return p1.toUpperCase()
  })
}

toHump('get_info_by_id')
// 'getInfoById'

3.金额的格式化处理之数字千分位逗号分隔

function format(num) {
  num = parseFloat(num).toFixed(2).toString()
  var integer = num.split('.')[0]
  var decimal = num.split('.')[1]
  
  var result = ''

  while (integer.length > 3) {
    result = ',' + integer.slice(-3) + result
    integer = integer.slice(0, integer.length - 3)
  }

  if (integer) {
    result = integer + result 
  }

  return result + '.' + decimal
}

format(399)
// '399.00'
format(3999)
// '3,999.00'
format(39999)
// '39,999.00'
format(3999999.98)
// '3,999,999.98'

也可以利用正则表达式实现：

function format(num) {
  num = parseFloat(num).toFixed(2).toString()
  return num.replace(/\B(?=(\d{3})+\.)/g, ',')
}

format(399)
// '399.00'
format(3999)
// '3,999.00'
format(39999)
// '39,999.00'
format(3999999.98)
// '3,999,999.98'

4.转换为树形结构

输入：

var data = [
  { id: 1, name: "办公管理", pid: 0 },
  { id: 2, name: "请假申请", pid: 1 },
  { id: 3, name: "出差申请", pid: 1 },
  { id: 4, name: "请假记录", pid: 2 },
  { id: 5, name: "系统设置", pid: 0 },
  { id: 6, name: "权限管理", pid: 5 },
  { id: 7, name: "用户角色", pid: 6 },
  { id: 8, name: "菜单设置", pid: 6 },
]

递归的实现方式：

function transform(list, pid = 0) {
  var result = []

  list.forEach(item => {
    if (item.pid === pid) {
      result.push(item)
      item.children = transform(list, item.id)
    }
  })

  return result
}

transform(data)

递归的实现方式每次都会遍历整个数据，考虑到性能问题的话，可以先将数据转换为字典结构使其能通过id来快速查询，这样只用一次遍历就能完成树形结构的转换：

function transform(list) {
  var tree = []
  var record = {}

  for (var i = 0, len = list.length; i < len; i++) {
    var item = list[i]
    var id = item.id

    if (record[id]) {
      item.children = record[id]
    } else {
      item.children = record[id] = []
    }

    if (item.pid) {
      if (!record[item.pid]) {
        record[item.pid] = []
      }

      record[item.pid].push(item)
    } else {
      tree.push(item)
    }
  }

  return tree
}

transform(data)

5.将嵌套的数组拉平

ES6 中新增了数组实例的flat()方法用于将嵌套的数组拉平，变成一维的数组，该方法返回一个新数组，对原数据没有影响。flat()默认只会拉平一层，如果想要拉平多层的嵌套数组，可以将flat()方法的参数写成一个整数，表示想要拉平的层数，默认为1。如果不管有多少层嵌套都要转成一维数组，可以用infinity关键字作为参数。

[1, 2, [3]].flat()
// [1, 2, 3]

[1, 2, [3, [4, 5]]].flat(2)
// [1, 2, 3, 4, 5]

[1, [2, [3]]].flat(Infinity)
// [1, 2, 3]

递归实现：

function flat(arr) {
  var result = []
  arr.forEach((val) => {
    if (val instanceof Array) {
      result = result.concat(flat(val))
    } else {
      result.push(val)
    }
  })
  return result
}

flat([1, 2, [3]])
// [1, 2, 3]

flat([1, [2, [3]]])
// [1, 2, 3]

6.数组乱序

function shuffle(arr) {
  var m = arr.length
  while (m > 1) {
    var index = Math.floor(Math.random() * m--)
    var temp = arr[m]
    arr[m] = arr[index]
    arr[index] = temp
  }
  return arr
}

shuffle([1, 2, 3, 4, 5, 6])
// [3, 2, 5, 6, 4, 1]

7.二叉树的最小深度

输入：

function Node(data, left, right) {
  this.data = data
  this.left = left
  this.right = right
}

// 根据二叉树前序遍历的结果数组生成二叉树
function createBinaryTree(list) {
  var node = null
  
  if (list.length === 0) {
    return null
  }

  var data = list.shift()
  if (data !== null) {
    node = new Node(data, createBinaryTree(list), createBinaryTree(list))
  }
  return node
}

var list = [3, 9, 20, null, null, 15, 7, null, null, null, 9, 2]
var binaryTree = createBinaryTree(list)

二叉树的最小深度是指从根节点到最近叶子节点的最短路径上的节点数量：

function minDepth(root) {
  if (root === null) {
    return 0
  } else if (root.left === null) {
    return minDepth(root.right) + 1
  } else if (root.right === null) {
    return minDepth(root.left) + 1
  } else {
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1
  }
}

minDepth(binaryTree)  // 3

8.数字字符串补零

ES6 中新增了字符串补全长度的方法，如果某个字符串不够指定长度，会在头部或尾部补全。padStart()用于头部补全，padEnd()用于尾部补全。

'1'.padStart(5, '0')  // '00001'

function padNumber(num, fill) {
  var len = ('' + num).length
  return (Array(fill > len ? fill - len + 1 : 0).join(0) + num)
}

padNumber(1, 5)  // '00001'

9.计算个人所得税

小明的公司每个月给小明发工资，假设他一个月的税前工资（扣除五险一金后、未扣税前的工资）为S元，则他应交的个人所得税按如下公式计算：
1）个人所得税起征点为3500元，若S不超过3500，则不交税，3500元以上的部分才计算个人所得税，令A=S-3500元；
2）A中不超过1500元的部分，税率3%；
3）A中超过1500元未超过4500元的部分，税率10%；
4）A中超过4500元未超过9000元的部分，税率20%；
5）A中超过9000元的部分，税率30%。
已知小明这个月税前工资为T，请问他应缴多少税？

function tax(salary) {
  if (salary > 0 && salary <= 3500) {
    return 0
  } else if (salary > 3500 && salary <= 5000) {
    return tax(3500) + (salary - 3500) * 0.03
  } else if (salary > 5000 && salary <= 8000) {
    return tax(5000) + (salary - 5000) * 0.1
  } else if (salary > 8000 && salary <= 12500) {
    return tax(8000) + (salary - 8000) * 0.2
  } else if (salary > 12500) {
    return tax(12500) + (salary - 12500) * 0.3
  }
}

tax(19000)  // 3195

上述的方法在税率区间增多的时候需要增加更多的条件判断语句，可以使用下面的方法进行优化：

function tax(salary) {
  var exceed = [0, 3500, 5000, 8000, 12500]
  var rate = [0, 0.03, 0.1, 0.2, 0.3]
  var result = 0
  for(var i = 0; i < exceed.length; i++){
     if(salary - exceed[i] <= 0) break
     if(exceed[i+1] && salary > exceed[i+1]){
       result += (exceed[i+1] - exceed[i]) * rate[i]
     }else{
       result += (salary - exceed[i]) * rate[i]
     }
  }
  return result
}

tax(19000)  // 3195

10.有序数组的查找

使用二分法查找：

function find(num, arr) {
  var leftIndex = 0
  var rightIndex = arr.length - 1

  while (leftIndex <= rightIndex) {
    mid = Math.floor((rightIndex + leftIndex) / 2)
    if (num === arr[mid]) {
      return mid
    } else if (num > arr[mid]) {
      leftIndex = mid + 1
    } else {
      rightIndex = mid - 1
    }
  }

  return -1
}

var arr = [1, 3, 6, 8, 11, 22, 88]
find(22, arr) // 5

---

参考文章：
1.「前端进阶」数组乱序