2021前端社招面试总结之算法篇

首次前端社招经验总结，大概分算法篇、编程篇、前端技术篇三部分。本次是算法篇的内容。

前言

对于前端来说，算法在面试中所占比例不是很高，题目难度也不是特别大，大部分属于 leetcode 简单题、中等题偏简单题目。对于社招前端而言，手写代码还是以考察实际项目编程为主，这个我们后续再讲。

考察范围也主要以数组、字符串、树为主。在我的面试过程中，也只遇到过一次动态规划类型的题目。

所以大家在准备过程中，针对性的做一些数组、字符串、二叉树的简单、中等题目即可。没有学过动态规划的，可以暂时放弃这部分，免得浪费面试准备时间。

面试过程中遇到的算法题

数组

1. 给定一个多重嵌套数组，拍平并去重 (难度：简单)

const arr = [
  [3, 9, 2, 4],
  [99, 32, 5, 7, 3],
  [6, 3, 12, 45, 9, [11, 8, [22, 15, 313, [44]]]],
  10,
  [99, 32],
]
// 方法1
function flatAndNoRepeat(arr) {
  const res = []
  function innerFunc(arr) {
    for (let item of arr) {
      // 先判断item是否为数组
      if (Array.isArray(item)) {
        // 数组的话，递归调用innerFunc方法
        innerFunc(item)
      } else if (!res.includes(item)) {
        // 非数组，则判断res中是否已包含该item。不包含则加入
        res.push(item)
      }
    }
  }
  return res
}
// 方法2 把res由数组换成set
function flatAndNoRepeat(arr) {
  const res = new Set()
  function innerFunc(arr) {
    for (let item of arr) {
      if (Array.isArray(item)) {
        innerFunc(item)
      } else {
        res.add(item)
      }
    }
  }
  return [...res]
}

tips: 数组去重的小技巧

const arr = [10, 10, 20, 30, 34, 30]
const res = [...new Set(arr)] // [10,20,30,34]

2. 将两个有序数组合并成一个有序数组 (难度：简单)

- 将两个有序数组合并成一个有序数组
- @param {number[]} A 有序数组 A
- @param {number[]} B 有序数组 B
- @returns {numbers[]} 合并后的有序数组
- @example
- const A = [1,2,7,8];
- const B = [3,4,5,6];
- mergeSorted(A, B); // 返回 [1,2,3,4,5,6,7,8]

function mergeSorted(A, B) {
  const res = [];
  const aLen = A.length;
  const bLen = B.length;
  let aindex = 0, bindex = 0;
  // 取A、B中小的数值，放入res数组中
  while(aindex < aLen && bindex < bLen) {
    if (A[aindex] <= B[bindex]) {
      res.push(A[aindex]);
      aindex++;
    }else {
      res.push(B[bindex]);
      bindex++;
    }
  }

  // 如果A或者B中还有剩余值，则依次加入到res数组中
  while(aindex < aLen) {
    res.push(A[aindex]);
    aindex++;
  }

  while(bindex < bLen) {
    res.push(B[bindex]);
    bindex++;
  }

  return res;
}

3. 给定一个数据结构 A，转成树形结构 B (难度：中等)

const A = [
  {id: 2, parentId: 1},
  {id: 1},
  {id: 3, parentId: 2},
  {id: 5, parentId: 4},
  {id: 4},
]

const B = [
  {id: 1, child: [{id: 2, parentId: 1, child: [{id: 3, parentId: 2}]}]},
  {id: 4, child: [{id: 5, parentId: 4}]},
]

function parseTree(A) {
  const res = {}
  const root = Symbol(0)
  A.forEach((item) => {
    const {id, parentId} = item
    if (!res[id]) {
      res[id] = {...item, child: []}
    } else {
      res[id] = {...res[id], ...item}
    }

    // 给没有parentId的id一个父节点 
    const parent = parentId || root
    if (!res[parent]) {
      res[parent] = {id: parent, child: [res[id]]}
    } else {
      // 因为push的是res[id]引用类型，所以res[id]变化，res[parent].child的内容自然也会变化
      res[parent].child.push(res[id])
    }
  })
  return res[root].child
}

字符串

1. 实现字符串中单词按数字顺序从小到大排序，比如：(难度：简单)

‘ac23dd rf5 8ee’ -> ‘rf5 8ee ac23dd’

function sortByNum(str) {
  // 取出各个单词中的数字部分
  function getNum(string) {
    let num = 0
    for (let char of string) {
      if (/\d/.test(char)) {
        num = num * 10 + Number(char)
      }
    }
    return num
  }

  // 按空格划分单词数组
  const arr = str.split(' ')
  // 数组按数字大小排序
  arr.sort((a, b) => getNum(a) - getNum(b))
  return arr.join(' ')
}

2. 把数字12345转换成千位分隔符方式12,345 (难度：简单)

// 方法1，从后往前排，3个一组，加逗号
function parseNum(number) {
  let res = ''
  let count = 1
  for (let i = number.length - 1; i > 0; i--) {
    res = number[i] + res
    if (count % 3 === 0) {
      res = ',' + res
    }
    count++
  }
  res = number[0] + res
  return res
}

// 方法2：正则表达式
function parseNum(number) {
  // 非首位，后续是连续3个数字的位置，变成','
  return str.replace(/(?!^)(?=(\d{3})+$)/g, ',')
}

3. 给定两个字符串 str1 和 str2，输出两个字符串的最长公共子序列。如过最长公共子序列为空，则输出-1 (难度：中等)

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

输入
“1A2C3D4B56”,”B1D23CA45B6A”
输出
“123456”
说明
“123456”和“12C4B6”都是最长公共子序列，任意输出一个。

// 动态规划
function longestCommonSubsequence(str1, str2) {
  const len1 = str1.length
  const len2 = str2.length

  const dp = new Array(len1 + 1).fill(0).map(() => new Array(len2 + 1).fill(0))

  // dp[i][j]表示str1[0, i] str2[0, j]的最长公共子序列的长度
  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1
      } else {
        dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])
      }
    }
  }

  // 求公共子序列
  let res = ''
  for (let i = len1, j = len2; dp[i][j] > 0; ) {
    if (str1[i - 1] === str2[j - 1]) {
      res = str1[i - 1] + res
      i--
      j--
    } else if (dp[i - 1][j] >= dp[i][j - 1]) {
      i--
    } else {
      j--
    }
  }
  return res === '' ? -1 : res
}

扩展题目

二叉树

1. 找出二叉树中某两个节点的第一个共同祖先，不得将其他的节点存储在另外的数据结构中。 (难度：中等)

function findCommonAncestor(root, nodeA, nodeB) {
  if (!root || root === nodeA || root === nodeB) return root
  const lnode = findCommonAncestor(root.left, nodeA, nodeB)
  const rnode = findCommonAncestor(root.right, nodeA, nodeB)
  if (!lnode) return rnode
  if (!rnode) return lnode
  return root // p、q分列左右子树上，则root为最近父节点
}

2. 二叉树的广度优先遍历 (难度：中等)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
function bfs(root) {
  if (!root || root.length) return []

  const queue = []
  const res = []

  queue.push(root)
  // 队列用来按层载入数据
  while (queue.length) {
    // 获取该层所有数据个数
    let len = queue.length
    const arr = []
    while (len) {
      // 吐出该层所有node
      const node = queue.shift()
      arr.push(node.val)
      node.left && queue.push(node.left)
      node.right && queue.push(node.right)
      len--
    }
    res.push(arr)
  }
  return res
}

其他

1. 随机从数组中取 5 个人，每次都跟前一次不一样 (难度：简单)

function randomPick(arr, count) {
  const len = arr.length
  let res = []
  let preItem = null
  for (let i = 0; i < count; ) {
    // 获取[0, len)的随机数
    const index = Math.floor(Math.random() * len)
    const curItem = arr[index]
    if (!res.includes(curItem) && preItem !== curItem) {
      res.push(curItem)
      preItem = curItem
      i++
    }
  }
  return res
}

2. 给你一个字符串表达式 s (3 + 2) / 4 * 5，请你实现一个基本计算器来计算并返回它的值。 (难度：困难)

此题为 leetcode 会员解锁，解题思路可参考这里

// nums存放数字
let nums = []
// opts存放运算符
let opts = []

// 运算符权重
const optweight = {
  '*': 2,
  '/': 2,
  '+': 1,
  '-': 1,
}
var calculate = function (s) {
  nums = []
  opts = []
  nums.push(0) // 防止第一个数为负数时的异常
  s = s.replaceAll(' ', '')
  let num = 0
  const len = s.length
  for (let i = 0; i < len; ) {
    const item = s[i]
    if (/\d/.test(item)) {
      // 在这里计算当前所有数字内容，放入nums数组中
      while (/\d/.test(s[i])) {
        num = 10 * num + Number(s[i])
        i++
      }
      nums.push(num)
      num = 0
    } else {
      switch (item) {
        case '(':
          opts.push(item)
          break
        case ')': {
          while (opts.length) {
            // 取左括号后的所有运算符，进行运算
            if (opts[opts.length - 1] !== '(') {
              cal()
            } else {
              // 吐出左括号，退出循环
              opts.pop()
              break
            }
          }
          break
        }
        case '+':
        case '-':
        case '*':
        case '/': {
          // 如果上一个字符也是符号，如+-3，则给nums加个0
          if (i > 0 && ['(', '+', '-'].includes(s[i - 1])) {
            nums.push(0)
          }
          // 如果运算符数组中有运算符，且最后一个运算符不是左括号
          while (opts.length && opts[opts.length - 1] !== '(') {
            // 如果opts内的最后一个运算符权重比当前运算符大，则要先计算里面的
            if (optweight[opts[opts.length - 1]] >= optweight[item]) {
              cal()
            } else {
              break
            }
          }
          opts.push(item)
          break
        }
        default:
          break
      }
      i++
    }
  }
  while (opts.length) {
    cal()
  }
  return nums.reduce((pre, cur) => pre + cur)
}

function cal() {
  // 没有两个以上数字，不计算
  if (nums.length < 2) return

  let res = 0
  // 取出nums中最后两个数字，opts中最后一个运算符，进行计算
  const a = nums.pop()
  const b = nums.pop()
  switch (opts.pop()) {
    case '+':
      res = a + b
      break
    case '-':
      res = b - a
      break
    case '*':
      res = a * b
      break
    case '/':
      res = (b / a) | 0
      break
    default:
      break
  }
  nums.push(res)
}

tips: 题目有点难，可以先完成这两道题基本计算器和基本计算器 II做练习

3. 顺时针打印矩阵 (难度：简单)

const arr = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
]

// N * N
// 扁平化输出、顺时针向内打印
// out put [1,2,3,6,9,8,7,4,5]

function flat(arr) {
  const res = []
  const len = arr.length
  const n = arr[0].length

  let index = 0

  while (res.length < len * n) {
    // 找规律
    for (let i = index; i < len - index; i++) {
      res.push(arr[index][i])
    }
    for (let i = index + 1; i < n - index; i++) {
      res.push(arr[i][len - index - 1])
    }
    for (let i = len - index - 2; i >= index; i--) {
      res.push(arr[len - index - 1][i])
    }
    for (let i = n - index - 2; i > index; i--) {
      res.push(arr[i][index])
    }
    index++
  }
  return res
}

扩展题目

4. 判断一个点是否在三角形内部 (难度：中等)

该题主要用到数学知识