LeetCode 是程式設計師鍛煉演算法能力的重要平台,而 Golang 作為高效的語言之一,在解題時需要靈活運用其特性和小技巧來提升效率。以下將介紹一些刷 LeetCode 時常用的 Golang 小技巧,並分析其效果與好處。
1. 使用 map[int]int
解決問題
在解題過程中,map[int]int
是一種非常實用的數據結構,特別是在需要快速查找元素或進行頻率統計時。雖然 Golang 中沒有內建的 set
結構,但我們可以使用 map[int]bool
模擬。
宣告與使用方法
// 宣告 map[int]int
counts := make(map[int]int)
// 插入與更新元素
counts[1]++
counts[2] += 3
// 查詢元素
if val, exists := counts[3]; exists {
fmt.Println("Value:", val)
}
// 刪除元素
delete(counts, 2)
效果
- 時間複雜度: 查找、插入和刪除操作均為 O(1)。
- 空間複雜度: 根據數據量動態分配內存。
好處
- 高效性: 提供 O(1) 的查找與更新效率,適用於需頻繁操作的題目。
- 靈活性: 支援多種操作,可用於統計頻率、記錄索引等場景。
- 簡潔性: 語法簡單,易於理解和使用。
2. 使用 slice
實作堆疊(Stack)
Golang 中沒有內建的堆疊結構,因此我們需要透過 slice
來實作。這在處理深度優先搜尋(DFS)或括號匹配等問題中十分常見。
實作方法
// 初始化 stack
stack := []int{}
// Push 操作
stack = append(stack, 5) // 將元素 5 壓入堆疊
// Pop 操作
if len(stack) > 0 {
top := stack[len(stack)-1] // 取得堆疊頂部元素
stack = stack[:len(stack)-1] // 移除堆疊頂部元素
}
// Peek 操作
if len(stack) > 0 {
top := stack[len(stack)-1] // 取得堆疊頂部元素但不移除
}
效果
- 時間複雜度: Push 和 Pop 操作均為 O(1)。
- 空間複雜度: 根據使用需求動態分配內存。
好處
- 模擬真實堆疊行為: 使用簡單語法實現經典的 LIFO(後進先出)邏輯。
- 高效性: 利用
slice
的內存管理,無需額外實作數據結構。 - 適配多樣場景: 適用於 DFS、括號檢查等需要堆疊操作的題目。
3. 使用 copy
高效複製切片
在處理需要拷貝切片的問題時,Golang 提供內建的 copy
函數,可以高效地完成此操作。
// 原始切片
original := []int{1, 2, 3, 4, 5}
// 創建新切片並拷貝
copySlice := make([]int, len(original))
copy(copySlice, original)
fmt.Println("Original:", original)
fmt.Println("Copy:", copySlice)
效果
- 時間複雜度: 查找、插入和刪除操作均為 O(1)。
- 空間複雜度: 根據數據量動態分配內存。
好處
- 高效性: 提供 O(1) 的查找與更新效率,適用於需頻繁操作的題目。
- 靈活性: 支援多種操作,可用於統計頻率、記錄索引等場景。
- 簡潔性: 語法簡單,易於理解和使用。
4. 使用 for
取代 while
Golang 沒有專門的 while
語法,但我們可以使用 for
模擬其行為,這在實現條件迴圈時非常實用。
// 使用 for 模擬 while
x := 0
for x < 5 {
fmt.Println(x)
x++
}
效果
- 功能一致:
for
可以模擬所有的while
場景。 - 語法統一: Golang 中只有一種迴圈語法,簡化了程式結構。
好處
- 簡潔統一: 避免學習和使用多種語法。
- 靈活性高:
for
的條件控制可以完全覆蓋while
的需求。
5. 處理鏈結串列(Linked List)的小技巧
在處理 Linked List 相關題目時,可以藉由畫圖幫助理解 Linked List 的行為 。
舉例來說若有List結構如 "prev -> first -> second -> Next",若需要交換first, second node,可透過以下操作。
定義與操作
type ListNode struct {
Val int
Next *ListNode
}
// 交換鏈結串列中成對的節點
func swapPairs(head *ListNode) *ListNode {
dummy := &ListNode{Next: head}
prev := dummy
for head != nil && head.Next != nil {
first := head
second := head.Next
// 交換節點
prev.Next = second
// prev -> second, first -> second -> Next
first.Next = second.Next
// prev -> second, first -> Next
second.Next = first
// prev -> second -> first -> Next
// 移動指針到下一對節點
prev = first
head = first.Next
}
return dummy.Next
}
重點解釋:交換 first
和 second
節點:
prev.Next = second
- 將
prev
的Next
指向second
,即prev.Next = second
。
目前狀態:prev -> second, first -> second -> Next。
first.Next = second.Next
- 將
first
的Next
指向second
的Next
,即first.Next = second.Next
。
目前狀態:prev -> second, first -> Next。
second.Next = first
- 將
second
的Next
指向first
,即second.Next = first
。
目前狀態:prev -> second -> first -> Next。
結語
在使用 Golang 刷 LeetCode 時,掌握 map[int]int
、slice
堆疊、多重返回值、defer
、copy
、變數交換(Swap)、鏈結串列操作以及使用 for
模擬 while
等技巧,能夠有效提升解題效率與程式可讀性。透過熟悉這些小技巧,我們可以更快速地解決問題,並從中學習到更多 Golang 的特性。