🔗 🟢 3038. Maximum Number of Operations With the Same Score I 1202

tags: `Biweekly Contest 124` `模擬(Simulation)`

題意

給定一個整數陣列 $nums$ ，如果 $nums$ 至少包含 $2$ 個元素，你可以執行以下操作：

選擇 $nums$ 中的 前兩個 元素並刪除它們，該次操作的分數為被刪除元素的和。

你的任務是找到可以執行的最大操作次數，使所有操作的得分相同，返回滿足上述條件的最大操作次數。

約束條件

$2 \leq \text{len}(nums) \leq 100$
$1 \leq nums[i] \leq 1000$

思路：模擬(Simulation)

題目確保了 $nums$ 至少包含 $2$ 個元素，因此可以先計算它們的和作為初始的目標得分。之後每次遍歷陣列的兩個元素，按照題意模擬即可。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 是陣列 $nums$ 的長度。
空間複雜度： $\mathcal{O}(1)$

寫法一

賽時寫法，比較直觀。

使用 $target$ 變數來記錄前兩個元素的和， $ans$ 變數紀錄操作次數，初始化為 $1$ ，表示最大操作次數至少為 $1$ 。然後從 $i=2$ 開始，每次檢查兩個元素的和是否等於 $target$ ，如果是則操作次數加一，否則跳出迴圈。

若從 $i=2$ 開始，由於每次要檢查 $i$ 和 $i+1$ 兩個元素，因此需要檢查 $i+1$ 是否超出範圍；也可以從 $i=3$ 開始，每次檢查 $i-1$ 和 $i$ ，這樣就不會有超出範圍的問題。

class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        n = len(nums)
        target = nums[0] + nums[1]
        ans = 1
        for i in range(2, n, 2):
            if i + 1 < n and nums[i] + nums[i+1] == target:
                ans += 1
            else:
                break
        return ans

class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int n = nums.size();
        int ans = 1, target = nums[0] + nums[1];
        for (int i = 2; i < n; i += 2){
            if (i + 1 < n && nums[i] + nums[i+1] == target) ans++;
            else break;
        }
        return ans;
    }
};

寫法二：省略 ans 變數

靈神提供的解法，省略了變數 $ans$ ，直接用下標 $i$ 來計算操作次數，優美且簡潔。

從 $i = 3$ 開始，每次檢查該元素與前面一個元素的和是否等於 $target$ ，如果不是則直接返回 $\lfloor \frac{i}{2} \rfloor$ ，否則繼續檢查下一對元素，直到結束，返回 $\lfloor \frac{n}{2} \rfloor$ 。

class Solution:
    def maxOperations(self, nums: List[int]) -> int:
        n = len(nums)
        target = nums[0] + nums[1]
        for i in range(3, n, 2):
            if nums[i-1] + nums[i] != target:
                return i // 2
        return n // 2

class Solution {
public:
    int maxOperations(vector<int>& nums) {
        int n = nums.size(), target = nums[0] + nums[1];
        for (int i = 3; i < n; i += 2){
            if (nums[i-1] + nums[i] != target) return i / 2;
        }
        return n / 2;
    }
};