Leetcode Problem:
Summary
- The problem requires applying operations to a given array of non-negative integers, where in each operation, if the current element is equal to the next element, the current element is multiplied by 2 and the next element is set to 0
- The operations are applied sequentially, and after all operations, the 0's are shifted to the end of the array.
Approach
- The approach used is to iterate over the array, apply the operations, and then shift the 0's to the end
- The operations are applied sequentially, and the 0's are shifted to the end by adding them to the end of the array.
Complexity
- O(n), where n is the size of the array, because each element is visited once.
Explanation
- The solution code starts by initializing an index to 0 and an empty array to store the result
- It then enters a while loop that continues until the index is greater than or equal to the size of the array
- Inside the loop, it skips the 0's by incrementing the index until it finds a non-zero element
- If the current element is equal to the next element, it multiplies the current element by 2 and increments the index
- It then pushes the current element to the result array and increments the index
- After the while loop, it shifts the 0's to the end of the array by adding them to the end of the array
- Finally, it returns the result array.
Solution Code:
class Solution {
public:
vector applyOperations(vector& nums) {
int idx = 0;
vector ans;
while(idx < nums.size()){
while(idx < nums.size() && nums[idx] == 0){
idx++;
}
if(idx >= nums.size()) break;
int num = nums[idx];
if((idx + 1) < nums.size() && (nums[idx] == nums[idx+1])){
num <<= 1;
idx++;
}
ans.push_back(num);
idx++;
}
int ansSize = ans.size();
while(ansSize < nums.size()){
ans.push_back(0);
ansSize++;
}
return ans;
}
};
class Solution {
public:
vector applyOperations(vector& nums) {
int idx = 0;
vector ans;
while(idx < nums.size()){
while(idx < nums.size() && nums[idx] == 0){
idx++;
}
if(idx >= nums.size()) break;
int num = nums[idx];
if((idx + 1) < nums.size() && (nums[idx] == nums[idx+1])){
num <<= 1;
idx++;
}
ans.push_back(num);
idx++;
}
int ansSize = ans.size();
while(ansSize < nums.size()){
ans.push_back(0);
ansSize++;
}
return ans;
}
};
'알고리즘' 카테고리의 다른 글
| Minimum Number of Operations to Sort a Binary Tree by Level (0) | 2025.03.03 |
|---|---|
| Merge Two 2D Arrays by Summing Values (0) | 2025.03.02 |
| Maximum Number of K-Divisible Components (0) | 2025.03.01 |
| Length of Longest Fibonacci Subsequence (0) | 2025.02.27 |
| Reverse Odd Levels of Binary Tree (0) | 2025.02.27 |
짬뽕얼큰하게
