面试手写代码指南：高频题型与实战解析

一、字符串处理类：反转与回文判断

字符串操作是面试中基础且高频的题型，主要考察对语言特性的掌握及边界条件处理能力。

1. 字符串反转

典型场景：要求不使用内置函数（如reverse()）实现字符串反转。
示例代码：

def reverse_string(s: str) -> str:
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return ''.join(chars)

关键点：

• 双指针法：通过首尾指针交换元素，时间复杂度为O(n)，空间复杂度为O(1)（原地修改）。
• 边界处理：需考虑空字符串、Unicode字符（如中文）的完整性。

2. 回文字符串判断

典型场景：判断字符串是否为回文（正读反读相同），忽略大小写与非字母数字字符。
示例代码：

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

关键点：

• 双指针优化：跳过非字母数字字符，减少无效比较。
• 大小写处理：统一转换为小写后比较，避免大小写干扰。

二、数组操作类：两数之和与去重

数组类题目考察对索引、循环及空间复杂度的控制能力。

1. 两数之和

典型场景：给定数组与目标值，返回两数索引使和等于目标值。
示例代码：

def two_sum(nums: list[int], target: int) -> list[int]:
    num_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i
    return []

关键点：

• 哈希表优化：将时间复杂度从O(n²)降至O(n)，空间复杂度为O(n)。
• 边界条件：需处理无解情况（返回空列表）。

2. 数组去重

典型场景：给定有序数组，原地删除重复元素并返回新长度。
示例代码：

def remove_duplicates(nums: list[int]) -> int:
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

关键点：

• 双指针法：快指针遍历，慢指针记录非重复元素位置。
• 原地修改：无需额外空间，符合题目要求。

三、链表操作类：反转与环检测

链表类题目考察指针操作与递归思维。

1. 链表反转

典型场景：反转单链表并返回头节点。
示例代码：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def reverse_list(head: ListNode) -> ListNode:
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

关键点：

• 迭代法：通过三个指针（prev、current、next_node）逐步反转。
• 递归法：也可用递归实现，但需注意栈溢出风险。

2. 链表环检测

典型场景：判断链表是否有环，并返回环的起始节点。
示例代码：

def detect_cycle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow

关键点：

• 快慢指针法：快指针每次走两步，慢指针走一步，相遇则说明有环。
• 环起始点计算：相遇后，将慢指针重置到头节点，两指针同速前进，再次相遇点即为环起始点。

四、递归与动态规划类：斐波那契数列与爬楼梯

递归类题目考察对分治思想与记忆化的理解。

1. 斐波那契数列

典型场景：计算第n个斐波那契数，要求优化时间复杂度。
示例代码：

def fib(n: int) -> int:
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

关键点：

• 动态规划：用数组存储中间结果，避免重复计算。
• 空间优化：可进一步优化为仅保留前两个状态，空间复杂度降至O(1)。

2. 爬楼梯问题

典型场景：每次可爬1或2阶，求爬到第n阶的方法数。
示例代码：

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

关键点：

• 状态转移：方法数等于前两阶方法数之和，与斐波那契数列类似。
• 迭代优化：避免递归的重复计算，时间复杂度为O(n)。

五、实战建议

1. 模拟面试环境：限时手写代码，培养时间管理能力。
2. 覆盖边界条件：如空输入、极端值、重复元素等。
3. 优化与沟通：先实现基础解法，再逐步优化，并解释思路。
4. 工具准备：熟悉常用数据结构（如栈、队列）的实现。

通过系统练习上述题型，开发者可显著提升面试中的手写代码能力，从容应对技术挑战。