刷LeetCode前先来这里！Pythontip基础算法10题通关攻略（附多种解法对比）
Python算法入门：10道基础题的多解法思维训练
在编程面试中，算法能力往往是区分候选人的关键因素。但对于初学者来说，直接挑战LeetCode上的中等难度题目可能会感到力不从心。这就好比一个刚开始健身的人，如果直接尝试举起100公斤的杠铃，不仅难以完成，还可能受伤。我们需要一个循序渐进的训练计划——而PythonTip上的基础算法题正是这个完美的"训练场"。
1. 为什么从基础算法题开始？
许多初学者在准备技术面试时，常常陷入一个误区：认为刷的题目越多、越难，效果就越好。实际上，掌握基础算法的多种解法比单纯追求题目数量重要得多。基础算法就像武术中的马步，只有扎稳了，后面的高难度动作才能水到渠成。
以简单的两数相加为例，虽然题目本身简单，但我们可以从中学习：
- Python的基本输入输出处理
- 函数的定义和使用
- 代码的简洁性优化
# 最基础的两数相加 def solve_it(): return a + b # 一行式解决方案 solve_it = lambda: a + b这两种写法虽然结果相同，但后者展示了Python的lambda表达式用法，体现了对语言特性的深入理解。面试官往往更看重这种对语言特性的灵活运用能力。
2. 基础题目中的算法思维培养
2.1 列表排序的艺术
列表排序看似简单，但其中蕴含着多种算法思想。Python内置的sorted()函数非常方便，但了解其背后的原理同样重要。
# 使用内置函数 def solve_it(): return sorted(L) # 手动实现冒泡排序 def bubble_sort(lst): n = len(lst) for i in range(n): for j in range(0, n-i-1): if lst[j] > lst[j+1]: lst[j], lst[j+1] = lst[j+1], lst[j] return lst比较这两种方法：
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| sorted() | O(n log n) | O(n) | 通用场景 |
| 冒泡排序 | O(n²) | O(1) | 教学用途 |
虽然在实际开发中我们几乎总是使用内置的sorted()，但手动实现排序算法能帮助我们理解算法原理，这在面试中是非常有价值的。
2.2 字符串处理的技巧
字符串逆序是一个经典的面试题，Python提供了多种实现方式：
# 切片方法 def reverse_str_slice(a): return a[::-1] # 使用reversed函数 def reverse_str_reversed(a): return ''.join(reversed(a)) # 递归方法 def reverse_str_recursive(a): if len(a) <= 1: return a return reverse_str_recursive(a[1:]) + a[0]性能对比：
- 切片方法：最简洁高效，时间复杂度O(n)，空间复杂度O(n)
- reversed函数：可读性好，但需要额外join操作
- 递归方法：教学意义大于实用价值，有栈溢出风险
提示：在Python中，字符串是不可变对象，任何修改都会创建新对象，这是字符串操作需要考虑的性能因素。
3. 字典与列表的高级操作
3.1 字典键的处理
处理字典键时，我们需要考虑键的类型和排序要求：
a = {1:1, 2:2, 3:3} # 方法1：直接转换 print(','.join(map(str, a))) # 方法2：显式处理键 keys = sorted(a.keys()) print(','.join(str(k) for k in keys))两种方法的区别在于：
- 方法1更简洁，但假设键已经是需要的顺序
- 方法2更明确，确保键按字典序排列
3.2 奇数位置字符提取
提取奇数位置字符也有多种实现方式：
# 方法1：循环判断 result = [] for i in range(len(a)): if i % 2 == 0: # Python索引从0开始 result.append(a[i]) print(''.join(result)) # 方法2：切片 print(a[::2])切片方法明显更简洁高效，但理解其工作原理很重要：
a[start:stop:step]是Python的切片语法::2表示从开始到结束，步长为2
4. 数学相关算法
4.1 素数判断算法
找出100以内的素数是一个经典的算法题，我们可以对比几种实现：
# 基础方法 primes = [] for num in range(2, 101): for i in range(2, num): if num % i == 0: break else: primes.append(str(num)) print(' '.join(primes)) # 优化方法：只需检查到平方根 import math primes = [] for num in range(2, 101): for i in range(2, int(math.sqrt(num)) + 1): if num % i == 0: break else: primes.append(str(num)) print(' '.join(primes))优化后的方法减少了不必要的检查，效率更高。进一步优化还可以使用埃拉托斯特尼筛法。
4.2 中位数计算
中位数计算需要考虑列表长度的奇偶性：
def median(lst): sorted_lst = sorted(lst) n = len(sorted_lst) if n % 2 == 1: return sorted_lst[n//2] else: return (sorted_lst[n//2-1] + sorted_lst[n//2])/2关键点：
- 必须先排序列表
- 奇数长度取中间值
- 偶数长度取中间两个数的平均值
5. 最大公约数与最小公倍数
5.1 最大公约数的多种算法
最大公约数(GCD)有多种计算方法，各有特点：
# 更相减损法 def gcd_sub(a, b): if a == b: return a return gcd_sub(max(a,b)-min(a,b), min(a,b)) # 辗转相除法（递归） def gcd_recursive(a, b): return a if b == 0 else gcd_recursive(b, a % b) # 辗转相除法（迭代） def gcd_iterative(a, b): while b: a, b = b, a % b return a性能比较：
| 方法 | 时间复杂度 | 优点 | 缺点 |
|---|---|---|---|
| 更相减损法 | O(max(a,b)) | 容易理解 | 效率较低 |
| 辗转相除(递归) | O(log(min(a,b))) | 代码简洁 | 有递归深度限制 |
| 辗转相除(迭代) | O(log(min(a,b))) | 效率高 | 代码稍复杂 |
5.2 最小公倍数的计算
最小公倍数(LCM)可以利用GCD来计算：
def lcm(a, b): return a * b // gcd_iterative(a, b)这种方法的效率远高于从最大值开始逐个检查的方法，因为它利用了数学关系：LCM(a,b) = a*b / GCD(a,b)。
6. 从基础到进阶的学习路径
掌握了这些基础算法后，可以按照以下路径继续提升：
- 数据结构基础：链表、栈、队列、哈希表的实现与应用
- 算法思想：分治、贪心、动态规划、回溯
- LeetCode分类练习：按题目类型系统练习
- 实际项目应用：将算法应用到实际问题中
注意：不要急于求成，每个算法概念都要确保真正理解并能手写实现。在面试中，面试官往往更看重你解决问题的思路，而不仅仅是最终答案。