'2025/02/24'에 해당되는 글 11건

Leetcode Problem:

• Most Profitable Path in a Tree

Summary

• The problem is to find the maximum net income that Alice can have if she travels towards the optimal leaf node in an undirected tree.

Approach

• The approach used is to use a depth-first search (DFS) traversal to find the optimal leaf node
• The DFS traversal is performed in two phases: first, to find the optimal leaf node for Bob, and second, to find the maximum net income for Alice
• The optimal leaf node for Bob is found by traversing the tree from node 0 and updating the amount array accordingly
• The maximum net income for Alice is then found by traversing the tree from the optimal leaf node and updating the sum variable accordingly.

Complexity

• O(n log n) due to the sorting of the amount array

Explanation

• The solution code first initializes the adjacency list and visited arrays
• It then defines two helper functions: goBobAndUpdateAmount and dfs
• The goBobAndUpdateAmount function performs the DFS traversal from node 0 to find the optimal leaf node for Bob, while the dfs function performs the DFS traversal from the optimal leaf node to find the maximum net income for Alice
• The solution code then calls the goBobAndUpdateAmount function to find the optimal leaf node for Bob, and then calls the dfs function to find the maximum net income for Alice
• The maximum net income for Alice is then returned as the result.

Solution Code:

class Solution {
    vector adj[100001];
    bool visited[100001] = {false,};
    bool visited2[100001] = {false,};
    bool isLeaf[100001] = {false,};
    int ans = -1000000001;
public:

    int goBobAndUpdateAmount(int node, int depth, int bob, vector& amount){
        if(visited[node]) return 100001;
        if(node == bob){
            amount[node] = 0;
            return depth;
        }
        visited[node] = true;
        int distanceBob = 100001;
        for(int i = 0 ; i < adj[node].size(); i++){
            int next = adj[node][i];
            distanceBob = goBobAndUpdateAmount(next, depth + 1, bob, amount);
            if(distanceBob == 100001) continue;
            if(depth > (distanceBob/2)){
                amount[node] = 0;
            } 
            if(depth == (distanceBob/2) && distanceBob %2 == 0){
                amount[node]/=2;
            }
            break;
        }
        return distanceBob;
    }
    void dfs(int node, int sum, vector& amount){
        if(visited2[node]) return;
        visited2[node] = true;
        sum += amount[node];
        if(isLeaf[node] && ans < sum){
            ans = sum;
        }
        for(int i = 0 ; i < adj[node].size(); i++){
            int next = adj[node][i];
            dfs(next, sum, amount);
        }
    }
    int mostProfitablePath(vector>& edges, int bob, vector& amount) {
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        for(int i = 1; i <= edges.size(); i++){
            if(adj[i].size() == 1) isLeaf[i] = true;
        }
        goBobAndUpdateAmount(0, 0, bob, amount);
        
        dfs(0, 0, amount);
        return ans;
    }
};

Leetcode Problem:

• Two Best Non-Overlapping Events

Summary

• Given a 2D array of events where each event has a start time, end time, and value, find the maximum sum of two non-overlapping events.

Approach

• The approach is to first sort the events by their start time, then use dynamic programming to find the maximum sum of two non-overlapping events
• We also use a suffix maximum array to store the maximum value that can be obtained by attending the events up to each index.

Complexity

• O(n log n) due to the sorting of events, where n is the number of events.

Solution Code:

class Solution {
public:
    int maxTwoEvents(vector>& events) {
        int n = events.size();
        
        sort(events.begin(), events.end(), [](const vector& a, const vector& b) {
            return a[0] < b[0];
        });
        
        vector suffixMax(n);
        suffixMax[n - 1] = events[n - 1][2];
        
        for (int i = n - 2; i >= 0; --i) {
            suffixMax[i] = max(events[i][2], suffixMax[i + 1]);
        }
        
        int maxSum = 0;
        
        for (int i = 0; i < n; ++i) {
            int left = i + 1, right = n - 1;
            int nextEventIndex = -1;
            
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (events[mid][0] > events[i][1]) {
                    nextEventIndex = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            if (nextEventIndex != -1) {
                maxSum = max(maxSum, events[i][2] + suffixMax[nextEventIndex]);
            }
            
            maxSum = max(maxSum, events[i][2]);
        }
        
        return maxSum;
    }
};

Leetcode Problem:

• Minimum Limit of Balls in a Bag

Summary

• Find the minimum possible penalty after performing operations on bags of balls.

Approach

• Binary search approach to find the minimum possible penalty
• The idea is to perform binary search on the possible maximum number of balls in a bag
• The binary search is performed on the range [1, max balls in a bag]
• For each mid value, it checks if the number of operations required to divide all bags into smaller bags is less than or equal to maxOperations
• If it is, then the minimum possible penalty is updated and the search space is narrowed down to the lower half of the range
• If not, the search space is narrowed down to the upper half of the range.

Complexity

• O(n log m) where n is the number of bags and m is the maximum number of balls in a bag.

Explanation

• The solution uses a binary search approach to find the minimum possible penalty
• The binary search is performed on the possible maximum number of balls in a bag, which is represented by the variable mid
• For each mid value, it checks if the number of operations required to divide all bags into smaller bags is less than or equal to maxOperations
• If it is, then the minimum possible penalty is updated and the search space is narrowed down to the lower half of the range
• If not, the search space is narrowed down to the upper half of the range
• This process is repeated until the minimum possible penalty is found.

Solution Code:

class Solution {
public:
    
    
    int minimumSize(vector& nums, int maxOperations) {
        int _max = 0;
        for(int i = 0 ; i < nums.size(); i++){
            if (_max < nums[i]){
                _max = nums[i];
            }
        }
        int l = 1; 
        int r = _max;
        int ans = _max;
        while(l <= r){
            int mid = l + (r - l)/2;
            cout << mid << endl;
            int operation = maxOperations;
            bool success = true;
            for(int i = 0 ; i < nums.size(); i++){
                if(mid < nums[i]){
                    operation -= ((nums[i] + mid - 1) / mid) - 1;
                }
                if(operation < 0){
                    success = false;
                    break;
                }
            }
            if(success){
                r = mid -1;
                ans = mid;
            } else{
                l= mid + 1;
            }

        }        

        return ans;
    }
};

Leetcode Problem:

• Maximum Number of Integers to Choose From a Range I

Summary

• Find the maximum number of integers that can be chosen from the range [1, n] without exceeding maxSum and without being in the banned array.

Approach

• The approach used is to first create a boolean array ban to mark the banned numbers, then create a vector nums to store the available numbers, and finally use two pointers to find the maximum sum that does not exceed maxSum.

Complexity

• O(n + banned.length) where n is the range [1, n] and banned.length is the number of banned numbers

Explanation

• The code first initializes a boolean array ban to mark the banned numbers and a vector nums to store the available numbers
• Then it iterates over the banned numbers and marks them in the ban array
• After that, it iterates over the range [1, n] and adds the available numbers to the nums vector
• Finally, it uses two pointers to find the maximum sum that does not exceed maxSum by iterating over the nums vector and adding the current number to the sum
• If the sum exceeds maxSum, it breaks the loop and returns the number of available numbers that were added to the sum.

Solution Code:

class Solution {
public:
    vector nums;
    bool ban[10001];
    int maxCount(vector& banned, int n, int maxSum) {
        for(int i = 0 ; i < banned.size(); i++){
            ban[banned[i]] = true;
        }
        for(int i = 1; i <= n; i++){
            if(ban[i]) continue;
            nums.push_back(i);
        }
        int sum = 0;
        int ans = 0;
        for(int i = 0 ; i < nums.size(); i++){
            sum += nums[i];
            if(sum > maxSum) break;
            ans++;
        }
        return ans;
    }
};

Leetcode Problem:

• Move Pieces to Obtain a String

Summary

• Check if a string can be transformed into another string by moving pieces (L, R, _) a certain number of times.

Approach

• This solution uses a two-pointer approach to iterate over both strings simultaneously
• It checks for the next available position for each piece in both strings and moves them accordingly
• If a piece cannot be moved to its next position, it returns false
• If all pieces can be moved to their next positions, it checks if both strings have been fully traversed and returns true if so, otherwise false.

Complexity

• O(n), where n is the length of the input strings.

Explanation

• The solution defines two helper functions, `nextCharIdx`, to find the next available position for each piece in both strings
• It then iterates over both strings using two pointers, `idx1` and `idx2`, which start at the beginning of each string
• It checks if the current positions in both strings match, and if they do, it moves the pieces to the next position
• If a piece cannot be moved to its next position, it returns false
• If all pieces can be moved to their next positions, it checks if both strings have been fully traversed and returns true if so, otherwise false.

Solution Code:

class Solution {
public:
    int nextCharIdx(string& str, int idx){
        for(int i = idx; i < str.size(); i++){
            if(str[i] == 'L' || str[i] == 'R') return i;
        }
        return str.size();
    }
    bool canChange(string start, string target) {
        int idx1, idx2;
        idx1 = idx2 = 0;
        while(true){
            idx1 = nextCharIdx(start, idx1);
            idx2 = nextCharIdx(target, idx2);
            if(idx1 == start.size() || idx2 == target.size()){       
                break;
            }
            if(start[idx1] != target[idx2]) return false;
            if(start[idx1] == 'L'){
                if(idx1 < idx2){
                    return false;
                }
            }
            if(start[idx1] == 'R'){
                if(idx1 > idx2){
                    return false;
                }
            }
            idx1++;
            idx2++;
        }
        if(idx1 == start.size() && idx2 == target.size()){
            return true;
        }
        return false;
    }
};

Leetcode Problem:

• Make String a Subsequence Using Cyclic Increments

Summary

• Given two strings, check if str2 can be made a subsequence of str1 by performing the operation at most once.

Approach

• The approach used is to iterate over each character in str1 and check if it is equal to the current character in str2 or the next character in str1 (cyclically)
• If it is, increment the pointer for str2.

Complexity

• O(n), where n is the length of str1

Explanation

• The solution iterates over each character in str1 and checks if it is equal to the current character in str2 or the next character in str1 (cyclically)
• If it is, increment the pointer for str2
• If the pointer for str2 reaches the end of str2, return true
• Otherwise, return false.

Solution Code:

class Solution {
public:

    bool canMakeSubsequence(string str1, string str2) {
        int j = 0;
        for(int i = 0 ; i < str1.size(); i++){
            char next = str1[i] == 'z' ? 'a' : str1[i] + 1;
            if(j < str2.size() && (str1[i] == str2[j] || str2[j] == next)){
                j++;
            }
        }
        if (j >= str2.size()) return true;
        return false;
    }
};

Leetcode Problem:

• Adding Spaces to a String

Summary

• Given a string and a vector of indices where spaces need to be added, insert spaces before the characters at the given indices.

Approach

• The approach is to iterate over the vector of indices and for each index, insert a space before the character at that index
• After the loop, add the remaining characters to the string.

Complexity

• O(n), where n is the number of indices in the vector.

Explanation

• The code uses a for loop to iterate over the vector of indices
• For each index, it uses the substr function to get the substring of the original string from the start index to the end index
• It then appends a space to the result string and updates the start index to the end index
• After the loop, it uses the substr function again to get the remaining substring of the original string and appends it to the result string
• The result string is then returned.

Solution Code:

class Solution {
public:
    string addSpaces(string s, vector& spaces) {
        int start = 0;
        int end;
        string ans = "";
        for(int i = 0 ; i < spaces.size(); i++){
            end = spaces[i];
            ans += s.substr(start, end-start);
            ans += " ";
            start = end;
        }
        ans += s.substr(start, s.size()-start);

        return ans;
    }
};

Leetcode Problem:

• Check If a Word Occurs As a Prefix of Any Word in a Sentence

Summary

• Check if a search word is a prefix of any word in a sentence.

Approach

• The approach used is to split the sentence into individual words and then check each word to see if it matches the search word
• If a match is found, the index of the word is returned
• If no match is found, -1 is returned.

Complexity

• O(n*m) where n is the number of words in the sentence and m is the length of the search word.

Explanation

• The solution code starts by splitting the sentence into individual words and storing them in a vector
• Then it iterates over each word and checks if it matches the search word
• If a match is found, the index of the word is returned
• If no match is found, -1 is returned
• The time complexity of this solution is O(n*m) because it needs to iterate over each word in the sentence and each character in the search word.

Solution Code:

class Solution {
public:
    vector words;
    int isPrefixOfWord(string sentence, string searchWord) {
        words.push_back(sentence);
        for(int i =0; i < sentence.size(); i++){
            if(sentence[i] == ' '){
                words.push_back(sentence.substr(i+1));
            }
        }
        for(int i = 0 ; i < words.size(); i++){
            int j = 0;
            for( ; j < searchWord.size(); j++){
                if(searchWord[j] != words[i][j]){
                    break;
                }
            }
            if(j == searchWord.size()){
                return i + 1;
            }
        }
        return -1;
    }
};

Leetcode Problem:

• Check If N and Its Double Exist

Summary

• Check if there exist two indices i and j in the given array such that arr[i] == 2 * arr[j] and i!= j.

Approach

• The approach used is to use a boolean array of size 4004 to keep track of the numbers we have seen so far
• For each number in the array, we check if its double or half exists in the boolean array
• If it does, we return true
• If not, we mark the number as seen in the boolean array.

Complexity

• O(n) where n is the size of the array

Explanation

• The given solution uses a boolean array of size 4004 to keep track of the numbers we have seen so far
• For each number in the array, we check if its double or half exists in the boolean array
• If it does, we return true
• If not, we mark the number as seen in the boolean array
• The time complexity of this solution is O(n) where n is the size of the array, as we are iterating through the array once
• The space complexity is also O(n) as we are using a boolean array of size 4004 to keep track of the numbers we have seen so far.

Solution Code:

class Solution {
public:
    int number[4004];
    bool checkIfExist(vector& arr) {
        for(int i = 0 ; i < arr.size(); i++){
            if (arr[i] & 1) {
                if(number[(arr[i] << 1) + 2000]){
                    return true;
                }
            } else{
                if(number[(arr[i] << 1) + 2000]){
                    return true;
                }
                if(number[(arr[i] >> 1) + 2000]){
                    return true;
                }
            }
            number[arr[i] + 2000] = true;
        }
        return false;
    }
};

Leetcode Problem:

• Valid Arrangement of Pairs

Summary

• Find a valid arrangement of pairs where each pair is connected to the previous one

Approach

• Use a depth-first search (DFS) to traverse the graph of pairs, starting from the node with the highest degree
• The DFS visits all nodes in the graph and constructs a path in reverse order

Complexity

• O(n + e), where n is the number of pairs and e is the number of edges

Explanation

• The solution first builds an adjacency list and degree map to represent the graph of pairs
• It then finds the node with the highest degree, which is the starting point for the DFS
• The DFS visits all nodes in the graph and constructs a path in reverse order, which represents a valid arrangement of pairs

Solution Code:

class Solution {
public:
    unordered_map> adj;
    unordered_map deg;

    vector rpath;
    void euler(int i){
        vector stk={i};
        while(!stk.empty()){
            i = stk.back();
            if(adj[i].empty()){
                rpath.push_back(i);
                stk.pop_back();
            } else{
                int j = adj[i].back();
                adj[i].pop_back();
                stk.push_back(j);
            }
        }
    }

    vector> validArrangement(vector>& pairs) {
        const int e = pairs.size();
        adj.reserve(e);
        deg.reserve(e);

        for(auto& edge : pairs){
            int start = edge[0], end=edge[1];
            adj[start].push_back(end);
            deg[start]++;
            deg[end]--;
        }

        int i0=deg.begin()->first;
        for (auto& [v,d]: deg){
            if(d == 1){
                i0 = v;
                break;
            }
        }
        euler(i0);

        vector> ans;
        ans.reserve(e);

        for(int i = rpath.size() - 2; i >= 0 ; i--){
            ans.push_back({rpath[i+1], rpath[i]});
        }
        return ans;

    }
};