36. Valid Sudoku

給定一個 9x9 的數獨板 (2D 數組)，請判斷該數獨是否有效。數獨部分空白的格子用 '.' 表示。

數獨驗證需滿足以下三個條件：

1. 每一行 (row) 中不能有重複的數字。
2. 每一列 (column) 中不能有重複的數字。
3. 每一個 3x3 的小方塊中不能有重複的數字。

解題思路：
為了判斷數獨的有效性，可以利用 HashSet 來存儲每一行、每一列以及每一個 3x3 小方塊中已經出現過的數字。具體步驟如下：

1. 創建三個資料結構：

• rows：儲存每一行中出現過的數字。
• cols：儲存每一列中出現過的數字。
• boxes：儲存每個 3x3 小方塊中出現過的數字。

2. 遍歷整個 9x9 數獨：

• 當前元素若不為 '.'，則檢查以下三個條件：
  • 當前元素是否已存在於該行 (rows[row]) 中。
  • 當前元素是否已存在於該列 (cols[col]) 中。
  • 當前元素是否已存在於對應的 3x3 小方塊 (boxes[box_index]) 中。
• 如果任何一個條件不滿足，則數獨無效，返回 False* 。

class Solution:
    def isValidSudoku(board):
        # 用於儲存每行、每列、每個3x3方塊的出現數字
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

        # 遍歷整個9x9的數獨板
        for row in range(9):
            for col in range(9):
                num = board[row][col]

                # 如果當前元素為空 ('.')，則跳過
                if num == '.':
                    continue

                # 計算當前元素屬於哪個3x3方塊
                box_index = (row // 3) * 3 + col // 3

                # 檢查該元素是否在當前行、列或方塊中出現過
                if (num in rows[row] or
                    num in cols[col] or
                    num in boxes[box_index]):
                    return False

                # 將當前元素加入對應的行、列、方塊中
                rows[row].add(num)
                cols[col].add(num)
                boxes[box_index].add(num)

        # 如果遍歷完所有元素且無違規情況，返回True
        return True

128. Longest Consecutive Sequence

給定一個未排序的整數數組 nums，找出其中最長的連續元素序列（連續數列）的長度，要求算法的時間複雜度為 O(n)。

建立 HashSet：

將數組中的所有元素加入到 HashSet 中，以去除重複元素並提高查找效率。
遍歷 HashSet：

對每個元素 num 進行檢查，確定它是否為一個連續序列的開頭。
判斷條件：若 num - 1 不在 HashSet 中，則 num 為連續序列的起點。
計算當前序列的長度：

解題思路：
這道題目要求找到最長的連續序列，並且時間複雜度需要達到 O(n)。要達到這個要求，我們可以使用 HashSet 來進行優化。通過 HashSet 的查找效率 O(1)，我們能夠快速確認某個元素是否存在，從而避免重複計算。

體解題步驟如下：

1. 建立 HashSet：
   • 將數組中的所有元素加入到 HashSet 中，以去除重複元素並提高查找效率。
2. 遍歷 HashSet：
   • 對每個元素 num 進行檢查，確定它是否為一個連續序列的開頭。
   • 判斷條件：若 num - 1 不在 HashSet 中，則 num 為連續序列的起點。
3. 計算當前序列的長度：
   • 從當前 num 開始，依次檢查 num + 1、num + 2、num + 3... 是否存在於 HashSet 中，直到不再存在為止。
     *計算序列的長度，並更新最大連續序列長度。
4. 返回結果：
   *返回最大連續序列的長度。

def longestConsecutive(nums):
# 使用 HashSet 去除重複元素並便於查找
num_set = set(nums)
longest_streak = 0

class Solution:
    # 遍歷 HashSet 中的每個元素
    for num in num_set:
        # 只從連續序列的起點開始計算長度
        if num - 1 not in num_set:
            current_num = num
            current_streak = 1

            # 繼續計算當前序列的長度
            while current_num + 1 in num_set:
                current_num += 1
                current_streak += 1

            # 更新最大連續序列長度
            longest_streak = max(longest_streak, current_streak)
    
    return longest_streak