刷 LeetCode 常用的 Golang 小技巧

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)。
• 空間複雜度： 根據數據量動態分配內存。

好處

1. 高效性： 提供 O(1) 的查找與更新效率，適用於需頻繁操作的題目。
2. 靈活性： 支援多種操作，可用於統計頻率、記錄索引等場景。
3. 簡潔性： 語法簡單，易於理解和使用。

4. 使用 for 取代 while

Golang 沒有專門的 while 語法，但我們可以使用 for 模擬其行為，這在實現條件迴圈時非常實用。

// 使用 for 模擬 while
x := 0
for x < 5 {
    fmt.Println(x)
    x++
}

效果

• 功能一致： for 可以模擬所有的 while 場景。
• 語法統一： Golang 中只有一種迴圈語法，簡化了程式結構。

好處

1. 簡潔統一： 避免學習和使用多種語法。
2. 靈活性高： 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 的特性。