- 正确答案：给定一个字符串，要求将其中的单词顺序反转（即整个字符串中单词的排列顺序颠倒），但每个单词内部的字符顺序保持不变。例如输入 "hello world python"，输出应为 "python world hello"。注意需处理首尾空格、连续空格等边界情况，且不能使用内置 split/reverse/join 等高级函数（手撕要求体现底层操作能力）。 - 解答思路：分三步完成—— 1. 全局翻转：先将整个字符串所有字符逆序，此时单词内部也反了，但单词整体位置已颠倒； 2. 单词级翻转：遍历翻转后的字符串，识别每个单词的起止索引（以空格为界），对每个单词内部字符再次翻转； 3. 清理多余空格：去除首尾空格，并将中间连续多个空格压缩为单个空格（若题目要求“严格格式化”）。关键在于：不依赖语言高级API，全程用双指针+原地交换实现，时间复杂度O(n)，空间复杂度O(1)（若允许修改原数组；若字符串不可变如Python，则需O(n)额外空间构造结果列表）。 - 深度知识讲解：本题本质考察对“原地算法”（in-place algorithm）和“双指针技术”的掌握，以及对字符串不可变性（如Python str）与可变性（如Java char[]、C++ string）的底层认知。 ▶ 底层数据结构视角：字符串在内存中是连续字符数组。C/C++中char*可直接swap；Python中str是immutable对象，必须转为list（可变序列）操作，最后join；Java中String不可变，需用StringBuilder或char[]。 ▶ 翻转操作原理：区间翻转通过双指针交换实现——left从区间头出发，right从区间尾出发，while left < right 时交换s[left]和s[right]，然后left++、right--。该操作时间复杂度O(k)，k为区间长度，无额外空间开销。 ▶ 空格处理机制：需手动跳过空格识别单词边界。典型状态机思想：用两个指针start/end标记当前单词起点和终点；或用快慢指针（slow指向结果写入位置，fast扫描原串），实现“原地去重空格”（类似LeetCode 151题标准解法）。 ▶ 稳定性与边界安全：需防御性编程——检查空串、全空格、单字符等case；索引越界判断（如fast >= n）必须显式写出；避免因连续空格导致start > end的非法翻转。 - 伪代码（通用可读版，适配多数语言）： ``` function reverseWords(s): if s is empty: return s // Step 1: convert to mutable list (e.g., char array) chars = s.to_char_array() // or list(s) in Python n = length(chars) // Step 2: reverse entire array reverse_range(chars, 0, n-1) // Step 3: reverse each word i = 0 while i < n: // skip leading spaces while i < n and chars[i] == ' ': i += 1 if i >= n: break // mark start of word start = i // find end of word while i < n and chars[i] != ' ': i += 1 end = i - 1 // reverse this word reverse_range(chars, start, end) // Step 4: remove extra spaces (optional but common requirement) // Use two-pointer in-place compaction: write = 0 read = 0 while read < n: // skip leading spaces if chars[read] == ' ': read += 1 continue // copy non-space char if write > 0: chars[write] = ' ' write += 1 // copy whole word while read < n and chars[read] != ' ': chars[write] = chars[read] write += 1 read += 1 // truncate to [0, write) result = subarray(chars, 0, write) return result as string function reverse_range(arr, left, right): while left < right: swap(arr[left], arr[right]) left += 1 right -= 1 ``` - Python 实现（含完整边界处理，符合面试手撕规范）： ``` def reverse_words(s: str) -> str: if not s: return s chars = list(s) n = len(chars) # Helper: reverse chars[l..r] inclusive def reverse(l, r): while l < r: chars[l], chars[r] = chars[r], chars[l] l += 1 r -= 1 # Step 1: reverse entire string reverse(0, n - 1) # Step 2: reverse each word i = 0 while i < n: if chars[i] == ' ': i += 1 continue j = i while j < n and chars[j] != ' ': j += 1 reverse(i, j - 1) i = j # Step 3: remove extra spaces - two pointers # write: next position to write valid char # read: current scanning position write = 0 read = 0 while read < n: # skip leading spaces if chars[read] == ' ': read += 1 continue # add space before word (except first word) if write > 0: chars[write] = ' ' write += 1 # copy current word while read < n and chars[read] != ' ': chars[write] = chars[read] write += 1 read += 1 return ''.join(chars[:write]) ``` - 扩展知识点： ▶ 进阶变体：若要求“单词内字符也反转”（如"hello world" → "dlrow olleh"），则只需执行Step1全局翻转，省略Step2； ▶ 内存优化：C++中可直接用std::reverse(s.begin(), s.end()) + 遍历空格分隔翻转，但面试官更关注手动实现细节； ▶ 复杂度陷阱：若用split()再reverse再join，时间O(n)但隐含多次内存分配，且无法体现底层能力； ▶ Unicode支持：真实系统中需考虑UTF-8多字节字符，但校园招聘通常假设ASCII； ▶ 测试用例设计：应覆盖 ""、" "、" "、"a"、" hello world "、"t a b" 等case，验证鲁棒性。

百度测开一面（53分钟）

全站热榜

创作者周榜