基础练习题答案与提示¶
包含范围：阶段一所有练习题的详细解答 使用建议：先自己尝试，遇到困难再查看答案
📋 目录¶
复杂度分析练习¶
练习1：分析代码复杂度¶
题目¶
分析以下代码的时间复杂度和空间复杂度：
Python
def function1(n):
sum = 0
for i in range(n):
for j in range(n):
sum += i * j
return sum
def function2(n):
sum = 0
for i in range(n):
for j in range(i, n):
sum += i * j
return sum
def function3(arr, target):
count = 0
for i in range(len(arr)):
if arr[i] == target:
count += 1
return count
答案与解析¶
function1: - 时间复杂度：O(n²) - 外层循环n次，内层循环n次 - 总操作数：n × n = n² - 空间复杂度：O(1) - 只使用了固定数量的变量（sum, i, j）
function2: - 时间复杂度：O(n²) - 外层循环n次 - 内层循环从i到n，平均n/2次 - 总操作数：n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²) - 空间复杂度：O(1)
function3: - 时间复杂度：O(n) - 单层循环，遍历一次数组 - 空间复杂度：O(1) - 只使用了固定数量的变量
练习2：优化代码¶
题目¶
优化以下代码，使其时间复杂度从O(n²)降到O(n)：
Python
# 原始代码：O(n²)
def find_duplicates(arr):
duplicates = []
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] == arr[j] and arr[i] not in duplicates:
duplicates.append(arr[i])
return duplicates
答案与解析¶
优化思路： 使用哈希表（集合）来记录已经见过的元素，避免嵌套循环。
优化后代码：
Python
def find_duplicates(arr):
"""
找出数组中的重复元素
时间复杂度：O(n)
空间复杂度：O(n)
"""
seen = set()
duplicates = set()
for num in arr:
if num in seen:
duplicates.add(num)
else:
seen.add(num)
return list(duplicates)
# 测试
arr = [1, 2, 3, 2, 4, 5, 3, 6]
print(find_duplicates(arr)) # [2, 3]（顺序可能不同）
复杂度分析： - 时间复杂度：O(n) - 单层遍历数组 - 集合的查找和插入都是O(1) - 空间复杂度：O(n) - 需要额外的空间存储seen和duplicates集合
数组练习¶
基础题¶
1. 找出数组中第二大的数¶
提示： - 不要排序（排序是O(n log n)） - 只需遍历两次或一次 - 维护最大值和次大值两个变量
答案：
Python
def find_second_largest(arr):
"""
找出数组中第二大的数
时间复杂度：O(n)
空间复杂度：O(1)
"""
if len(arr) < 2:
return None
largest = float('-inf')
second_largest = float('-inf')
for num in arr:
if num > largest:
second_largest = largest
largest = num
elif num > second_largest and num != largest:
second_largest = num
return second_largest if second_largest != float('-inf') else None
# 测试
print(find_second_largest([1, 2, 3, 4, 5])) # 4
print(find_second_largest([5, 5, 4, 3])) # 4
print(find_second_largest([1])) # None
2. 反转数组（不使用额外空间）¶
提示： - 使用双指针法 - 一个从前往后，一个从后往前 - 交换元素直到中间
答案：
Python
def reverse_array(arr):
"""
原地反转数组
时间复杂度：O(n/2) = O(n)
空间复杂度：O(1)
"""
left = 0
right = len(arr) - 1
while left < right:
# 交换
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
return arr
# 测试
arr = [1, 2, 3, 4, 5]
reverse_array(arr)
print(arr) # [5, 4, 3, 2, 1]
3. 检查数组是否有序¶
提示： - 检查是否升序或降序 - 只需遍历一次 - 比较相邻元素
答案：
Python
def is_sorted(arr):
"""
检查数组是否有序（升序或降序）
时间复杂度：O(n)
空间复杂度：O(1)
"""
if len(arr) <= 2:
return True
# 确定是升序还是降序
i = 1
while i < len(arr) and arr[i] == arr[i-1]:
i += 1
if i == len(arr):
return True # 所有元素相同
is_ascending = arr[i] > arr[i-1]
# 检查剩余元素
for i in range(1, len(arr)):
if is_ascending and arr[i] < arr[i-1]:
return False
if not is_ascending and arr[i] > arr[i-1]:
return False
return True
# 简化版：只检查升序
def is_sorted_ascending(arr):
"""检查是否升序"""
return all(arr[i] <= arr[i+1] for i in range(len(arr)-1))
# 测试
print(is_sorted([1, 2, 3, 4, 5])) # True
print(is_sorted([5, 4, 3, 2, 1])) # True
print(is_sorted([1, 3, 2, 4])) # False
进阶题¶
4. 合并两个有序数组¶
提示： - 使用双指针 - 比较两个数组的元素 - 创建新数组存储结果
答案：
Python
def merge_sorted_arrays(arr1, arr2):
"""
合并两个有序数组
时间复杂度：O(n + m)
空间复杂度：O(n + m)
"""
result = []
i = j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
# 添加剩余元素
result.extend(arr1[i:])
result.extend(arr2[j:])
return result
# 测试
print(merge_sorted_arrays([1, 3, 5], [2, 4, 6])) # [1, 2, 3, 4, 5, 6]
print(merge_sorted_arrays([1, 2, 3], [4, 5, 6])) # [1, 2, 3, 4, 5, 6]
5. 数组的轮转¶
提示： - 方法1：使用额外数组（简单） - 方法2：三次翻转（原地，推荐）
答案：
Python
def rotate(arr, k):
"""
向右轮转数组k步
方法1：使用额外数组
"""
n = len(arr)
if n == 0 or k % n == 0:
return arr
k = k % n
return arr[-k:] + arr[:-k] # 切片操作：[start:end:step]提取子序列
def rotate_in_place(arr, k):
"""
向右轮转数组k步
方法2：三次翻转（原地）
时间复杂度：O(n)
空间复杂度：O(1)
"""
n = len(arr)
if n == 0 or k % n == 0:
return
k = k % n
def reverse(left, right):
"""翻转arr[left:right+1]"""
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
# 三次翻转
reverse(0, n - 1) # 翻转整个数组
reverse(0, k - 1) # 翻转前k个元素
reverse(k, n - 1) # 翻转剩余元素
# 测试
arr = [1, 2, 3, 4, 5, 6, 7]
rotate_in_place(arr, 3)
print(arr) # [5, 6, 7, 1, 2, 3, 4]
链表练习¶
基础题¶
1. 获取链表长度¶
答案：
Python
def get_length(head):
"""
获取链表长度
时间复杂度：O(n)
空间复杂度：O(1)
"""
count = 0
current = head
while current:
count += 1
current = current.next
return count
2. 获取链表第n个节点的值¶
答案：
Python
def get_nth(head, n):
"""
获取链表第n个节点（从0开始）
时间复杂度：O(n)
空间复杂度：O(1)
"""
current = head
count = 0
while current:
if count == n:
return current.val
count += 1
current = current.next
return None # 索引超出范围
3. 清空链表¶
答案：
Python
def clear_list(head):
"""
清空链表（Python中通过垃圾回收自动处理）
时间复杂度：O(n)
空间复杂度：O(1)
"""
current = head
while current:
next_node = current.next
current.next = None # 断开连接（帮助GC）
current = next_node
return None # 返回None表示链表已清空
进阶题¶
4. 删除链表的倒数第n个节点¶
提示： - 使用快慢指针 - 快指针先走n步 - 然后快慢一起走，快指针到尾时，慢指针就在要删除的位置
答案：
Python
def remove_nth_from_end(head, n):
"""
删除链表倒数第n个节点
时间复杂度：O(n)
空间复杂度：O(1)
"""
# 创建哑节点简化边界处理
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
# 快指针先走n+1步
for _ in range(n + 1):
fast = fast.next
# 快慢一起走
while fast:
fast = fast.next
slow = slow.next
# 删除节点
slow.next = slow.next.next
return dummy.next
5. 旋转链表¶
提示： - 先计算链表长度 - 找到旋转点 - 重新连接
答案：
Python
def rotate_right(head, k):
"""
向右旋转链表k次
时间复杂度：O(n)
空间复杂度：O(1)
"""
if not head or not head.next:
return head
# 计算长度
length = 1
tail = head
while tail.next:
tail = tail.next
length += 1
# 处理k
k = k % length
if k == 0:
return head
# 找到新的尾节点（第length-k-1个节点）
new_tail = head
for _ in range(length - k - 1):
new_tail = new_tail.next
# 重新连接
new_head = new_tail.next
new_tail.next = None
tail.next = head
return new_head
栈练习¶
练习1：基本操作¶
答案：
Python
class Stack:
"""使用list实现栈"""
def __init__(self):
self.items = []
def push(self, item):
"""入栈：O(1)"""
self.items.append(item)
def pop(self):
"""出栈：O(1)"""
if not self.is_empty():
return self.items.pop()
raise IndexError("栈为空")
def peek(self):
"""查看栈顶：O(1)"""
if not self.is_empty():
return self.items[-1]
raise IndexError("栈为空")
def is_empty(self):
"""判断是否为空"""
return len(self.items) == 0
def size(self):
"""栈的大小"""
return len(self.items)
# 测试
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop()) # 3
print(stack.peek()) # 2
print(stack.size()) # 2
练习2：括号匹配¶
提示： - 遇到左括号入栈 - 遇到右括号检查栈顶是否匹配 - 最后检查栈是否为空
答案：
Python
def is_valid(s):
"""
判断括号是否合法
时间复杂度：O(n)
空间复杂度：O(n)
"""
stack = []
mapping = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in mapping: # 右括号
if stack and stack[-1] == mapping[char]: # 负索引：从末尾倒数访问元素
stack.pop()
else:
return False
else: # 左括号
stack.append(char)
return not stack
# 测试
print(is_valid("()")) # True
print(is_valid("()[]{}")) # True
print(is_valid("(]")) # False
print(is_valid("([)]")) # False
print(is_valid("{[]}")) # True
练习3：逆波兰表达式¶
提示： - 遇到数字入栈 - 遇到运算符弹出两个数字计算 - 结果入栈
答案：
Python
def eval_rpn(tokens):
"""
计算逆波兰表达式
时间复杂度：O(n)
空间复杂度：O(n)
"""
stack = []
for token in tokens:
if token in '+-*/':
# 弹出两个操作数
b = stack.pop()
a = stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
elif token == '/':
stack.append(int(a / b)) # 向零截断
else:
# 数字
stack.append(int(token))
return stack[0]
# 测试
print(eval_rpn(["2", "1", "+", "3", "*"])) # 9
print(eval_rpn(["4", "13", "5", "/", "+"])) # 6
print(eval_rpn(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])) # 22
队列练习¶
练习1：基本操作¶
答案：
Python
from collections import deque
class Queue:
"""使用deque实现队列"""
def __init__(self):
self.items = deque()
def enqueue(self, item):
"""入队：O(1)"""
self.items.append(item)
def dequeue(self):
"""出队：O(1)"""
if not self.is_empty():
return self.items.popleft()
raise IndexError("队列为空")
def peek(self):
"""查看队首：O(1)"""
if not self.is_empty():
return self.items[0]
raise IndexError("队列为空")
def is_empty(self):
"""判断是否为空"""
return len(self.items) == 0
def size(self):
"""队列的大小"""
return len(self.items)
练习2：用队列实现栈¶
答案：
Python
class StackWithQueue:
"""用队列实现栈"""
def __init__(self):
self.queue = deque()
def push(self, x):
"""入栈：O(n)"""
self.queue.append(x)
# 把前面的元素都移到后面
for _ in range(len(self.queue) - 1):
self.queue.append(self.queue.popleft())
def pop(self):
"""出栈：O(1)"""
if self.queue:
return self.queue.popleft()
raise IndexError("栈为空")
def top(self):
"""查看栈顶：O(1)"""
if self.queue:
return self.queue[0]
raise IndexError("栈为空")
哈希表练习¶
练习1：两数之和¶
答案：
Python
def two_sum(nums, target):
"""
找出数组中两个数之和等于target
时间复杂度：O(n)
空间复杂度：O(n)
"""
seen = {}
for i, num in enumerate(nums): # enumerate同时获取索引和值
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
练习2：字母异位词分组¶
答案：
Python
from collections import defaultdict # defaultdict带默认值的字典，避免KeyError
def group_anagrams(strs):
"""
将字母异位词分组
时间复杂度：O(n * k log k)，k是最长字符串长度
空间复杂度：O(n * k)
"""
groups = defaultdict(list)
for s in strs:
# 排序后的字符串作为key
key = ''.join(sorted(s))
groups[key].append(s)
return list(groups.values())
树练习¶
练习1：二叉树的最大深度¶
答案：
Python
def max_depth(root):
"""
二叉树的最大深度
时间复杂度：O(n)
空间复杂度：O(h)，h是树的高度
"""
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return max(left_depth, right_depth) + 1
练习2：翻转二叉树¶
答案：
Python
def invert_tree(root):
"""
翻转二叉树
时间复杂度：O(n)
空间复杂度：O(h)
"""
if not root:
return None
# 交换左右子节点
root.left, root.right = root.right, root.left
# 递归翻转
invert_tree(root.left)
invert_tree(root.right)
return root
练习3：对称二叉树¶
答案：
Python
def is_symmetric(root):
"""
判断二叉树是否对称
时间复杂度：O(n)
空间复杂度：O(h)
"""
if not root:
return True
def check(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
check(left.left, right.right) and
check(left.right, right.left))
return check(root.left, root.right)
📝 学习建议¶
如何使用这些答案¶
- 先自己尝试：不要马上看答案
- 遇到困难时：先看提示，再想一会儿
- 实在想不出：再看答案，理解思路
- 重要步骤：自己重新实现一遍
- 举一反三：尝试变式题目
常见错误¶
- 边界条件：空数组、单元素数组
- 索引越界：注意数组和链表的边界
- 时间复杂度：避免不必要的嵌套循环
- 空间复杂度：合理使用数据结构
练习方法¶
- 每题至少写3遍：第一遍理解，第二遍熟练，第三遍优化
- 限时练习：模拟面试环境
- 总结模式：记录常见的解题模式
继续努力！算法能力通过不断练习来提升！ 💪