阿里巴巴面试中的10个经典算法题目及Python/Golang实现
引言
在准备阿里巴巴等大型科技公司的技术面试时，深入理解并掌握一些常见的算法问题及其解决方案是非常重要的。这些题目不仅能够帮助你提升编程技能，还能增强你的逻辑思维和问题解决能力。本文将介绍十个经典的算法题目，并提供Python和Golang的实现代码。
1. 两数之和 (Two Sum)
题目描述：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
Python 实现：
def two_sum(nums, target):
num_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_map:
return [num_map[complement], i]
num_map[num] = i
return []
Golang 实现：
func twoSum(nums []int, target int) []int {
numMap := make(map[int]int)
for i, num := range nums {
complement := target - num
if j, ok := numMap[complement]; ok {
return []int{j, i}
}
numMap[num] = i
}
return nil
}
2. 三数之和 (Three Sum)
题目描述：
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a, b, c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
Python 实现：
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
for left < right and nums[left] == nums[left+1]:
left += 1
for left < right and nums[right] == nums[right-1]:
right -= 1
left, right = left + 1, right - 1
return result
Golang 实现：
func threeSum(nums []int) [][]int {
sort.Ints(nums)
var result [][]int
for i := 0; i < len(nums)-2; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
left, right := i+1, len(nums)-1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum < 0 {
left++
} else if sum > 0 {
right--
} else {
result = append(result, []int{nums[i], nums[left], nums[right]})
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
left++
right--
}
}
}
return result
}
3. 最长无重复字符的子串 (Longest Substring Without Repeating Characters)
题目描述：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
Python 实现：
def length_of_longest_substring(s: str) -> int:
char_map = {}
left = maxLength = 0
for right in range(len(s)):
if s[right] in char_map:
left = max(left, char_map[s[right]] + 1)
char_map[s[right]] = right
maxLength = max(maxLength, right - left + 1)
return maxLength
Golang 实现：
func lengthOfLongestSubstring(s string) int {
charMap := make(map[byte]int)
left, maxLength := 0, 0
for right := 0; right < len(s); right++ {
if index, ok := charMap[s[right]]; ok {
left = max(left, index+1)
}
charMap[s[right]] = right
maxLength = max(maxLength, right-left+1)
}
return maxLength
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
4. LRU 缓存机制 (Least Recently Used Cache)
题目描述：
设计并实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get(key) 和写入数据 put(key, value)。当缓存达到其容量上限时，它应该在写入新数据之前删除最久未使用的数据值。
Python 实现：
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
del self.cache[key]
elif len(self.cache) >= self.capacity:
self.cache.popitem(last=False)
self.cache[key] = value
Golang 实现：
type LRUCache struct {
cache map[int]*list.Element
list *list.List
capacity int
}
type entry struct {
key int
value int
}
func Constructor(capacity int) LRUCache {
return LRUCache{
cache: make(map[int]*list.Element),
list: list.New(),
capacity: capacity,
}
}
func (this *LRUCache) Get(key int) int {
if elem, ok := this.cache[key]; ok {
this.list.MoveToBack(elem)
return elem.Value.(*entry).value
}
return -1
}
func (this *LRUCache) Put(key int, value int) {
if elem, ok := this.cache[key]; ok {
this.list.Remove(elem)
delete(this.cache, key)
}
if len(this.cache) >= this.capacity {
oldest := this.list.Remove(this.list.Front())
delete(this.cache, oldest.(*entry).key)
}
entry := &entry{key, value}
this.cache[key] = this.list.PushBack(entry)
}
5. 合并两个有序链表 (Merge Two Sorted Lists)
题目描述：
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
Python 实现：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_two_lists(l1, l2):
dummy = ListNode(0)
current = dummy
while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 or l2
return dummy.next
Golang 实现：
type ListNode struct {
Val int
Next *ListNode
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
current := dummy
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
current.Next = l1
l1 = l1.Next
} else {
current.Next = l2
l2 = l2.Next
}
current = current.Next
}
if l1 != nil {
current.Next = l1
} else {
current.Next = l2
}
return dummy.Next
}
6. 二叉树的最大深度 (Maximum Depth of Binary Tree)
题目描述：
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
Python 实现：
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def max_depth(root):
if root is None:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
Golang 实现：
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
7. 有效的括号 (Valid Parentheses)
题目描述：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合。
Python 实现：
def is_valid(s: str) -> bool:
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack
Golang 实现：
func isValid(s string) bool {
stack := []rune{}
mapping := map[rune]rune{')': '(', '}': '{', ']': '['}
for _, char := range s {
if closing, ok := mapping[char]; ok {
if len(stack) == 0 || stack[len(stack)-1] != closing {
return false
}
stack = stack[:len(stack)-1]
} else {
stack = append(stack, char)
}
}
return len(stack) == 0
}
8. 反转链表 (Reverse Linked List)
题目描述：
反转一个单链表。
Python 实现：
def reverse_list(head):
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
Golang 实现：
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
current := head
for current != nil {
nextNode := current.Next
current.Next = prev
prev = current
current = nextNode
}
return prev
}
9. 爬楼梯 (Climbing Stairs)
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
Python 实现：
def climb_stairs(n: int) -> int:
if n <= 2:
return n
first, second = 1, 2
for _ in range(3, n + 1):
third = first + second
first, second = second, third
return second
Golang 实现：
func climbStairs(n int) int {
if n <= 2 {
return n
}
first, second := 1, 2
for i := 3; i <= n; i++ {
third := first + second
first, second = second, third
}
return second
}
10. 旋转图像 (Rotate Image)
题目描述：
给定一个 n × n 的二维矩阵表示一个图像，将图像顺时针旋转 90 度。你需要原地旋转图像，即不使用额外的空间来完成这个任务。
Python 实现：
def rotate(matrix):
n = len(matrix)
for layer in range(n // 2):
first, last = layer, n - layer - 1
for i in range(first, last):
offset = i - first
top = matrix[first][i]
matrix[first][i] = matrix[last - offset][first]
matrix[last - offset][first] = matrix[last][last - offset]
matrix[last][last - offset] = matrix[i][last]
matrix[i][last] = top
Golang 实现：
func rotate(matrix [][]int) {
n := len(matrix)
for layer := 0; layer < n/2; layer++ {
first, last := layer, n-layer-1
for i := first; i < last; i++ {
offset := i - first
top := matrix[first][i]
matrix[first][i] = matrix[last-offset][first]
matrix[last-offset][first] = matrix[last][last-offset]
matrix[last][last-offset] = matrix[i][last]
matrix[i][last] = top
}
}
}
结语
以上就是阿里巴巴面试中常见的十个经典算法题目及其Python和Golang实现。通过理解和练习这些题目，你可以更好地准备技术面试，同时也能够提高自己的编程技巧。希望这篇文章对你有所帮助，祝你在面试中取得优异成绩！
附录
-
推荐阅读：
-
工具列表：
- PyCharm（Python IDE）
- GoLand（Golang IDE）
- Visual Studio Code（多语言编辑器）
如果你有任何疑问或需要进一步的帮助，请随时留言讨论！
