阿里巴巴面試中的10個(gè)經(jīng)典算法題目及Python/Golang實(shí)現(xiàn)

阿里巴巴面試中的10個(gè)經(jīng)典算法題目及Python/Golang實(shí)現(xiàn)

引言

在準(zhǔn)備阿里巴巴等大型科技公司的技術(shù)面試時(shí)，深入理解并掌握一些常見的算法問題及其解決方案是非常重要的。這些題目不僅能夠幫助你提升編程技能，還能增強(qiáng)你的邏輯思維和問題解決能力。本文將介紹十個(gè)經(jīng)典的算法題目，并提供Python和Golang的實(shí)現(xiàn)代碼。

1. 兩數(shù)之和 (Two Sum)

題目描述：
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè)整數(shù)，并返回他們的數(shù)組下標(biāo)。

Python 實(shí)現(xiàn)：

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 實(shí)現(xiàn)：

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. 三數(shù)之和 (Three Sum)

題目描述：
給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a, b, c ，使得 a + b + c = 0 ？找出所有滿足條件且不重復(fù)的三元組。

Python 實(shí)現(xiàn)：

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 實(shí)現(xiàn)：

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. 最長(zhǎng)無重復(fù)字符的子串 (Longest Substring Without Repeating Characters)

題目描述：
給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。

Python 實(shí)現(xiàn)：

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 實(shí)現(xiàn)：

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 緩存機(jī)制 (Least Recently Used Cache)

題目描述：
設(shè)計(jì)并實(shí)現(xiàn)一個(gè) LRU (最近最少使用) 緩存機(jī)制。它應(yīng)該支持以下操作：獲取數(shù)據(jù) get(key) 和寫入數(shù)據(jù) put(key, value)。當(dāng)緩存達(dá)到其容量上限時(shí)，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值。

Python 實(shí)現(xiàn)：

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 實(shí)現(xiàn)：

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. 合并兩個(gè)有序鏈表 (Merge Two Sorted Lists)

題目描述：
將兩個(gè)升序鏈表合并為一個(gè)新的升序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

Python 實(shí)現(xiàn)：

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 實(shí)現(xiàn)：

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)

題目描述：
給定一個(gè)二叉樹，找出其最大深度。二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。

Python 實(shí)現(xiàn)：

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 實(shí)現(xiàn)：

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. 有效的括號(hào) (Valid Parentheses)

題目描述：
給定一個(gè)只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。有效字符串需滿足：左括號(hào)必須用相同類型的右括號(hào)閉合；左括號(hào)必須以正確的順序閉合。

Python 實(shí)現(xiàn)：

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 實(shí)現(xiàn)：

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. 反轉(zhuǎn)鏈表 (Reverse Linked List)

題目描述：
反轉(zhuǎn)一個(gè)單鏈表。

Python 實(shí)現(xiàn)：

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 實(shí)現(xiàn)：

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)

題目描述：
假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？

Python 實(shí)現(xiàn)：

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 實(shí)現(xiàn)：

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. 旋轉(zhuǎn)圖像 (Rotate Image)

題目描述：
給定一個(gè) n × n 的二維矩陣表示一個(gè)圖像，將圖像順時(shí)針旋轉(zhuǎn) 90 度。你需要原地旋轉(zhuǎn)圖像，即不使用額外的空間來完成這個(gè)任務(wù)。

Python 實(shí)現(xiàn)：

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 實(shí)現(xiàn)：

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
        }
    }
}

結(jié)語

以上就是阿里巴巴面試中常見的十個(gè)經(jīng)典算法題目及其Python和Golang實(shí)現(xiàn)。通過理解和練習(xí)這些題目，你可以更好地準(zhǔn)備技術(shù)面試，同時(shí)也能夠提高自己的編程技巧。希望這篇文章對(duì)你有所幫助，祝你在面試中取得優(yōu)異成績(jī)！

附錄

如果你有任何疑問或需要進(jìn)一步的幫助，請(qǐng)隨時(shí)留言討論！

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容