大厂面试专项讲解 - 字节/阿里/腾讯真题¶

class DLinkedNode:
    """双向链表节点"""
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    """
    LRU缓存
    时间：O(1) get和put
    空间：O(capacity)
    """

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # 哈希表：key -> 节点

        # 创建伪头部和伪尾部节点
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove_node(self, node):
        """移除节点"""
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_head(self, node):
        """添加节点到头部"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _move_to_head(self, node):
        """移动节点到头部"""
        self._remove_node(node)
        self._add_to_head(node)

    def get(self, key: int) -> int:
        """获取值"""
        if key not in self.cache:
            return -1

        # 获取节点，移动到头部
        node = self.cache[key]
        self._move_to_head(node)

        return node.value

    def put(self, key: int, value: int) -> None:
        """放入值"""
        if key in self.cache:
            # 更新值，移动到头部
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)
        else:
            # 创建新节点
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self._add_to_head(node)

            # 检查容量
            if len(self.cache) > self.capacity:
                # 移除尾部节点（最久未使用）
                removed = self.tail.prev
                self._remove_node(removed)
                del self.cache[removed.key]

def four_sum(nums, target):
    """
    四数之和
    时间：O(n³)
    空间：O(1)
    """
    nums.sort()
    n = len(nums)
    result = []

    for i in range(n - 3):
        # 跳过重复
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        for j in range(i + 1, n - 2):
            # 跳过重复
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue

            # 双指针
            left, right = j + 1, n - 1

            while left < right:
                current_sum = nums[i] + nums[j] + nums[left] + nums[right]

                if current_sum == target:
                    result.append([nums[i], nums[j], nums[left], nums[right]])

                    # 跳过重复
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1

                    left += 1
                    right -= 1

                elif current_sum < target:
                    left += 1
                else:
                    right -= 1

    return result

def trap(height):
    """
    接雨水（双指针）
    时间：O(n)
    空间：O(1)
    """
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0

    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]

    return water

def trap_dp(height):
    """
    接雨水（动态规划）
    时间：O(n)
    空间：O(n)
    """
    if not height:
        return 0

    n = len(height)

    # left_max[i] = height[0:i]的最大值
    left_max = [0] * n
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])

    # right_max[i] = height[i:n]的最大值
    right_max = [0] * n
    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])

    # 计算水量
    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - height[i]

    return water

def longest_valid_parentheses(s):
    """
    最长有效括号（栈）
    时间：O(n)
    空间：O(n)
    """
    max_length = 0
    stack = [-1]  # 初始化：-1作为起始位置

    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        else:
            # 弹出栈顶
            stack.pop()

            if not stack:
                # 栈空，压入当前索引作为新的起始位置
                stack.append(i)
            else:
                # 计算有效长度
                current_length = i - stack[-1]
                max_length = max(max_length, current_length)

    return max_length

from collections import deque

def max_sliding_window(nums, k):
    """
    滑动窗口最大值（单调队列）
    时间：O(n)
    空间：O(k)
    """
    if not nums or k <= 0:
        return []

    # 单调递减队列：存储索引
    deque_idx = deque()
    result = []

    for i, num in enumerate(nums):
        # 移除超出窗口的元素
        while deque_idx and deque_idx[0] <= i - k:
            deque_idx.popleft()

        # 移除比当前元素小的元素（单调递减）
        while deque_idx and nums[deque_idx[-1]] < num:  # 负索引：从末尾倒数访问元素
            deque_idx.pop()

        # 添加当前元素索引
        deque_idx.append(i)

        # 记录窗口最大值
        if i >= k - 1:
            result.append(nums[deque_idx[0]])

    return result

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_between(head, left, right):
    """
    反转链表II
    时间：O(n)
    空间：O(1)
    """
    # 创建虚拟头节点
    dummy = ListNode(0)
    dummy.next = head

    # 第1步：找到left前一个节点
    prev = dummy
    for _ in range(left - 1):
        prev = prev.next

    # 第2步：反转从left到right的节点
    current = prev.next
    reverse_prev = None

    for _ in range(right - left + 1):
        next_node = current.next
        current.next = reverse_prev
        reverse_prev = current
        current = next_node

    # 第3步：连接反转后的链表
    prev.next.next = current
    prev.next = reverse_prev

    return dummy.next

def inorder_traversal(root):
    """
    中序遍历（递归）
    时间：O(n)
    空间：O(h)
    """
    result = []

    def inorder(node):
        if not node:
            return

        inorder(node.left)
        result.append(node.val)
        inorder(node.right)

    inorder(root)
    return result

def inorder_traversal_iterative(root):
    """
    中序遍历（迭代）
    时间：O(n)
    空间：O(h)
    """
    result = []
    stack = []
    current = root

    while current or stack:
        # 一直向左走
        while current:
            stack.append(current)
            current = current.left

        # 访问节点
        current = stack.pop()
        result.append(current.val)

        # 转向右子树
        current = current.right

    return result

def my_pow(x, n):
    """
    Pow(x, n)（快速幂）
    时间：O(log n)
    空间：O(1)
    """
    def fast_pow(x, n):
        if n == 0:
            return 1.0

        half = fast_pow(x, n // 2)

        if n % 2 == 0:
            return half * half
        else:
            return half * half * x

    if n < 0:
        x = 1 / x
        n = -n

    return fast_pow(x, n)

def longest_common_prefix(strs):
    """
    最长公共前缀（垂直扫描）
    时间：O(m * n)，m是最短字符串长度，n是字符串数量
    空间：O(1)
    """
    if not strs:
        return ""

    # 找到最短字符串
    min_str = min(strs, key=len)

    for i, char in enumerate(min_str):
        # 检查所有字符串的第i个字符
        for s in strs:
            if s[i] != char:
                return min_str[:i]

    return min_str

def generate_parenthesis(n):
    """
    括号生成（回溯）
    时间：O(4^n / sqrt(n))
    空间：O(n)
    """
    result = []

    def backtrack(current, left, right):
        """
        current: 当前生成的字符串
        left: 左括号数量
        right: 右括号数量
        """
        # 终止条件：生成了2n个字符
        if len(current) == 2 * n:
            result.append(current)
            return

        # 添加左括号（如果左括号数量 < n）
        if left < n:
            backtrack(current + '(', left + 1, right)

        # 添加右括号（如果右括号数量 < 左括号数量）
        if right < left:
            backtrack(current + ')', left, right + 1)

    backtrack('', 0, 0)
    return result

def permute(nums):
    """
    全排列（回溯）
    时间：O(n! * n)
    空间：O(n)
    """
    result = []
    n = len(nums)
    used = [False] * n

    def backtrack(current):
        # 终止条件：生成了n个数字
        if len(current) == n:
            result.append(current[:])
            return

        for i in range(n):
            if not used[i]:
                # 选择
                used[i] = True
                current.append(nums[i])

                # 递归
                backtrack(current)

                # 撤销选择
                current.pop()
                used[i] = False

    backtrack([])
    return result

def permute_swap(nums):
    """
    全排列（交换法）
    时间：O(n! * n)
    空间：O(1)（不包括输出）
    """
    result = []

    def backtrack(start):
        # 终止条件
        if start == len(nums):
            result.append(nums[:])
            return

        for i in range(start, len(nums)):
            # 交换
            nums[start], nums[i] = nums[i], nums[start]

            # 递归
            backtrack(start + 1)

            # 撤销交换
            nums[start], nums[i] = nums[i], nums[start]

    backtrack(0)
    return result

def subsets(nums):
    """
    子集（回溯）
    时间：O(2^n * n)
    空间：O(n)
    """
    result = []

    def backtrack(start, current):
        # 每次递归都记录当前子集
        result.append(current[:])

        # 从start开始，避免重复
        for i in range(start, len(nums)):
            # 选择nums[i]
            current.append(nums[i])

            # 递归（从i+1开始，避免重复使用）
            backtrack(i + 1, current)

            # 撤销选择
            current.pop()

    backtrack(0, [])
    return result

def combine(n, k):
    """
    组合（回溯）
    时间：O(C(n,k) * k)
    空间：O(k)
    """
    result = []

    def backtrack(start, current):
        # 终止条件：找到k个数
        if len(current) == k:
            result.append(current[:])  # 切片操作：[start:end:step]提取子序列
            return

        # 从start到n
        # 剪枝优化：i最多到 n - (k - len(current)) + 1
        for i in range(start, n - (k - len(current)) + 2):
            # 选择i
            current.append(i)

            # 递归（从i+1开始，保证递增顺序）
            backtrack(i + 1, current)

            # 撤销选择
            current.pop()

    backtrack(1, [])
    return result

def exist(board, word):
    """
    单词搜索
    时间：O(m * n * 4^L)，L是word长度
    空间：O(L)
    """
    if not board or not board[0]:
        return False

    m, n = len(board), len(board[0])

    def dfs(i, j, index):
        """
        i, j: 当前位置
        index: word的索引
        """
        # 终止条件：找到完整单词
        if index == len(word):
            return True

        # 边界检查 + 字符匹配
        if i < 0 or i >= m or j < 0 or j >= n:
            return False
        if board[i][j] != word[index]:
            return False

        # 标记已访问
        temp = board[i][j]
        board[i][j] = '#'

        # 向四个方向搜索
        found = (dfs(i + 1, j, index + 1) or
                 dfs(i - 1, j, index + 1) or
                 dfs(i, j + 1, index + 1) or
                 dfs(i, j - 1, index + 1))

        # 恢复
        board[i][j] = temp

        return found

    # 从每个位置开始搜索
    for i in range(m):
        for j in range(n):
            if dfs(i, j, 0):
                return True

    return False

def num_islands(grid):
    """
    岛屿数量（DFS）
    时间：O(m * n)
    空间：O(m * n)
    """
    if not grid or not grid[0]:
        return 0

    m, n = len(grid), len(grid[0])
    count = 0

    def dfs(i, j):
        """标记相连的陆地"""
        # 边界检查
        if i < 0 or i >= m or j < 0 or j >= n:
            return
        if grid[i][j] != '1':
            return

        # 标记为已访问
        grid[i][j] = '2'

        # 向四个方向扩展
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)

    # 遍历整个网格
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                # 发现新岛屿
                count += 1
                # 标记整个岛屿
                dfs(i, j)

    return count

def two_sum(nums, target):
    """
    两数之和
    时间：O(n)
    空间：O(n)
    """
    # 创建哈希表
    num_to_index = {}

    for i, num in enumerate(nums):
        complement = target - num

        # 检查补数
        if complement in num_to_index:
            return [num_to_index[complement], i]

        num_to_index[num] = i

    return []

def f(a,b):
    d={}
    for i,x in enumerate(a):  # enumerate同时获取索引和值
        y=b-x
        if y in d:return[d[y],i]
        d[x]=i
    return[]

# ❌ 忘记处理空数组
def max_sub_array(nums):
    return max(nums)  # 空数组会报错

# ✅ 正确处理
def max_sub_array(nums):
    if not nums:
        return 0
    return max(nums)

# ❌ 可能溢出
def multiply(a, b):
    return a * b  # 大数可能溢出

# ✅ 使用模运算
def multiply(a, b, mod=10**9 + 7):
    return (a * b) % mod

# ❌ 可能越界
def get_next(arr, i):
    return arr[i + 1]  # 最后一个元素会越界

# ✅ 边界检查
def get_next(arr, i):
    if i + 1 < len(arr):
        return arr[i + 1]
    return None