題目資訊

題目編號: 1550
題目連結: Three Consecutive Odds
主題: Array

題目敘述

給定一個整數數組 $arr$，如果數組中存在三個連續的奇數，則返回 $true$。否則，返回 $false$。

範例 1:

輸入: arr = [2,6,4,1]
輸出: false
解釋: 沒有三個連續的奇數。

範例 2:

輸入: arr = [1,2,34,3,4,5,7,23,12]
輸出: true
解釋: [5, 7, 23] 是三個連續的奇數。

約束條件:

$1 \leq arr.length \leq 1000$
$1 \leq arr[i] \leq 1000$

直覺

這個問題是一個簡單的條件檢查，要求在整數數組中檢查是否存在三個連續的奇數。這一需求暗示我們需要對數組進行簡單的遍歷以計數連續奇數。如果在遍歷過程中遇到三個連續的奇數，我們可以立即確認它們的存在並返回 true；否則，如果遍歷完成而未找到這種模式，則返回 false。

解法

為了解決這個問題，我們從數組的末端開始迭代到開頭，同時維護一個名為 oddCount 的計數器來追踪遇到的連續奇數數量。我們使用以下方法：

初始化一個計數器 oddCount 為零。此計數器將有助於追踪連續的奇數。
從數組的尾端開始迭代，對於每一個元素 arr[i]，確定其奇偶性：
- 如果 arr[i] 是一個奇數，這可藉由條件 arr[i] & 1 判定（即對 arr[i] 進行與1的位元運算，對於奇數結果將為真），oddCount 增加一。
- 如果 arr[i] 是偶數，則將 oddCount 重置為零，因為連續的奇數序列被打斷。
在迭代過程中，如果 oddCount 在任何時候達到三，這意味著我們遇到了三個連續的奇數，則我們可以立即返回 true。
如果迴圈完成但從未達到三個連續奇數，則返回 false。

此方法有效利用位元運算的特性來確定數字的奇偶性，並確保通過線性掃描輸入數組達到最佳性能，使其適合最多1000個元素的約束。

程式碼

C++

class Solution {
public:
    bool threeConsecutiveOdds(vector<int>& arr) {
        int oddCount = 0; // 初始化一個計數器來計算連續奇數的數量

        // 從陣列的尾端遍歷到開頭
        for (int i = arr.size() - 1; i >= 0; i--) {
            // 使用位元運算檢查當前數字是否為奇數
            if (arr[i] & 1) {
                oddCount++; // 若為奇數，則遞增計數器
                if (oddCount >= 3) {
                    return true; // 若計數器達到3，則返回true
                }
            } else {
                oddCount = 0; // 若遇到偶數，則重置計數器
            }
        }
        
        return false; // 若未找到三個連續的奇數，則返回false
    }
};

Python

class Solution:
    def threeConsecutiveOdds(self, arr):
        oddCount = 0  # 初始化連續奇數的計數器

        # 從陣列的最後一個元素到第一個元素遍歷
        for i in range(len(arr) - 1, -1, -1):
            # 使用位元運算檢查當前數字是否為奇數
            if arr[i] & 1:
                oddCount += 1  # 奇數計數器加一
                if oddCount >= 3:
                    return True  # 若有三個連續奇數，返回True
            else:
                oddCount = 0  # 若遇到偶數則重置計數器

        return False  # 若未找到三個連續奇數則返回False

複雜度分析

時間複雜度: $O(n)$，因為該算法遍歷陣列一次，其中 $n$ 是陣列的大小。
空間複雜度: $O(1)$，因為該算法使用恆定數量的額外空間，與輸入大小無關，具體來說是用於儲存計數器 oddCount。

CS Note
En

Leetcode 1550. Three Consecutive Odds

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析