[LeetCode] 2460. Apply Operations to an Array

2460. Apply Operations to an Array

• Hardness: \(\color{green}\textsf{Easy}\)
• Ralated Topics: Array、Simulation
• \(\color{blue}\textsf{Weekly Contest 318}\)

一、題目

You are given a 0-indexed array nums of size n consisting of non-negative integers. You need to apply n - 1 operations to this array where, in the ith operation (0-indexed), you will apply the following on the ith element of nums:

• If nums[i] == nums[i + 1], then multiply nums[i] by 2 and set nums[i + 1] to 0. Otherwise, you skip this operation. After performing all the operations, shift all the 0’s to the end of the array.
• For example, the array [1,0,2,0,0,1] after shifting all its 0’s to the end, is [1,2,1,0,0,0]. Return the resulting array.
• Note that the operations are applied sequentially, not all at once.

Example 1:

• Input: nums = [1,2,2,1,1,0]
• Output: [1,4,2,0,0,0]
• Explanation: We do the following operations:

• i = 0: nums[0] and nums[1] are not equal, so we skip this operation.
• i = 1: nums[1] and nums[2] are equal, we multiply nums[1] by 2 and change nums[2] to 0. The array becomes [1,4,0,1,1,0].
• i = 2: nums[2] and nums[3] are not equal, so we skip this operation.
• i = 3: nums[3] and nums[4] are equal, we multiply nums[3] by 2 and change nums[4] to 0. The array becomes [1,4,0,2,0,0].
• i = 4: nums[4] and nums[5] are equal, we multiply nums[4] by 2 and change nums[5] to 0. The array becomes [1,4,0,2,0,0].
  After that, we shift the 0’s to the end, which gives the array [1,4,2,0,0,0].

• Input: nums = [0,1]
• Output: [1,0]
• Explanation: No operation can be applied, we just shift the 0 to the end.

Constraints:

• 2 <= nums.length <= 2000
• 0 <= nums[i] <= 1000

二、分析

• 照題目的指示做兩件事：
  1. 將前後重複的數字，把前者乘二，後者歸零。
  2. 利用 Two Pointer 的技巧，將零全部丟到後面。

三、解題

1. Two Pointer

• Time complexity: \(O(n)\)
• Space complexity: \(O(1)\)

vector<int> applyOperations(vector<int>& nums) {
    for (int i = 0; i < nums.size()-1; i++) {
        if (nums[i] == 0) continue;
        if (nums[i] == nums[i+1]) {     // 將前後重複的數字加到前者
            nums[i] *= 2;
            nums[i+1] = 0;
        }
    }
    int i = 0, j = 0;
    while (i < nums.size()) {
        if (nums[i] != 0) {         // 將零全部移到後面
            nums[j++] = nums[i++];
        } else {
            i++;
        }
    }
    while (j < nums.size()) {
        nums[j++] = 0;
    }
    return nums;
}

回目錄 Catalog