面试经验：字节跳动面试中的难题

字节跳动这家公司，应该是所有秋招的公司中，对算法最重视的一个了，每次面试基本都会让你手撕算法，今天这篇文章就记录下当时被问到的几个算法题，并且每个算法题我都详细着给出了最优解，下面再现当时的面试场景。看完一定让你有所收获

一、小牛试刀：有效括号

大部分情况下，面试官都会问一个不怎么难的问题，不过你千万别太开心，因为这道题往往可以拓展出更多有难度的问题，或者一道题看起来很简单，但是给出最优解，确实很不容易的。这道题是这样的

给定一个只包括 ‘(’，’)'的字符串，判断字符串是否有效。注：空字符串属于有效字符串

示例 1:
输入: "(())"
输出: true
  
 实例 2：
 输入: "())("
输出: false
 

第一眼看到这道题，我去，这么简单，稳了（因为一面的时候，刚刚被面试官怼过勇者斗恶龙的DP题，在 leetcdoe 属于 hard 级别）。

其实这道题的 leetcode 第 20 题的简化版，属于 easy 级别

于是我也不假思索直接用栈来解决了，相信 99% 都会用栈解决吧？这里我稍微说以下过程吧，步骤如下：

1、在遍历字符串的过程中，遇到 “(” 就让它入栈，遇到 “)” 就判断下栈里面有没有 “(” ：

（1）、如果有，则把处于栈顶的 "("  弹出，相当于和 ")" 进行匹配，然后继续往后遍历字符串

（2）、如果没有，则匹配失败。相当于字符串的最前面出现了 ")"，显然这是不合理的。

2、当字符串遍历完成，判断栈是否为空，如果为空则表示字符串有效，否则无效。

为了兼顾小白，我该给你们画了个图演示，，，，我太良心了。

代码如下所示（Java，不过不是学Java也能看懂）

public static boolean isValid(String s){
   
    if(s == null || s.length() < 1)
        return true;
    int n = s.length();// 字符串长度
    // 创建一个栈来装字符
    Stack<Character> stack = new Stack<>();
    // 遍历字符串
    for(int i = 0; i < n; i++){
   
        // 获取字符串的第 i 个字符
        char c = s.charAt(i);
        if(c == '('){
   
            stack.push(c);
        }else{
   
            if(stack.