🔗 🟢 3184. Count Pairs That Form a Complete Day I 1150

tags: Weekly Contest 402 暴力法(Brute Force) 雜湊表(Hash Table) 模運算(Modulo)

本題與 3185. Count Pairs That Form a Complete Day II [🔗解題紀錄] 相同，只差在數字範圍，建議直接使用下一題的解法。

題意

給定一個整數陣列 hours\text{hours}。返回有多少對 (i,j)(i, j) 滿足 i<ji < j 且 hours[i]+hours[j]\text{hours}[i] + \text{hours}[j] 為 2424 的整數倍數。

約束條件

  • 1≤n=hours.length≤1001 \leq n = \text{hours.length} \leq 100
  • 1≤hours[i]≤1091 \leq \text{hours}[i] \leq 10^9

思路：暴力法(Brute Force)

對於陣列中的每個元素 hours[i]\text{hours}[i]，我們遍歷其後面的所有元素 hours[j]\text{hours}[j]，其中 j>ij > i。然後，我們計算這兩個數的和 hours[i]+hours[j]\text{hours}[i] + \text{hours}[j] 是否是 2424 的整數倍數。如果符合條件，將答案加一。

由於 nn 最大為 100100，所以 O(n2)\mathcal{O}(n^2) 的暴力法是可以接受的。關於如何優化，請參考下一題。

複雜度分析

  • 時間複雜度：O(n2)\mathcal{O}(n^2) ，其中 nn 為陣列的長度。
  • 空間複雜度：O(1)\mathcal{O}(1) 。
1
2
3
4
5
6
7
8
9
class Solution:
    def countCompleteDayPairs(self, hours: List[int]) -> int:
        n = len(hours)
        ans = 0
        for i in range(n):
            for j in range(i+1, n):
                if (hours[i] + hours[j]) % 24 == 0:
                    ans += 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int countCompleteDayPairs(vector<int>& hours) {
        int n = hours.size(), ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i+1; j < n; j++)
                if ((hours[i] + hours[j]) % 24 == 0)
                    ans++;
        return ans;
    }
};

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, backlight, photo background,

(1girl, solo), skirt, shirt, black hair, bow, school uniform, white shirt, ponytail, flower, short sleeves, pleated skirt, outdoors, bowtie, plaid, plaid skirt, field, flower field,

A girl in a white shirt and green plaid skirt standing in a field of green plants and white flowers, with a transparent greenhouse in the background, bright sunny day, fresh and natural atmosphere,