'2025/02/25'에 해당되는 글 6건

Leetcode Problem:

• Continuous Subarrays

Summary

• This problem requires finding the total number of continuous subarrays in a given array where the absolute difference between any two elements in the subarray is less than or equal to 2.

Approach

• The approach used here is to use two heaps, a min heap and a max heap, to keep track of the indices of the smallest and largest elements in the current window
• The window is expanded by pushing the next element into the heaps and shrinking the window by popping elements from the heaps until the difference between the largest and smallest elements exceeds 2
• The total number of continuous subarrays is then calculated by summing up the size of the window for each possible window size.

Complexity

• O(n log n) due to the heap operations

Solution Code:

class Solution {
public:
    struct _heap{
        function cmp;
        int arr[100002];
        int size;
        _heap(){
            size = 1;
        }
        void push(int a){
            arr[size++] = a;
            int idx = size - 1;
            while(idx > 1 && !cmp(arr[idx/2], arr[idx])){
                int t = arr[idx/2];
                arr[idx/2] = arr[idx];
                arr[idx] = t;
                idx/=2;
            }
        }
        int pop(){
            int ret = arr[1];
            arr[1] = arr[--size];
            int i = 1;
            while(true){
                int j = i * 2;
                if(j >= size) break;
                if(j+1 < size && !cmp(arr[j], arr[j+1])){
                    j++;
                }
                if(!cmp(arr[i], arr[j])){
                    int t = arr[i];
                    arr[i] = arr[j];
                    arr[j] = t;
                    i = j;
                } else{
                    break;
                }
            }
            return ret;
        }
        int top(){
            return arr[1];
        }
        bool empty(){
            return size == 1;
        }
    };
    long long continuousSubarrays(vector& nums) {
        long long sum = 0;
        long long l = 0;
        long long r = 0;
        _heap minHeap;
        _heap maxHeap;
        minHeap.cmp = [&nums](int a, int b) { return nums[a] < nums[b] ;};
        maxHeap.cmp = [&nums](int a, int b) { return nums[a] > nums[b] ;};
        while(r < nums.size()){
            minHeap.push(r);
            maxHeap.push(r);
            
            while(l < r && nums[maxHeap.top()] - nums[minHeap.top()] > 2){
                l++;
                while(!minHeap.empty() && minHeap.top() < l){
                    minHeap.pop();
                }
                while(!maxHeap.empty() && maxHeap.top() < l){
                    maxHeap.pop();
                }
            }
            sum += r - l + 1;
            r++;
        }
        return sum;
    }
};

Leetcode Problem:

• Find Score of an Array After Marking All Elements

Summary

• Given an array of positive integers, apply a scoring algorithm where the smallest unmarked integer is chosen, added to the score, and its adjacent elements are marked
• The process is repeated until all elements are marked.

Approach

• A priority queue (implemented as a heap) is used to store the unmarked elements along with their indices
• The heap is updated after each iteration to reflect the newly marked elements
• The algorithm iterates until the heap is empty, at which point the final score is returned.

Complexity

• O(n log n) due to the heap operations (insertion and deletion)

Solution Code:

struct _node{
    int idx;
    int val;
};

bool _cmp(_node a, _node b){
    if(a.val != b.val) return a.val < b.val;
    return a.idx < b.idx;
}

struct _heap{
    _node arr[100002];
    int size;
    _heap(){
        size = 1;
    }
    void push(_node a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && _cmp(arr[idx], arr[idx/2])){
            _node tmp = arr[idx/2];
            arr[idx/2] = arr[idx];
            arr[idx] = tmp;
            idx >>= 1;
        }
    }
    _node pop(){
        _node ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i*2;
            if(j >= size){
                break;
            }
            if(j+1 < size && _cmp(arr[j+1], arr[j])){
                j++;
            }
            if(_cmp(arr[j], arr[i])){
                _node t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;

            } else {
                break;
            }
        }

        return ret;

    }
    bool empty(){
        return size == 1;
    }
    _node peek(){
        return arr[1];
    }
};

class Solution {
public:
    _heap h;
    _heap remove;
    bool removed[100002];
    long long findScore(vector& nums) {
        for(int i = 0 ; i < nums.size(); i++){
            h.push({i, nums[i]});
        }
        long long sum = 0;
        while(!h.empty()){
            while(!h.empty() && h.peek().val == remove.peek().val && 
                                h.peek().idx == remove.peek().idx){
                remove.pop();
                h.pop();
            }
            if(h.empty()) break;
            _node nod = h.pop();
            cout << nod.val << endl;
            sum += nod.val;
            if(nod.idx -1 >= 0 && !removed[nod.idx-1]){
                removed[nod.idx-1] = true;
                remove.push({nod.idx-1, nums[nod.idx-1]});
            }
            if(nod.idx+1 < nums.size()  && !removed[nod.idx+1]){
                removed[nod.idx+1] = true;
                remove.push({nod.idx+1, nums[nod.idx+1]});
            }
        }
        return sum;
    }
};

Leetcode Problem:

• Take Gifts From the Richest Pile

Summary

• The problem requires to find the number of gifts remaining after k seconds, where each second, the maximum pile is chosen and its size is reduced to the floor of its square root.

Approach

• A heap data structure is used to store the number of gifts in each pile
• The pop operation is used to choose the maximum pile and reduce its size to the floor of its square root
• The process is repeated for k seconds.

Complexity

• O(n log n) due to the heap operations, where n is the number of piles.

Explanation

• The provided solution code first initializes a heap with the number of gifts in each pile
• Then, it enters a loop that runs for k seconds
• In each iteration, it pops the maximum pile from the heap, reduces its size to the floor of its square root, and pushes it back into the heap
• Finally, it calculates the total number of gifts remaining by summing up the sizes of all piles in the heap.

Solution Code:

struct _heap{
    int arr[1002];
    int size;
    _heap(){
        size = 1;
    }
    void push(int a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && arr[idx] > arr[idx/2]){
            int t = arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = t;
            idx/=2;
        }
    }
    int pop(){
        int ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if(j>= size) break;
            if(j+1 < size && arr[j] < arr[j+1]){
                j++;
            }
            if(arr[i] < arr[j]){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else {
                break;
            }
        }


        return ret;
    }
};

class Solution {
public:
    _heap h;
    long long pickGifts(vector& gifts, int k) {
        for(int i = 0 ; i < gifts.size(); i++){
            h.push(gifts[i]);
        }
        while(k--){
            int gift = h.pop();
            int i = 1;
            while(i*i <= gift) i++;
            i--;
            h.push(i);
        }
        long long sum = 0;
        for(int i = 1; i < h.size; i++){
            sum += h.arr[i];
        }
        return sum;
    }
};

Leetcode Problem:

• Maximum Beauty of an Array After Applying Operation

Summary

• Given a 0-indexed array nums and a non-negative integer k, find the maximum possible beauty of the array after applying the operation any number of times.

Approach

• This problem can be solved by using a two-pointer technique
• The idea is to maintain two pointers, one at the beginning and one at the end of the array
• The pointer at the end is used to track the maximum possible beauty
• The pointer at the beginning is used to track the minimum possible value in the current window
• If the difference between the value at the end pointer and k is less than or equal to the sum of the value at the beginning pointer and k, it means that we can extend the current window to the right
• Otherwise, we move the beginning pointer to the right.

Complexity

• O(n log n) due to the sorting operation, where n is the size of the input array.

Explanation

• The solution starts by sorting the input array in ascending order
• Then it initializes two pointers, l and r, to 0
• It also initializes a variable ans to 1
• The while loop continues until the end pointer r reaches the end of the array
• Inside the loop, it checks if the difference between the value at the end pointer and k is less than or equal to the sum of the value at the beginning pointer and k
• If the condition is true, it means that we can extend the current window to the right, so it increments the end pointer r and updates the ans variable with the maximum of the current ans and the difference between the end pointer r and the beginning pointer l
• Otherwise, it increments the beginning pointer l
• Finally, the solution returns the ans variable, which represents the maximum possible beauty of the array.

Solution Code:

class Solution {
public:
    int maximumBeauty(vector& nums, int k) {
        sort(nums.begin(), nums.end());
        int l = 0;
        int r = 0;
        int ans = 1;
        while(r < nums.size()){
            if(nums[r] - k <= nums[l] + k){
                r++;
                ans = max(ans, r - l);
            } else{
                l++;
            }
        }
        
        
        return ans;
    }
};

Leetcode Problem:

• Find Longest Special Substring That Occurs Thrice I

Summary

• Find the length of the longest special substring of a given string that occurs at least thrice, or return -1 if no such substring exists.

Approach

• Use binary search to find the longest special substring that occurs at least thrice
• The approach involves checking for the presence of a special character (a single character) in the string and counting its occurrences
• If a special character is found to occur at least thrice, the approach updates the binary search range to focus on the longer special substrings.

Complexity

• O(n log m) where n is the length of the string and m is the range of possible special characters (26 lowercase English letters)

Explanation

• The solution uses binary search to efficiently find the longest special substring that occurs at least thrice
• The binary search range is initially set to the entire string, and the approach iteratively narrows down the range to focus on longer special substrings
• The approach checks for the presence of a special character in the string and counts its occurrences
• If a special character is found to occur at least thrice, the approach updates the binary search range to focus on the longer special substrings
• The process is repeated until the longest special substring that occurs at least thrice is found, or the binary search range becomes empty.

Solution Code:

class Solution {
public:
    int maximumLength(string s) {
        int ans = -1;
        int l = 1;
        int r = s.size()-2;
        
        while(l <= r){
            int mid = (l + r) >> 1;
            bool success = false;
            for(char i = 'a'; i <= 'z'; i++){
                int k = 0;
                int specialCnt = 0;
                for(int j = 0; j < s.size(); j++){
                    if(s[j] == i){
                        k++;
                    } else{
                        k = 0;
                    }
                    if(k == mid){
                        k--;
                        specialCnt++;
                        if(specialCnt >= 3){
                            success = true;
                            break;
                        }
                    }
                }
                if(success) break;
            }
            if(success){
                l = mid + 1;
                ans = mid;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Special Array II

Summary

• Check if every pair of adjacent elements in an array contains numbers with different parity.

Approach

• Use a prefix sum array to store the parity of each element in the array
• Then for each query, check if the difference between the parity at the end and start indices is equal to the number of elements in the query
• If it is, the subarray is special.

Complexity

• O(n + q) where n is the size of the array and q is the number of queries.

Explanation

• The solution uses a prefix sum array to store the parity of each element in the array
• The parity is 1 if the number is odd and 0 if the number is even
• The prefix sum array is updated by adding 1 to the parity if the current number is even and the previous number is odd, or if the current number is odd and the previous number is even
• Then for each query, the difference between the parity at the end and start indices is calculated
• If the difference is equal to the number of elements in the query, the subarray is special
• Otherwise, it is not special.

Solution Code:

class Solution {
public:
    vector isArraySpecial(vector& nums, vector>& queries) {
        vector ans;
        vector memo;
        memo.push_back(1);
        for(int i = 1 ; i < nums.size(); i++){
            int num = memo.back();
            if(nums[i] %2 == nums[i-1] %2){
                memo.push_back(num);
            } else{
                memo.push_back(num+1);
            }
        }
        for(int i =  0; i < queries.size(); i++){
            int a = queries[i][0];
            int b = queries[i][1];
            if(b- a == memo[b] - memo[a]){
                ans.push_back(true);
            } else {
                ans.push_back(false);
            }
        }
        return ans;
    }
};