Python 面試高頻算法題，這五個你應該掌握！
在Python求職面試中，算法題是考察候選人編程能力和解決問題能力的重要環節。很多公司都會通過算法題來篩選出優秀的工程師。本文將為大家總結Python面試中最常考的五個算法題。
1. 兩數之和 (Two Sum)
題目描述： 給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出和為目標值 target 的那兩個整數，并返回它們的數組下標。你可以假設每種輸入只會對應一個答案，并且數組中同一個元素不能使用兩遍。
解題思路：
最直觀的方法是使用兩層循環遍歷數組，檢查每兩個數字的和是否等于目標值。但這種方法的時間復雜度為 O(n^2)。
更高效的方法是使用哈希表（字典）來存儲已經遍歷過的數字及其下標。在遍歷數組的過程中，對于每個數字 num，我們檢查 target - num 是否在哈希表中。如果在，則說明我們找到了這兩個數字，直接返回它們的下標即可。否則，將當前的 num 和它的下標存入哈希表中。這種方法的時間復雜度為 O(n)。
def two_sum(nums, target):
"""
找出數組中和為目標值的兩個數的下標
Args:
nums: 整數數組
target: 目標值
Returns:
包含兩個下標的列表，如果不存在則返回 None
"""
num_map = {} # 創建一個空字典用于存儲數字和它們的下標
for index, num in enumerate(nums):
complement = target - num # 計算與當前數字配對的另一個數字
if complement in num_map: # 檢查complement是否已在字典中
return [num_map[complement], index] # 如果在，返回complement的下標和當前數字的下標
num_map[num] = index # 如果不在，將當前數字和它的下標存入字典
returnNone# 如果遍歷完數組沒有找到符合條件的兩個數，返回 None
# 案例
nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(f"數組：{nums}，目標值：{target}，結果：{result}") # 輸出：數組：[2, 7, 11, 15]，目標值：9，結果：[0, 1]
nums = [3, 2, 4]
target = 6
result = two_sum(nums, target)
print(f"數組：{nums}，目標值：{target}，結果：{result}") # 輸出：數組：[3, 2, 4]，目標值：6，結果：[1, 2]2. 反轉鏈表 (Reverse Linked List)
題目描述： 給你單鏈表的頭節點 head ，請你反轉鏈表，并返回反轉后的鏈表頭節點。
解題思路：反轉鏈表的核心思想是改變鏈表中節點的指向。我們可以使用迭代或遞歸兩種方法來實現。
迭代法：
維護三個指針：prev（指向前一個節點，初始為 None），curr（指向當前節點，初始為 head），next_node（指向下一個節點）。
遍歷鏈表，對于每個當前節點 curr，先保存它的下一個節點 next_node。然后將 curr 的 next 指針指向 prev。接著，將 prev 移動到 curr，curr 移動到 next_node。當 curr 為 None 時，prev 就指向了反轉后的鏈表的頭節點。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_linked_list(head):
"""
反轉單鏈表
Args:
head: 鏈表的頭節點
Returns:
反轉后鏈表的頭節點
"""
prev = None# 前一個節點，初始為 None
curr = head # 當前節點，初始為頭節點
while curr:
next_node = curr.next # 保存下一個節點
curr.next = prev # 將當前節點的 next 指針指向前一個節點
prev = curr # 將 prev 移動到當前節點
curr = next_node # 將 curr 移動到下一個節點
return prev # 當 curr 為 None 時，prev 就是反轉后的頭節點
# 案例
# 創建鏈表：1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
def print_linked_list(head):
while head:
print(head.val, end=" -> ")
head = head.next
print("None")
print("原始鏈表：", end="")
print_linked_list(head)
reversed_head = reverse_linked_list(head)
print("反轉后鏈表：", end="")
print_linked_list(reversed_head)3. 二分查找 (Binary Search)
題目描述： 給定一個有序整數數組 nums 和一個目標值 target，請你在該數組中搜索目標值。如果目標值存在返回它的下標，否則返回 -1。
二分查找是一種高效的搜索算法，適用于已排序的數組。其基本思想是：
- 找到數組的中間元素。
- 如果中間元素等于目標值，則返回中間元素的下標。
- 如果中間元素小于目標值，則在數組的右半部分繼續搜索。
- 如果中間元素大于目標值，則在數組的左半部分繼續搜索。
重復以上步驟，直到找到目標值或搜索范圍為空。
def binary_search(nums, target):
"""
在有序數組中查找目標值
Args:
nums: 有序整數數組
target: 目標值
Returns:
目標值的下標，如果不存在則返回 -1
"""
left, right = 0, len(nums) - 1# 初始化左右指針
while left <= right:
mid = (left + right) // 2# 計算中間元素的下標
if nums[mid] == target:
return mid # 找到目標值，返回下標
elif nums[mid] < target:
left = mid + 1# 目標值在右半部分，移動左指針
else:
right = mid - 1# 目標值在左半部分，移動右指針
return-1# 如果循環結束沒有找到目標值，返回 -1
# 案例
nums = [-1, 0, 3, 5, 9, 12]
target = 9
result = binary_search(nums, target)
print(f"數組：{nums}，目標值：{target}，結果：{result}") # 輸出：數組：[-1, 0, 3, 5, 9, 12]，目標值：9，結果：4
nums = [-1, 0, 3, 5, 9, 12]
target = 2
result = binary_search(nums, target)
print(f"數組：{nums}，目標值：{target}，結果：{result}") # 輸出：數組：[-1, 0, 3, 5, 9, 12]，目標值：2，結果：-14. 合并兩個有序鏈表 (Merge Two Sorted Lists)
題目描述： 將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。
解題思路：
我們可以創建一個新的鏈表，并通過比較兩個輸入鏈表的當前節點的值，將較小的節點添加到新鏈表中。
維護一個指向新鏈表尾部的指針 tail 和兩個指向輸入鏈表當前節點的指針 l1 和 l2。
比較 l1 和 l2 當前節點的值：
- 如果 l1 為空，將 l2 的剩余部分添加到新鏈表的尾部。
- 如果 l2 為空，將 l1 的剩余部分添加到新鏈表的尾部。
- 如果 l1.val <= l2.val，將 l1 的當前節點添加到新鏈表的尾部，并將 l1 指向下一個節點。
- 否則，將 l2 的當前節點添加到新鏈表的尾部，并將 l2 指向下一個節點。
重復以上步驟，直到兩個輸入鏈表都為空。為了方便操作，我們可以創建一個啞節點作為新鏈表的頭部。
def merge_two_lists(l1, l2):
"""
合并兩個有序鏈表
Args:
l1: 第一個有序鏈表的頭節點
l2: 第二個有序鏈表的頭節點
Returns:
合并后的有序鏈表的頭節點
"""
dummy = ListNode(0) # 創建一個啞節點作為新鏈表的頭部
tail = dummy # tail 指向新鏈表的尾部
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next # 移動 tail 指針
# 將剩余的鏈表添加到尾部
if l1:
tail.next = l1
elif l2:
tail.next = l2
return dummy.next # 返回啞節點的下一個節點，即合并后鏈表的頭節點
# 案例
# 創建鏈表1: 1 -> 2 -> 4
list1 = ListNode(1)
list1.next = ListNode(2)
list1.next.next = ListNode(4)
# 創建鏈表2: 1 -> 3 -> 4
list2 = ListNode(1)
list2.next = ListNode(3)
list2.next.next = ListNode(4)
print("鏈表1：", end="")
print_linked_list(list1)
print("鏈表2：", end="")
print_linked_list(list2)
merged_list = merge_two_lists(list1, list2)
print("合并后鏈表：", end="")
print_linked_list(merged_list)5. 有效的括號 (Valid Parentheses)
題目描述： 給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。
有效字符串需滿足：
- 左括號必須用相同類型的右括號閉合。
- 左括號必須以正確的順序閉合。
解題思路：
這道題可以使用棧（Stack）來解決。遍歷字符串中的每個字符：
- 如果遇到左括號（'(', '[', '{'），將其壓入棧中。
- 如果遇到右括號（')', ']', '}'），檢查棧是否為空。如果為空，則說明沒有對應的左括號，字符串無效。否則，彈出棧頂的元素，判斷它是否與當前的右括號匹配。如果不匹配，則字符串無效。
遍歷完字符串后，如果棧為空，則說明所有括號都正確閉合，字符串有效。否則，說明還有未閉合的左括號，字符串無效。
def is_valid(s):
"""
判斷字符串中的括號是否有效
Args:
s: 包含括號的字符串
Returns:
True 如果字符串有效，False 否則
"""
stack = [] # 創建一個空棧
mapping = {")": "(", "]": "[", "}": "{"} # 定義右括號和對應的左括號
for char in s:
if char in mapping: # 如果是右括號
top_element = stack.pop() if stack else'#'# 如果棧為空，pop會報錯，用 '#' 代替
if mapping[char] != top_element:
returnFalse# 棧頂元素與當前右括號不匹配，返回 False
else: # 如果是左括號，壓入棧中
stack.append(char)
returnnot stack # 如果棧為空，說明所有括號都正確閉合，返回 True
# 案例
s = "()"
result = is_valid(s)
print(f"字符串：'{s}'，是否有效：{result}") # 輸出：字符串：'()'，是否有效：True
s = "()[]{}"
result = is_valid(s)
print(f"字符串：'{s}'，是否有效：{result}") # 輸出：字符串：'()[]{}'，是否有效：True
s = "(]"
result = is_valid(s)
print(f"字符串：'{s}'，是否有效：{result}") # 輸出：字符串：'(]'，是否有效：False
s = "([)]"
result = is_valid(s)
print(f"字符串：'{s}'，是否有效：{result}") # 輸出：字符串：'([)]'，是否有效：False
s = "{[]}"
result = is_valid(s)
print(f"字符串：'{s}'，是否有效：{result}") # 輸出：字符串：'{[]}'，是否有效：True總結
掌握這些常見的算法題對于Python面試至關重要。通過理解每道題的解題思路、掌握相應的代碼實現，并進行大量的練習，將會更有信心應對面試中的算法挑戰。
