字节面试高频百题(一)
内容提要
本文汇总字节跳动面试高频算法题及解法，包括反转链表、丑数、LRU缓存、二叉树遍历、二叉搜索树转双向链表、二分查找、层序遍历、两数之和、合并有序链表、双栈实现队列、跳台阶、K个一组翻转链表、最大子数组和、最长无重复子数组、判断链表环、合并有序数组、链表公共节点、环入口、括号序列、删除倒数第N个节点等。
延伸解读
高频题覆盖的算法模式
本文汇总的20道题覆盖了链表、二叉树、数组、动态规划、栈和队列等常见数据结构。其中链表相关题目最多，包括反转、合并、环检测、公共节点等，这些操作都依赖指针技巧，如虚拟头节点、快慢指针。二叉树题目则围绕遍历展开，如先中后序、层序和二叉搜索树转链表。掌握这些模式有助于应对字节面试中的算法环节。
链表题中的指针技巧
链表题频繁使用虚拟头节点和快慢指针。虚拟头节点能简化头节点可能被修改的情况，如合并有序链表和删除倒数第N个节点。快慢指针则用于环检测、找环入口和倒数节点。这些技巧在多个题目中反复出现，理解其原理可以举一反三，减少面试时的思考时间。
动态规划与滑动窗口的应用
跳台阶和最大子数组和体现了动态规划思想，前者是斐波那契数列的变种，后者需要定义以当前元素结尾的最大和。最长无重复子数组则使用滑动窗口，通过哈希集合维护窗口内元素唯一性。这些方法在数组和字符串问题中很常见，注意状态定义和边界条件。
二叉树遍历的递归与迭代
二叉树的先中后序遍历可以用递归统一实现，只需调整访问根节点的位置。层序遍历则需要借助队列进行迭代。二叉搜索树转双向链表利用中序遍历的有序性，在遍历过程中调整指针。理解递归与迭代的转换，以及不同遍历顺序的应用场景，是解决二叉树问题的关键。
Q&A
字节跳动面试中常考的反转链表有哪两种解法？
有两种解法：遍历法和递归法。遍历法使用三个指针（pre、cur、next）逐个反转节点指向；递归法则先递归到链表末尾，然后逐层反转指针。
如何判断一个数是否为丑数？
丑数是只包含质因子2、3、5的正整数。判断方法：若n<=0则不是丑数；否则循环将n除以2、3、5直到不能整除，最后若n==1则是丑数，否则不是。
设计LRU缓存结构需要用到哪些数据结构？如何实现O(1)的get和set？
使用哈希表+双向链表（或LinkedHashMap）。哈希表提供O(1)的访问，链表维护访问顺序。get时若存在则将该key移到最近使用位置；set时若key存在则更新并移到最近使用，若容量满则删除最久未使用的key（链表头部），然后插入新key到尾部。
如何用两个栈实现一个队列？
使用两个栈stack1和stack2。入队时直接压入stack1；出队时若stack2为空，则将stack1所有元素依次弹出并压入stack2，然后从stack2弹出栈顶元素。若stack2非空则直接弹出。
在升序数组中统计某个数字出现的次数，如何用二分查找实现？
分别用二分查找找到目标值的左边界和右边界。左边界查找时，当nums[mid]==target时收缩右边界；右边界查找时收缩左边界。若找到左右边界，则次数=右边界-左边界+1；否则返回0。
如何判断链表中是否有环？如果有环，如何找到环的入口节点？
判断有环：使用快慢指针，快指针每次走两步，慢指针每次走一步，若相遇则有环。找环入口：相遇后，将慢指针重新指向头节点，然后快慢指针同时每次走一步，再次相遇的节点即为环的入口。
