'분류 전체보기'에 해당되는 글 291건

Leetcode Problem:

• Minimum Number of Operations to Sort a Binary Tree by Level

Summary

• This is a solution for the problem of finding the minimum number of operations needed to make the values at each level of a binary tree strictly increasing.

Approach

• This solution uses a level-order traversal to store the node values at each level in a vector
• Then it sorts the node values at each level and checks for any swaps needed to make the values strictly increasing
• The solution keeps track of the number of swaps needed and returns the total number of swaps as the minimum number of operations.

Complexity

• O(n log n) where n is the number of nodes in the tree, due to the sorting operation at each level.

Explanation

• The solution first performs a level-order traversal of the tree and stores the node values at each level in a vector
• Then it sorts the node values at each level and checks for any swaps needed to make the values strictly increasing
• The solution keeps track of the number of swaps needed and returns the total number of swaps as the minimum number of operations.

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:
    vector equalLevelNode[100001];
    void traversal(TreeNode* root, int level){
        if(root == nullptr) return;
        equalLevelNode[level].push_back(root->val);
        traversal(root->left, level + 1);
        traversal(root->right, level + 1);
    }
    int minimumOperations(TreeNode* root) {
        traversal(root, 0);
        int ans = 0;
        for(int i = 0 ; i <= 100000; i++){
            if(equalLevelNode[i].size() == 0) break;
            unordered_map m;
            vector sorted;
            for(int j = 0 ; j < equalLevelNode[i].size(); j++){
                sorted.push_back(j);
            }
            sort(sorted.begin(), sorted.end(), [&](int a, int b){
                return equalLevelNode[i][a] < equalLevelNode[i][b];
            });
            for(int j = 0; j < sorted.size(); j++){
                m[sorted[j]] = j;
            }
            for(int j = 0; j < sorted.size(); j++){
                if(equalLevelNode[i][sorted[j]] != equalLevelNode[i][j]){
                    ans++;
                    int t = equalLevelNode[i][sorted[j]];
                    equalLevelNode[i][sorted[j]] = equalLevelNode[i][j];
                    equalLevelNode[i][j] = t;

                    sorted[m[j]] = sorted[j];
                    m[sorted[j]] = m[j];
                }
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Merge Two 2D Arrays by Summing Values

Summary

• Merge two sorted arrays of integers with unique ids, into one array sorted by id, respecting the conditions that only ids appearing in at least one array should be included and each id should be included only once with its value being the sum of the values of this id in the two arrays.

Approach

• The approach used is to first create a map where the keys are the ids and the values are the sums of the values of each id in the two arrays
• Then, we create a vector of vectors and iterate over the map, pushing back a vector for each key-value pair into the vector.

Complexity

• O(n + m) where n and m are the sizes of the two input arrays, because we are iterating over each element in both arrays once.

Explanation

• The solution starts by creating a map where the keys are the ids and the values are the sums of the values of each id in the two arrays
• This is done by iterating over the first array and adding the value of each id to the corresponding key in the map
• Then, we do the same for the second array
• After that, we create a vector of vectors and iterate over the map, pushing back a vector for each key-value pair into the vector
• This results in a vector of vectors where each inner vector contains an id and its corresponding sum, sorted by id in ascending order.

Solution Code:

class Solution {
public:
    vector> mergeArrays(vector>& nums1, vector>& nums2) {
        map m;
        for(int i = 0 ; i < nums1.size(); i++){
            int id = nums1[i][0];
            int v = nums1[i][1];
            m[id] += v;
        }
        for(int i = 0 ; i < nums2.size(); i++){
            int id = nums2[i][0];
            int v = nums2[i][1];
            m[id] += v;
        }
        vector> ans;
        for (auto iter : m){
            int id = iter.first;
            int v = iter.second;
            ans.push_back({id, v});
        }
        return ans;
    }
};

Leetcode Problem:

• Apply Operations to an Array

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

Leetcode Problem:

• Maximum Number of K-Divisible Components

Summary

• Given an undirected tree with n nodes, edges, values, and k, find the maximum number of components in any valid split of the tree such that the value of each connected component is divisible by k.

Approach

• This solution uses a depth-first search (DFS) traversal to explore the tree and find the maximum number of components
• It maintains two arrays, undirectAdj and directAdj, to store the adjacency list of the tree
• The solution also uses two flags, visited and visited2, to keep track of visited nodes during the traversal
• The traversal function is called recursively to explore the tree, and the solution updates the values of the nodes based on the divisibility of their sum by k.

Complexity

• O(n log n) due to the sorting of the leaf nodes in the leafs array.

Explanation

• The solution starts by building the adjacency list of the tree using the undirectAdj and directAdj arrays
• Then, it calls the traversal function to explore the tree and find the leaf nodes
• The traversal function uses a recursive approach to explore the tree, and it updates the values of the nodes based on the divisibility of their sum by k
• The solution maintains two arrays, leafs, to store the leaf nodes of the tree
• The solution iterates over the leaf nodes and updates their values based on the divisibility of their sum by k
• Finally, the solution returns the maximum number of components in any valid split of the tree.

Solution Code:

class Solution {
public:
    vector undirectAdj[30000];
    vector directAdj[30000];
    vector leafs[2];
    bool visited[30000];
    bool visited2[30000];
    int in[30000];
    int succeed = 0;
    void traversal(int root){
        visited[root] = true;
        int nextCnt = 0;
        for(int i = 0 ; i < undirectAdj[root].size(); i++){
            int next = undirectAdj[root][i];
            if(visited[next]){
                continue;
            }
            nextCnt++;
            directAdj[next].push_back(root);
            in[root]++;
            traversal(next);
        }
        if(nextCnt == 0){
            leafs[0].push_back(root);
        }
    }
    int maxKDivisibleComponents(int n, vector>& edges, vector& values, int k) {
        
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            undirectAdj[a].push_back(b);
            undirectAdj[b].push_back(a);
        }
        int root = 0;
        traversal(root);
        int leafIdx = 0;
        int ans = 0;
        bool end = false;
        while(true){
            leafs[leafIdx^1].clear();
            for(int i = 0 ; i < leafs[leafIdx].size(); i++){
                int cur = leafs[leafIdx][i];
                if(succeed >= n-1 && cur == root){
                    end = true;
                    break;
                }
                if(cur == root){
                    continue;
                }
                int next = directAdj[cur][0];
                if(visited2[cur]) continue;
                visited2[cur] = true;
                succeed++;
                if(values[cur] % k){ 
                    values[next] = (values[next] + values[cur]) % k;
                } else{
                    ans++;
                }
                in[next]--;
                if(in[next] == 0){
                    leafs[leafIdx^1].push_back(next);
                }
            }
            if(end) break;
            leafIdx ^= 1;
        }
        
        if(values[root] % k){
            return 1;
        } else{
            return ans + 1;
        }
    }
};

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