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