前言

最近陆陆续续面了一些科技大厂与量化交易公司的前端实习岗位，可能个人运气比较好大厂的算法考的其实还算一般，都是比较常见的题，但是量化交易公司的题上来就是王炸，不过也确实应该，不然人家工资靠那么高干嘛，要求严格点不过分。

话不多说，上题：

美团一面

美团一面给了两道题选择一道题作答即可，分别是：

1. 20. 有效的括号 - 力扣（LeetCode）2. 937. 重新排列日志文件 - 力扣（LeetCode）

先来看第一题：

这道题非常非常非常基础，如果现在还解不出来但想去大厂的友友建议先看一下数据结构在去刷算法。这道题最好的解法就是调用栈，简单高效。

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
      var stack = [];   //创建一个执行栈
      for(var i = 0; i < s.length; i++){   //遍历字符串
        if(s[i] == '(' ){         //遇到"(","{","["则push入栈对应的闭括号入栈
          stack.push(')');
        }else if(s[i] == '{'){
          stack.push('}');
        }else if( s[i] == '['){
          stack.push(']');
        }else{                    //进入了else内的括号只是")","}","]"
          if(stack.length == 0){              //栈内为空，则没有匹配到的括号，返回false
            return false;
          }
          if(s[i] ==  stack[stack.length - 1]){       //计较栈顶是否对应
            stack.pop();
          }else{
            return false;
          }
        }
      }
      if(stack.length!= 0){    //循环结束，栈内仍有元素，返回false
        return false;
      }
      return true;
  }

再来看第二题：

与第一题相比，这题难就难在如果不会用正则，那就要巨多判断步骤，但是你会正则的话，这题还是比较有意思的。

/**
 * @param {string[]} logs
 * @return {string[]}
 */
var reorderLogFiles = (logs) => logs.map(s => {
    const [_, id, log] = s.match(/^(\S+) (.*)$/);  //提取出日志ID (`id`) 和日志内容 (`log`)。
    const isAlphabetic = /^[a-z ]+$/.test(log);    //判断是不是字母型日志
    return {s, id, log, isAlphabetic};
}).sort((a, b) => {                             //通过不同的判断条件来判断相邻两条Log的排列
    if (a.isAlphabetic !== b.isAlphabetic) {
        return a.isAlphabetic ? -1 : 1;   
    }
    if (a.isAlphabetic) {
        if (a.log !== b.log) {
            return a.log < b.log ? -1 : 1;
        } else {
            return a.id < b.id ? -1 : 1;
        }
    } else {
        return 0;      //都为数字日志，保留原来位置
    }
}).map((v) => v.s);    //返回排序号的数组

上面的这道题解法，真的很妙，大家可以阅读一下，使用Sort根据不同的条件进行判断,

比较是否为字母型日志：

如果两者都是字母型日志：

如果两者都是数字型日志：

这是下面的原答案链接，937. 重新排列日志文件 - 力扣（LeetCode）

字节一面

前面的美团一面第二题虽然复杂，但是人也给我一道简单题了，而且还是选择一道题拿下就行了，明显放水。接着看字节字面的算法题：

3. LCR 144. 翻转二叉树 - 力扣（LeetCode）4. 设计二叉树结构、自己设计案例、再前序遍历二叉树输出数组先看第一题：

也是一道非常简单的树结构题，不多讲了，不会的友友可以看一下解析

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var mirrorTree = function(root) {
  if (root === null) {
    return root;
  }
  // 交换当前节点的左右子树
  [root.left, root.right] = [root.right, root.left];
  // 递归地镜像左右子树
  mirrorTree(root.left);
  mirrorTree(root.right);
  return root;
};

2. 再来看第二题：设计二叉树结构、自己设计案例、再前序遍历二叉树输出数组。

是不是挺多友友觉得这题也是挺简单的，确实。当时为了这里可以增加一些闪光点，我使用TS给面试官加一些印象分了：

interface NodeValue {    // 定义传入参数的类型
  value: number;
  left?: BinaryTreeNode | null;  // 可选属性
  right?: BinaryTreeNode | null; // 可选属性
}
class BinaryTreeNode {   // 创建二叉树的结构
  value: number | null;
  left: BinaryTreeNode | null;
  right: BinaryTreeNode | null;
  constructor(obj: NodeValue) {   // 约定传入参数的类型
    this.value = obj.value ?? null;
    this.left = obj.left ?? null;
    this.right = obj.right ?? null; // 修正这里，确保正确设置right属性
  }
  PreRraversal(): void {      // 前序遍历
    if (this.value !== null) {
      console.log(this.value);
    }
    this.left && this.left.PreRraversal();   // 如果left存在则遍历左子树
    this.right && this.right.PreRraversal(); // 遍历右子树
  }
}

如果不会TS的类型约束的话，在面试的时候还是不要使用了，毕竟写对了才是第一位。

字节招的人还是比较多的，这里还给友友们弄了几个字节一面题：

5. 394. 字符串解码 - 力扣（LeetCode）

/**
 * @param {string} s
 * @return {string}
 */
function decodeString(s) {
    let stack = [];
    let currentNum = 0;
    let currentStr = '';
    for (let char of s) {
        if (+char+1) {   //隐式转换  +1防止出现'0'进入不了判断内部
            currentNum = currentNum * 10 + parseInt(char, 10);
        } else if (char === '[') {   
            stack.push([currentStr, currentNum]);  //存储之前的解码内容与解码数字
            currentStr = '';    //置空
            currentNum = 0;
        } else if (char === ']') {   //解码
            let [prevStr, num] = stack.pop();   //解构出[]内的内容与重复次数
            currentStr = prevStr + currentStr.repeat(num); // repeat 将字符串重复num次
        } else {
            currentStr += char;
        }
    }
    return currentStr;
}

其实这里存储[]与使用两个栈式没有什么区别的

这里通过在栈内存储每次解码的currentStr之后再去对这个变量置空，减少了对变量的引入，同时在遇见"[ " 时对currentNum置空，**"+char+1"**也是JS中常见的一种判断数字字符的方法。

6. 3. 无重复字符的最长子串 - 力扣（LeetCode）

无重复字符的最长子串，老朋友了。LeetCode第3题就是，经典滑动窗口习题

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
 let maxLength = 0;  //记录长度
  let seen = new Set();  //使用Set身上has与delete方法，同时
  let left = 0;
  
  for (let right = 0; right < s.length; right++) {
    // 移除左边的字符，直到当前字符可以被加入而不引起重复
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    
    seen.add(s[right]);
    maxLength = maxLength>right - left + 1?maxLength:right - left + 1
  }
  
  return maxLength;
};

这题的思路也很简单，题解配合注释看便可以了。

7.300. 最长递增子序列 - 力扣（LeetCode）

这题不用多说他的重要性了，Vue，React框架的Diff算法的优化缩影里面就有最长递增子序列的思想，同时也是动态规划的经典题型之一，因此就是背也要把这题背下来的。

/**
 * @param {number[]} nums
 * @return {number}
 */
   var lengthOfLIS = function(nums) {
    const dp = new Array(nums.length).fill(1); // 初始化dp数组
    let maxLen = 1;
    for (let i = 1; i < nums.length; i++) {
        let maxPrev = 0;
        // 直接遍历之前的dp数组
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                maxPrev = Math.max(maxPrev, dp[j]);
            }
        }
        dp[i] = maxPrev + 1;
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
};

这里的思想是使用dp数组来进行存储当前下标元素的当前最大递增序列，这也是动态规划的中心思想：“局部最优解可以扩展为全局最优解”

量化公司一面

金融量化公司的待遇是没得说，实习生给开到600~800一天，人家要要求自然也是高的。

8 LCR 105. 岛屿的最大面积 - 力扣（LeetCode）

经典的动态规划+DFS问题：

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
  let MaxIsland=0
  function findMaxIsland(n,m,res){
      if(n>=grid[0].length||m>=grid.length||n<0||m<0 || grid[m][n] === 0){
          return res
      }
          grid[m][n]=0
          res++
          res = findMaxIsland(n + 1, m, res);
          res = findMaxIsland(n - 1, m, res);
          res = findMaxIsland(n, m + 1, res);
          res = findMaxIsland(n, m - 1, res);
      return res
  }
  for(let j=0;j
      for(let i=0;i
          if(grid[j][i]===1){
            let ret=findMaxIsland(i,j,0)
          MaxIsland= ret>MaxIsland?ret:MaxIsland
          console.log(ret)
          }
      }
  }
  return MaxIsland
};

695. 岛屿的最大面积 Max Area of Island【LeetCode 力扣官方题解】_哔哩哔哩_bilibili靠文字叙述太抽象这里直接给大家找来了官方动画来解惑咯。其实不只是最大岛屿是这个思想，岛屿数量也是这个思想

9 最大岛屿的中心点

这道题在LeetCode上并没有，应该是这个公司题库自己的题，题目也很简单，就是在最大岛屿的基础上求它的中心点，中心点的定义为，最上面与最底部的坐标平均值，最左边与最右边的平均值，看题解：

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function (grid) {
    //全部置为无穷大
    const Lands=[]
    let center = [] //center
    function findMaxIsland(n, m, res, arr) {
        if (n >= grid[0].length || m >= grid.length || n < 0 || m < 0 || grid[m][n] === 0) {
            return res
        }
        arr[0] = n < arr[0] ? n : arr[0]    //上
        arr[1] = n > arr[1] ? n : arr[1]    //下
        arr[2] = m < arr[2] ? m : arr[2]    //左
        arr[3] = m > arr[3] ? m : arr[3]    //右
        grid[m][n] = 0  //置空
        res++   // maxArea++
        res = findMaxIsland(n + 1, m, res,arr);
        res = findMaxIsland(n - 1, m, res,arr);
        res = findMaxIsland(n, m + 1, res,arr);
        res = findMaxIsland(n, m - 1, res,arr);
        return res
    }
    for (let j = 0; j < grid.length; j++) {
        for (let i = 0; i < grid[0].length; i++) {
            if (grid[j][i] === 1) {
                Lands.push([i, i, j, j])    //push一个第一片岛屿的中心点 [top bottom left right]
                let ret = findMaxIsland(i, j, 0, Lands[Lands.length-1])
                center = ret > MaxIsland ?([
                    (Lands[Lands.length-1][2]+Lands[Lands.length-1][3])/2,   // X轴
                    (Lands[Lands.length-1][0]+Lands[Lands.length-1][1])/2    // Y轴
                ]) : center
            }
        }
    }
    return center
};
grid = [
    [1,1,1,1,0],
    [1,1,0,1,0],
    [1,1,0,0,0],
    [0,0,0,0,0]
  ]
console.log(maxAreaOfIsland(grid));

道题虽然不在LeetCode中，但要单独说换一下呢，因为现在大厂面试的趋势仍然是LeetCode热门题，但是现在为了考察算法能力，也加入了许多的改变，融合的更多的数据处理知识点。因此更需要我们准备好多方面的数据结构的处理能力。