Shopee

TODO: Leetcode 200 (Medium)

LeetCode 200. Number of Islands (島嶼的數量) 難易度: Medium

  • 題目描述：給定一個由 '1'（陸地）和 '0'（水域）組成的二維矩陣，計算矩陣中有多少個相互連接的陸地區域。
  • 解題思路：使用BFS或DFS遍歷矩陣，將相鄰的陸地標記為已訪問，並計算有多少個相互連接的陸地區域。
  • 連結：https://leetcode.com/problems/number-of-islands

TODO: Leetcode 215 Kth Largest Element in an Array (Medium)

Leetcode 215. Kth Largest Element in an Array (數組中的第K個最大元素) 難易度: Medium

  • 題目描述: 給定一個無序的整數數組 nums，找出其中第 k 大的元素。

  • 解題思路: 可以使用快速選擇算法（Quick Select）來解決這個問題。該算法的基本思想是選擇一個輸入數組的基準元素，將數組分為兩個部分，一部分是大於基準元素的數字，另一部分是小於基準元素的數字。根據這兩部分的大小關係，可以遞迴地在其中一部分繼續尋找第 k 大的元素。

  • 連結: https://leetcode.com/problems/kth-largest-element-in-an-array

heapq 是什麼，具體怎麼操作

在 Golang 中，heap 包提供了堆（heap）的實現，並且包含了一些常用的操作。堆是一種特殊的數據結構，它可以用來快速查找和操作最大或最小的元素。

heap 包中的 heap.Interface 接口定義了堆的操作方法，其中包括：

  • Len() int：返回堆的元素個數。
  • Less(i, j int) bool：返回索引 i 的元素是否小於索引 j 的元素。
  • Swap(i, j int)：交換索引 i 和索引 j 的元素。
  • Push(x interface{})：將元素 x 添加到堆中。
  • Pop() interface{}：從堆中彈出並返回最小（或最大）的元素。

Golang 中的 heap 包提供了 Push 和 Pop 方法，可以使用 heap.Push 向堆中添加元素，使用 heap.Pop 從堆中彈出最小（或最大）的元素。

下面是一個示例，展示了如何使用 heap 包來操作堆：

package main

import (
    "container/heap"
    "fmt"
)

// 自定義一個整數切片型別
type IntHeap []int

// 實現 heap.Interface 接口的方法

func (h IntHeap) Len() int {
    return len(h)
}

func (h IntHeap) Less(i, j int) bool {
    return h[i] < h[j]
}

func (h IntHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func main() {
    // 創建一個空的堆
    h := &IntHeap{}

    // 添加元素到堆中
    heap.Push(h, 3)
    heap.Push(h, 1)
    heap.Push(h, 4)
    heap.Push(h, 2)

    // 從堆中彈出最小的元素
    min := heap.Pop(h)

    fmt.Println("Min element:", min)
}

在這個示例中，我們創建了一個自定義的 IntHeap 型別，並實現了 heap.Interface 接口的方法。然後，我們創建了一個空的堆 h，並使用 heap.Push 方法向堆中添加元素，最後使用 heap.Pop 方法彈出最小的元素。

請注意，這個示例中的堆是小根堆，如果想要使用大根堆，只需在 Less 方法中修改比較運算符的方向即可。

heapq是Python中的一個模組，提供了對堆數據結構的支持。堆是一種特殊的二叉樹結構，具有以下特點：

  1. 堆是一個完全二叉樹，即除了最後一層，其他層都是滿的，而且最後一層的節點儘量靠左排列。
  2. 堆中每個節點的值都大於或等於（最大堆）或小於或等於（最小堆）其子節點的值。 樹上所有父節點的值都小於等於他的子節點的值，這種堆叫做最小堆；樹上所有父節點的值都大於等於他的子節點的值，這種堆叫做最大堆。

heapq模組提供了一系列函數用於對堆進行操作，包括創建堆、插入元素、彈出元素等。以下是一些常用的heapq函數：

  1. heapify(iterable): 將可迭代對象轉換為一個堆，時間複雜度為O(n)。
  2. heappush(heap, item): 將元素插入堆中，並保持堆的特性。
  3. heappop(heap): 彈出並返回堆中最小（或最大）的元素，同時保持堆的特性。
  4. heappushpop(heap, item): 先將元素插入堆中，然後彈出並返回堆中最小（或最大）的元素。
  5. heapreplace(heap, item): 彈出並返回堆中最小（或最大）的元素，然後將元素插入堆中。

使用heapq模組，你可以方便地實現堆排序、優先隊列等常見算法和數據結構。具體的操作步驟包括創建一個列表作為堆，然後使用相應的函數進行操作。例如，要創建一個最小堆並將元素插入其中，可以按照以下步驟：

import heapq

# 創建一個空堆
heap = []

# 向堆中插入元素
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)

# 彈出並返回堆中最小的元素
smallest = heapq.heappop(heap)
print(smallest)  # 輸出：1

hash set 怎麼實作怎麼處理 collision 細節 (probing, self balanced binary search tree)

Hash Set（哈希集合）通常使用散列函數將元素映射到哈希表的索引位置上。在哈希表中，碰撞（collision）是指不同的元素被映射到相同的索引位置上的情況。 碰撞可能發生，因為散列函數的輸入空間可能大於哈希表的大小，這就造成多個元素映射到同一個索引位置的情況。

處理碰撞的方法有多種，其中包括開放定址法（probing）和使用自平衡二叉搜索樹（self-balanced binary search tree）。

  1. 開放定址法（Probing）：當發生碰撞時，開放定址法通過在哈希表中的其他位置進行尋找，直到找到一個空的位置將元素插入其中。常見的開放定址法有線性探測（linear probing）、二次探測（quadratic probing）和雙重散列（double hashing）。這些方法都是基於哈希表的特性，依次查找鄰近的位置，直到找到一個可用的空位置。

  2. 線性探測的特點是，如果哈希表的某個位置已經被佔用，則會依次查找下一個位置，直到找到一個空的位置。這可能導致連續的元素被存儲在哈希表的相鄰位置上，稱為聚集（clustering）現象。聚集可能會導致查找性能的下降，因為聚集越多，需要查找的位置越多。

  3. 二次探測（Quadratic probing）是一種在雜湊表中解決碰撞（collision）的技術。當發生碰撞時，它使用二次函數來探測下一個可用的插槽。與線性探測不同，二次探測使用二次函數計算下一個要檢查的插槽。探測序列是通過在每次迭代中以二次值增加探測步長來生成的。

二次探測公式通常表示為：

hash(key, i) = (hash(key) + c1 * i + c2 * i^2) % table_size

其中，hash(key) 是鍵的雜湊值，i 是探測步長，c1 和 c2 是常數，table_size 是雜湊表的大小。

通過使用二次探測，我們可以減少線性探測可能出現的聚集現象。但是，在選擇 c1 和 c2 的值時需要小心，以確保最終可以探測到所有插槽並完整地探索整個雜湊表。 請注意，具體的實現細節可能因所使用的編程語言或數據結構而異。

  • 雙重散列（Double hashing。它與線性探測和二次探測不同，使用兩個雜湊函數來計算下一個可用的插槽位置。

當發生碰撞時，雙重散列使用兩個不同的雜湊函數來計算下一個插槽位置，直到找到一個空槽或符合特定條件的槽。這兩個雜湊函數通常被稱為 hash1(key) 和 hash2(key)。 雙重散列的探測序列可以通過以下方式計算：

hash(key, i) = (hash1(key) + i * hash2(key)) % table_size

其中，hash1(key) 是第一個雜湊函數，hash2(key) 是第二個雜湊函數，i 是探測步長，table_size 是雜湊表的大小。

雙重散列的主要優勢是能夠更好地分散碰撞，減少聚集現象。通過適當選擇兩個不同的雜湊函數，可以有效地解決碰撞並提高查找效率。 需要注意的是，實現雙重散列時需要選擇合適的雜湊函數和探測步長，以確保探測序列能夠遍歷整個雜湊表並找到空槽。

  1. 自平衡二叉搜索樹（Self-Balanced Binary Search Tree = red-black tree）：在碰撞發生時，將具有相同索引的元素存儲在二叉搜索樹中。自平衡二叉搜索樹（如平衡二叉樹、紅黑樹）可以保持樹的平衡，並提供高效的插入、查找和刪除操作。通過使用自平衡二叉搜索樹來處理碰撞，可以確保元素的插入和查找操作的平均時間複雜度保持在O(log n)。

開放定址法對於存儲較小的數據集和快速插入操作可能更有效， 而自平衡二叉搜索樹則對於存儲大型數據集和快速查找操作更適用。

需要注意的是，碰撞的發生是不可避免的，因此在實現哈希集合時，必須適當地處理碰撞情況，以確保數據的完整性和正確性。

像解釋 rehash 機制，能不能做得更快

rehash（重新哈希）是一種動態調整哈希表大小的機制，用於處理哈希碰撞（collision）的情況。 當哈希表中的項目數目增加到一個預定的閾值時，就會觸發重新哈希操作。

重新哈希的過程通常包括以下步驟：

  1. 創建一個新的、更大的哈希表，它的大小通常是原哈希表的兩倍或更大。
  2. 遍歷原哈希表中的每個桶（bucket），將其中的項目重新計算哈希值，並放入新的哈希表的對應桶中。
  3. 調整新哈希表的參數，如閾值、桶的數量等。

重新哈希的目的是為了減少哈希碰撞，提高哈希表的效能。通過擴大哈希表的大小，可以使每個桶中的項目數量減少，從而減少碰撞的發生概率。 同時，重新哈希還可以平均分佈項目到新的桶中，提高查找和插入操作的效率。

為了加快重新哈希的速度，可以考慮以下方法：

  1. 預分配空間：在創建哈希表時，可以事先分配足夠大的空間，以減少頻繁的重新哈希操作。這樣可以減少重新哈希的次數和時間開銷。
  2. 增量重新哈希：將重新哈希操作分成多個小步驟，在每個步驟中只處理一部分項目，從而分散計算的負載，減少單次重新哈希的時間。
  3. 並行處理：在多核或分佈式環境中，可以將重新哈希操作分配給多個線程或節點同時進行處理，以加快整體的重新哈希速度。
  4. 優化哈希函數：選擇一個高效的哈希函數可以減少碰撞的發生概率，從而減少重新哈希的頻率。

array 找所有的 triplet 的 sum 使得他們的 sum 是 k 的倍數

要找出所有的三元組（triplet），使其總和為 k 的倍數，可以使用以下方法：

  1. 排序：首先對給定的數組進行排序，這樣可以更方便地進行後續操作。
  2. 遍歷組合：使用三個嵌套的循環來遍歷所有可能的三元組的組合。假設索引變量為 i、j 和 k，則遍歷範圍為 i 從 0 到 n-3，j 從 i+1 到 n-2，k 從 j+1 到 n-1。這樣可以保證遍歷所有不同的三元組。
  3. 計算總和：在每次遍歷時，計算三元組的總和。如果總和是 k 的倍數，則將這個三元組添加到結果列表中。
  4. 處理重複結果：由於排序後，可能會出現重複的三元組。為了避免重複，需要在遍歷時檢查當前的數字是否和前一個數字相同，如果相同則跳過。
func FindTriplets(arr []int, target int) [][]int {
    result := [][]int{}
    n := len(arr)
    for i := 0; i < n-2; i++ {
        for j := i + 1; j < n-1; j++ {
            for k := j + 1; k < n; k++ {
        // 為了避免重複，需要在遍歷時檢查當前的數字是否和前一個數字相同，如果相同則跳過
                if k > j+1 && arr[k] == arr[k-1] {
                    continue
                }
                if (arr[i]+arr[j]+arr[k])%target == 0 {
                    result = append(result, []int{arr[i], arr[j], arr[k]})
                }
            }
        }
    }
    return result
}

這個算法的時間複雜度是 O(n^3)，其中 n 是數組的長度。如果數組很大，效率可能會比較低。 在實際應用中，可以考慮使用更高效的算法來解決這個問題，如使用哈希表或優化的雙指針方法。

  • input: [('a', 'b'), ('c', 'd'), ('b', 'e')] output: [['a', 'b', 'e'], ['c', 'd']] 找出同一個 group，且 output 是要 follow input 的 order e.g., a > b > e

  • 第一題 leetcode 上沒有，叫你弄出一個 wave array 在 odd position 上的數字要 > even position 上的數字 input 是 unique 數字 [2, 4, 5, 1, 3, 6] output 任一種 valid 的 [2, 5, 4, 6, 1, 3]

  • 第二題 leetcode179
  • hard (leetcode 632)
© Kimi Tsai all right reserved.            Updated : 2023-07-12 09:04:53

results matching ""

    No results matching ""

    results matching ""

      No results matching ""