'2025/02'에 해당되는 글 176건

Leetcode Problem:

• Length of Longest Fibonacci Subsequence

Summary

• The problem is to find the length of the longest Fibonacci-like subsequence in a given strictly increasing array of positive integers.

Approach

• The solution uses a binary search approach to find the longest Fibonacci-like subsequence
• It first sorts the array and then uses a binary search to find the length of the longest Fibonacci-like subsequence.

Complexity

• O(n log n) due to the binary search and O(n^2) due to the nested loops in the combi function.

Explanation

• The solution starts by sorting the array
• Then it uses a binary search to find the length of the longest Fibonacci-like subsequence
• The binary search is performed by checking if a number exists in the array
• If it does, the function returns true, otherwise it returns false
• The function then uses a combi function to find the longest Fibonacci-like subsequence
• The combi function uses a depth-first search approach to find the longest Fibonacci-like subsequence
• It starts by adding the first two elements of the array to the selected vector and then recursively calls itself with the remaining elements of the array
• The function then checks if the length of the selected vector is greater than 2 and if the length of the selected vector plus 1 is equal to the next element in the array
• If it is, the function increments the depth and the ans variable
• The function then pops the last element from the selected vector and recursively calls itself with the remaining elements of the array
• The function continues this process until the depth is greater than 2 or the end of the array is reached
• The function then returns the ans variable, which represents the length of the longest Fibonacci-like subsequence.

Solution Code:

class Solution {
public:
    int ans = 0;
    bool checkNum(int n, vector& arr){
        int l = 0;
        int r = arr.size() - 1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(arr[mid] == n) return true;
            if(arr[mid] < n){
                l = mid + 1;
            } else{
                r = mid - 1;
            }
        }
        return false;
    }

    void combi(vector&arr, int cur, int depth, vector& selected){
        if(depth == 2){
            int a =  selected[0];
            int b =  selected[1];
            int cnt = 0;
            while(checkNum(a + b, arr)){
                int t = a + b;
                a = b;
                b = t;
                cnt++;
            }
            if(cnt >= 1){
                ans = max(ans, depth + cnt);
            }
            return;
        }

        for(int i = cur + 1; i < arr.size(); i++){
            selected.push_back(arr[i]);
            combi(arr, i, depth + 1, selected);
            selected.pop_back();
        }
    }
    int lenLongestFibSubseq(vector& arr) {
        vector selected;
        combi(arr, -1, 0, selected);
        return ans;
    }
};

Leetcode Problem:

• Reverse Odd Levels of Binary Tree

Summary

• Given the root of a perfect binary tree, reverse the node values at each odd level of the tree.

Approach

• The approach used is to first initialize a tree array with the values of the nodes in the binary tree
• Then, a recursive function is used to reverse the values at each odd level
• The function checks if the current index is greater than the maximum size, and if so, returns
• Otherwise, it checks if the level is odd, and if so, reverses the values at the current index and the next index
• Finally, the function is called recursively for the left and right subtrees.

Complexity

• O(n log n) where n is the number of nodes in the tree, due to the recursive calls and the reversal operation at each odd level.

Explanation

• The provided solution code first initializes a tree array with the values of the nodes in the binary tree using the init function
• Then, it calls the reverse function to reverse the values at each odd level
• The reverse function checks if the current index is greater than the maximum size, and if so, returns
• Otherwise, it checks if the level is odd, and if so, reverses the values at the current index and the next index
• Finally, the function is called recursively for the left and right subtrees
• The changeValue function is used to update the values of the nodes in the binary tree after reversing the values at each odd level.

Solution Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    const static int TREE_SIZE = (1<<14) + 1;
    int tree[TREE_SIZE];
    int maxSize = 0;
    void init(TreeNode* root, int idx){
        if(root == nullptr){
            return;
        }
        maxSize = (maxSize, idx);
        tree[idx] = root->val;
        init(root->left, idx*2);
        init(root->right, idx*2 + 1);
    }
    void reverse(int level, int idx){
        if(idx > maxSize) return;
        int idx2 = idx << 1;
        if(level & 1){
            int l = idx;
            int r = idx2 - 1;
            while(l < r){
                int t = tree[l];
                tree[l] = tree[r];
                tree[r] = t;
                l++;
                r--;
            }
        }
        reverse(level+1, idx2);
    }
    TreeNode* changeValue(TreeNode* root, int idx){
        if(root == nullptr) return nullptr;
        root->val = tree[idx];
        changeValue(root->left, idx*2);
        changeValue(root->right, idx*2 + 1);
        return root;
    }
    TreeNode* reverseOddLevels(TreeNode* root) {
        init(root, 1);
        reverse(0, 1);
        return changeValue(root, 1);
    }
};

Leetcode Problem:

• Max Chunks To Make Sorted

Summary

• Given an integer array representing a permutation of the integers in the range [0, n - 1], find the largest number of chunks we can make to sort the array.

Approach

• We use two pointers, one from the end of the array and one from the beginning, to track the maximum element seen so far in each chunk
• We also use a stack to store the elements of the current chunk
• The time complexity of this approach is O(n), where n is the length of the input array.

Complexity

• O(n)

Explanation

• We initialize a rightMin array to keep track of the maximum element seen so far in each chunk
• We iterate through the array from right to left, and for each element, we check if the stack is empty
• If it is, we push the current element onto the stack and set the rightMin value to the current index
• If the stack is not empty and the current element is less than the top of the stack, we push the current element onto the stack and set the rightMin value to the top of the stack
• If the current element is greater than or equal to the top of the stack, we set the rightMin value to the top of the stack
• We then iterate through the array from left to right, and for each element, we update the leftMax value to be the maximum of the current leftMax value and the current element
• We then check if the leftMax value is less than or equal to the rightMin value
• If it is, we increment the ans variable by 1
• Finally, we return the ans variable, which represents the largest number of chunks we can make to sort the array.

Solution Code:

class Solution {
public:
    int rightMin[10];
    vector st;
    int maxChunksToSorted(vector& arr) {
        int ans = 0;
        for(int i = arr.size()-1; i >= 0; i--){
            if(st.empty()){
                st.push_back(arr[i]);
                rightMin[i] = arr.size();
            } else if(arr[i] < st.back()){
                rightMin[i] = st.back();
                st.push_back(arr[i]);
            } else{
                rightMin[i] = st.back();
            }
        }
        int leftMax = 0;
        for(int i = 0 ; i < arr.size(); i++){
            leftMax = max(leftMax, arr[i]);
            if(leftMax <= rightMin[i]){
                ans++;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Final Prices With a Special Discount in a Shop

Summary

• Given an integer array prices where prices[i] is the price of the ith item in a shop, find the final price for each item considering a special discount.

Approach

• The solution uses a stack to keep track of the prices of items that have not been discounted yet
• It iterates through the prices array in reverse order, and for each item, it checks if there is a smaller item in the stack that can provide a discount
• If a discount is found, it is applied to the current item, and the updated price is pushed onto the stack
• If no discount is found, the current price is pushed onto the stack as is.

Complexity

• O(n), where n is the number of items in the prices array, because each item is processed once.

Explanation

• The solution uses a stack to efficiently find the smallest price that can provide a discount for each item
• It starts by iterating through the prices array in reverse order, and for each item, it checks if there is a smaller item in the stack that can provide a discount
• If a discount is found, it is applied to the current item, and the updated price is pushed onto the stack
• This process continues until the stack is empty, at which point the current item's price is pushed onto the stack as is
• This approach ensures that each item is processed only once and that the stack is always in the correct order to find the smallest price that can provide a discount.

Solution Code:

class Solution {
public:
    vector st;
    vector finalPrices(vector& prices) {
        for(int i = prices.size() - 1; i >= 0 ; i--){
            while(st.size() != 0 && st.back() > prices[i]){
                st.pop_back();
            }
            if(st.size() == 0){
                st.push_back(prices[i]);
            } else{
                prices[i] -= st.back();
                st.push_back(prices[i] + st.back());
            }
        }
        return prices;
    }
};

Leetcode Problem:

• Construct String With Repeat Limit

Summary

• Construct a new string using the characters of s such that no letter appears more than repeatLimit times in a row, and return the lexicographically largest possible string.

Approach

• The approach used is to first count the frequency of each character in s
• Then, we start with the largest possible character and keep adding it to the result string until we reach the repeatLimit limit
• If we encounter a character that is already at the limit, we remove the last occurrence of that character from the result string and replace it with the next character in the sorted order.

Complexity

• O(n log n) where n is the length of s, due to the sorting operation.

Solution Code:

class Solution {
public:
    vector arr;
    int charCnt[256];
    string repeatLimitedString(string s, int repeatLimit) {
        for(int i = 0 ; i < s.size(); i++){
            charCnt[s[i]]++;
        }
        for(int i = 'z'; i >= 'a'; i--){
            while(charCnt[i]--){
                arr.push_back(i);
            }
        }
        int repeat = 1;
        int beforeChar = arr[0];
        int j = 0;
        for(int i = 1 ; i < arr.size(); i++){
            if(beforeChar == arr[i]){
                repeat++;
            } else {
                repeat = 1;
                beforeChar = arr[i];
            }
            if(repeat > repeatLimit){
                if (j <= i){
                    j = i + 1;
                }
                while(j < arr.size() && beforeChar == arr[j]){
                    j++;
                }
                if(j >= arr.size()){
                    arr[i] = 0;
                    break;
                }
                char t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                beforeChar = arr[i];
                repeat = 1;
                j++;
            }
        }
        string ans = "";
        for(int i = 0 ; i < arr.size(); i++){
            if(arr[i] == 0) break;
            ans += arr[i];
        }
        return ans;
    }
};

Leetcode Problem:

• Final Array State After K Multiplication Operations I

Summary

• This solution performs k operations on the input array nums
• In each operation, it finds the minimum value in nums and replaces it with the minimum value multiplied by a given multiplier.

Approach

• The solution uses a min-heap data structure to efficiently find the minimum value in the array
• It first pushes all elements of the array into the heap
• Then, it performs k operations by popping the minimum element from the heap, multiplying it by the multiplier, and pushing it back into the heap
• This process is repeated k times to achieve the final state of the array.

Complexity

• O(k log n) where n is the size of the input array, as each operation involves popping from the heap and pushing back into the heap, which takes log n time, and k operations are performed.

Explanation

• The solution uses a min-heap to efficiently find the minimum element in the array
• The min-heap is implemented using a binary heap data structure
• The cmp function used to compare elements in the heap is defined as a lambda function that compares the indices of the elements in the array if the values are equal
• This ensures that the smallest index is always at the root of the heap
• The getFinalState function first pushes all elements of the input array into the heap
• Then, it performs k operations by popping the minimum element from the heap, multiplying it by the multiplier, and pushing it back into the heap
• This process is repeated k times to achieve the final state of the array.

Solution Code:

struct _node{
    int idx;
    int val;
};

template 
struct _heap{
    int size;
    T arr[101];
    function cmp;
    _heap(){
        size = 1;
    }
    void push(T a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && cmp(arr[idx >> 1], arr[idx])){
            T t = arr[idx >> 1];
            arr[idx >> 1] = arr[idx];
            arr[idx] = t;
            idx >>= 1;
        }
    }
    T pop(){
        T 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])){
                T t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else{
                break;
            }
        }

        return ret;
    }
};

class Solution {
public:
    _heap h;
    vector getFinalState(vector& nums, int k, int multiplier) {
        h.cmp = [&nums](int a, int b){
            if(nums[a] != nums[b]){
                return nums[a] > nums[b];
            }
            return a > b;
        };
        for(int i = 0 ; i < nums.size(); i++){
            h.push(i);
        }
        while(k--){
            int idx = h.pop();
            nums[idx] *= multiplier;
            h.push(idx);
        }
        return nums;
    }
};

Leetcode Problem:

• Maximum Average Pass Ratio

Summary

• Given a 2D array of classes and extra students, find the maximum average pass ratio after assigning the extra students.

Approach

• We use a max heap to store the classes, where the pass ratio of each class is used as the comparison key
• We start by pushing all classes into the heap
• Then, we pop the class with the lowest pass ratio and push a new class with the increased pass ratio until we have assigned all extra students
• Finally, we calculate the average pass ratio by summing the pass ratios of all classes and dividing by the number of classes.

Complexity

• O(n log n + m log n) where n is the number of classes and m is the number of extra students

Explanation

• The time complexity of the solution is O(n log n + m log n) because we push all classes into the heap in O(n log n) time and pop the class with the lowest pass ratio in O(log n) time, and we repeat this process m times
• The space complexity is O(n) because we store all classes in the heap.

Solution Code:

struct _node{
    int pass;
    int total;
};
struct _heap{
    _node arr[100002];
    int size;
    function cmp;
    _heap(){
        size = 1;
    }
    void push(_node a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && cmp(arr[idx/2], arr[idx])){
            _node t = arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = t;
            idx /= 2;
        }
    }
    _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], arr[j+1])){
                j++;
            }
            if(cmp(arr[i], arr[j])){
                _node t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else{
                break;
            }
        }
        return ret;
    }
    bool empty(){
        return size == 1;
    }
};
class Solution {
public:
    _heap h;
    double getRatio(_node classs){
        double pass = classs.pass;
        double total = classs.total;
        return pass / total;
    }
    double diffRatio(_node a){
        double ratio1 = getRatio(a);
        double ratio2 = getRatio({a.pass+1, a.total+1});
        return ratio2 - ratio1;
    }
    double maxAverageRatio(vector>& classes, int extraStudents) {
        h.cmp = [&](_node a, _node b) {
            double diffRatio1 = diffRatio(a);
            double diffRatio2 = diffRatio(b);
            return diffRatio1 < diffRatio2;
        };
        for(int i = 0 ; i < classes.size(); i++){
            h.push({classes[i][0], classes[i][1]});
        }
        while(extraStudents--){
            _node clas = h.pop();
            h.push({clas.pass+1, clas.total+1});
        }
        double sum = 0;
        while(!h.empty()){
            sum += getRatio(h.pop());
        }
        return sum / classes.size();
    }
};

Leetcode Problem:

• Maximum Absolute Sum of Any Subarray

Summary

• Given an integer array, find the maximum absolute sum of any subarray.

Approach

• Use two pointers to track the maximum and minimum prefix sum, then return the maximum of the two absolute values.

Complexity

• O(n) where n is the number of elements in the array

Explanation

• The solution works by iterating over the array twice, once to find the maximum prefix sum and once to find the minimum prefix sum
• The maximum prefix sum is updated whenever a positive number is encountered, and the minimum prefix sum is updated whenever a negative number is encountered
• The maximum of the two absolute values is then returned as the result.

Solution Code:

class Solution {
public:
    int maxAbsoluteSum(vector& nums) {
        int r = 0;
        int l = 0;
        int plusMax = 0;
        int prefixSum = 0;
        for(int num : nums){
            prefixSum += num;
            if(prefixSum < 0) prefixSum = 0;
            plusMax = max(plusMax, prefixSum);
        }

        int minusMin = 0;
        prefixSum = 0;
        for(int num:nums){
            prefixSum += num;
            if(prefixSum > 0) prefixSum = 0;
            minusMin = min(minusMin, prefixSum);
        }
        return plusMax > abs(minusMin) ? plusMax : abs(minusMin);
    }
};

Leetcode Problem:

• Number of Sub-arrays With Odd Sum

Summary

• Find the number of subarrays with an odd sum in a given array of integers.

Approach

• The solution uses a prefix sum approach to keep track of the current sum of the subarray
• It also uses two counters, evenCount and oddCount, to keep track of the number of subarrays with even and odd sums respectively
• The time complexity is O(n) where n is the size of the array.

Complexity

• O(n)

Explanation

• The solution iterates over the array and for each element, it checks if the prefix sum is odd or even
• If it's odd, it increments the oddCount and adds the evenCount to the answer
• If it's even, it increments the evenCount and adds the oddCount to the answer
• The answer is then taken modulo MOD to prevent overflow
• The solution returns the final answer.

Solution Code:

class Solution {
public:
    #define MOD 1000000007
    int numOfSubarrays(vector& arr) {
        
        long long prefixSum = 0;
        int evenCount = 1;
        int oddCount = 0;
        int ans = 0;
        for(int i = 0 ; i < arr.size(); i++){
            prefixSum += arr[i];

            if(prefixSum & 1){
                oddCount++;
                ans += evenCount;
            } else{
                evenCount++;
                ans += oddCount;
            }
            ans %= MOD;
        }
        return ans;
    }
};

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;
    }
};