'LeetCode'에 해당되는 글 274건

Leetcode Problem:

• Maximal Score After Applying K Operations

Summary

• Find the maximum possible score that can be attained after applying exactly k operations to the given array of integers.

Approach

• The approach is to use a min-heap to store the elements of the array
• We first push all the elements into the heap
• Then, we repeatedly pop the smallest element from the heap, add its value to the score, and push the ceiling of the value back into the heap
• This process is repeated k times to maximize the score.

Complexity

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

Solution Code:

struct _heap{
    int arr[100001];
    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+1] > arr[j]){
                j++;
            }
            if(arr[j] > arr[i]){
                int t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
                i = j;
            } else {
                break;
            }
        }

        return ret;
    }
};

class Solution {
public:
    _heap h;
    long long maxKelements(vector& nums, int k) {
        long long score = 0;
        for(int i = 0 ; i < nums.size(); i++){
            h.push(nums[i]);
        }
        while(k--){
            int n = h.pop();
            score += n;
            int t1 = n/3;
            double t2 = (double)n/3;
            h.push(t1 == t2 ? t1 : (int)(t2 + 1));
        }
        return score;
    }
};

Leetcode Problem:

• Smallest Range Covering Elements from K Lists

Summary

• Find the smallest range that includes at least one number from each of k sorted lists.

Approach

• Use two heaps, a min heap and a max heap, to keep track of the smallest and largest numbers in the current range
• The min heap stores the smallest number in each list, and the max heap stores the largest number in each list
• The solution iteratively updates the range by popping the smallest number from the min heap and pushing the next number in the same list into the min heap
• The range is updated by comparing the current range with the new range and updating the minimum and maximum values if necessary.

Complexity

• O(k * log(k * n)) where k is the number of lists and n is the maximum length of a list

Explanation

• The solution uses two heaps to keep track of the smallest and largest numbers in the current range
• The min heap stores the smallest number in each list, and the max heap stores the largest number in each list
• The solution iteratively updates the range by popping the smallest number from the min heap and pushing the next number in the same list into the min heap
• The range is updated by comparing the current range with the new range and updating the minimum and maximum values if necessary
• The time complexity is O(k * log(k * n)) where k is the number of lists and n is the maximum length of a list.

Solution Code:

struct _node{
    int num;
    int idx;
};
bool _asc(_node a, _node b){
    if(a.num != b.num) return a.num < b.num;
    return a.idx < b.idx;
}
bool _dec(_node a, _node b){
    if(a.num != b.num) return a.num > b.num;
    return a.idx < b.idx;
}
struct _heap{
    _node arr[3500*50];
    int size;
    _heap(){
        size = 1;
    }
    bool (*_cmp)(_node a, _node b);
    void setCmp(bool (*func)(_node a, _node b)){
        _cmp = func;
    }
    void push(_node a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && _cmp(arr[idx], arr[idx/2])){
            _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+1], arr[j])){
                j++;
            }
            if(_cmp(arr[j], arr[i])){
                _node t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
                i = j;
            } else {
                break;
            }
        }
        return ret;
    }
    int peek(){
        return arr[1].num;
    }
    bool empty(){
        return size == 1;
    }
};

class Solution {
public:
    _heap minHeap;
    _heap maxHeap;
    _heap _maxLazy;
    int numsIdx[3500] = {0};

    void removeMaxHeap(_node a){
        _maxLazy.push(a);
    }
    int peekMaxHeap(){
        while(!_maxLazy.empty() && maxHeap.peek() == _maxLazy.peek()){
            maxHeap.pop();
            _maxLazy.pop();
        }
        return maxHeap.arr[1].num;
    }

    vector smallestRange(vector>& nums) {
        minHeap.setCmp(_asc);
        maxHeap.setCmp(_dec);
        _maxLazy.setCmp(_dec);
        for(int i = 0 ; i < nums.size(); i++){
            minHeap.push({nums[i][0], i});
            maxHeap.push({nums[i][0], i});
        }
        vector res;
        res.push_back(minHeap.peek());
        res.push_back(maxHeap.peek());

        while(true){
            _node n = minHeap.pop();
            removeMaxHeap(n);
            int nextIdx = ++numsIdx[n.idx];
            if(nextIdx >= nums[n.idx].size()) break;
            int nextNum = nums[n.idx][nextIdx];
            minHeap.push({nextNum, n.idx});
            maxHeap.push({nextNum, n.idx});
            if((res[1] - res[0]) > (peekMaxHeap() - minHeap.peek())){
                res[0] = minHeap.peek();
                res[1] = peekMaxHeap();
            }
        }

        return res;
    }
};

Leetcode Problem:

• The Number of the Smallest Unoccupied Chair

Summary

• Find the chair number that a friend will sit on at a party.

Approach

• Use a min-heap to keep track of the chairs that are available and the start and end times of each friend's visit.

Complexity

• O(n log n) due to the sorting of start and end times, where n is the number of friends.

Explanation

• Create a min-heap to store the chairs and a vector to store the start and end times of each friend's visit
• Sort the start and end times to ensure that the friends arrive and leave in the correct order
• Then, iterate over the time range and pop the smallest chair from the heap when a friend arrives and push it back into the heap when the friend leaves
• If the target friend arrives, return the chair number.

Solution Code:

struct _pair{
    int start;
    int end;
    int chair;
};

struct _heap{
    int size;
    int arr[10001];
    _heap(){
        size = 1;
    }
    void push(int a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 0 && arr[idx] < arr[idx/2]){
            int tmp = arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = tmp;
            idx /= 2;
        }
    }
    int pop(){
        int ret = arr[1];
        int i = 1;
        arr[i] = arr[--size];
        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 tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i = j;
            } else {
                break;
            }
        }
        return ret;
    }
    bool empty(){
        return size == 1;
    }
};
vector<_pair> _times;

class Solution {
public:
    static bool _cmpStart(int a, int b){
        return _times[a].start > _times[b].start;
    }
    static bool _cmpEnd(int a, int b){
        return _times[a].end > _times[b].end;
    }
    int smallestChair(vector>& times, int targetFriend) {
        _times.clear();
        _heap h;
        vector start;
        vector end;
        for(int i = 0 ; i < times.size(); i++){
            _times.push_back({times[i][0], times[i][1], -1});
            start.push_back(i);
            end.push_back(i);
            h.push(i);
        }
        sort(start.begin(), start.end(), _cmpStart);
        sort(end.begin(), end.end(), _cmpEnd);

        int startSize = start.size();
        int endSize = end.size();
        for(int i = 0 ; i <= 100000; i++){
            while(endSize > 0 && _times[end[endSize - 1]].end == i){
                h.push(_times[end[endSize - 1]].chair);
                endSize--;
            }
            while(startSize > 0 && _times[start[startSize - 1]].start == i){
                int chair = h.pop();
                if (start[startSize - 1] == targetFriend){
                    return chair;
                }
                _times[start[startSize - 1]].chair = chair;
                startSize--;
            }
        }
        return 0;
    }
};

Leetcode Problem:

• Letter Tile Possibilities

Summary

• The problem is to find the number of possible non-empty sequences of letters that can be made using the letters printed on the tiles.

Approach

• The solution uses a recursive approach with backtracking
• It checks all possible combinations of letters and stores the valid sequences in a set.

Complexity

• O(2^n * n) where n is the length of the tiles string

Explanation

• The solution uses a recursive function checkCnt to generate all possible sequences of letters
• It uses a set to store the valid sequences and a visited array to prevent duplicate sequences
• The function checks all possible combinations of letters and adds the valid sequences to the set
• Finally, it returns the size of the set, which represents the number of possible non-empty sequences of letters.

Solution Code:

class Solution {
public:
    bool visited[7];
    set s;
    void checkCnt(string &tiles, string letters, int length, int depth){
        if(length == depth){
            s.insert(letters);
            return;
        }
        for(int i = 0 ; i < tiles.size(); i++){
            if(visited[i]) continue;
            visited[i] = true;
            checkCnt(tiles, letters + tiles[i], length + 1, depth);
            visited[i] = false;
        }
    }   
    int numTilePossibilities(string tiles) {
        for(int i = 1; i <= tiles.size(); i++){
            checkCnt(tiles, "", 0, i);
        }
        return s.size();
    }
};

Leetcode Problem:

• Maximum Width Ramp

Summary

• The problem requires finding the maximum width of a ramp in an integer array
• A ramp is defined as a pair (i, j) where i < j and nums[i] <= nums[j]
• The width of the ramp is j - i
• The goal is to find the maximum width of such a ramp in the given array.

Approach

• Binary Search Approach: The solution uses a binary search approach to find the maximum width of the ramp
• It initializes two pointers, one at the start and one at the end of the array
• It calculates the middle index and checks if there is a ramp starting from that index
• If there is, it moves the left pointer to the right of the middle index
• Otherwise, it moves the right pointer to the left of the middle index
• This process continues until the left pointer is greater than the right pointer.

Complexity

• O(n log n) due to the binary search, where n is the size of the array

Explanation

• The solution starts by initializing two pointers, one at the start and one at the end of the array
• It calculates the middle index and checks if there is a ramp starting from that index
• If there is, it moves the left pointer to the right of the middle index
• Otherwise, it moves the right pointer to the left of the middle index
• This process continues until the left pointer is greater than the right pointer
• The solution uses a binary search approach to find the maximum width of the ramp, which allows it to efficiently search for the ramp
• The time complexity of the solution is O(n log n) due to the binary search, where n is the size of the array.

Solution Code:

class Solution {
public:
    int maxWidthRamp(vector& nums) {
        int l = 0;
        int r = nums.size() - 1;
        int ans = 0;
        while(l <= r){
            int win_size = (l + r) / 2;
            bool success = false;
            int minValue = 5*10000;
            for(int i = 0; i < nums.size()- win_size; i++){
                minValue = min(minValue, nums[i]);
                if(minValue <= nums[i+win_size]){
                    success = true;
                }
            }
            if(success){
                l = win_size + 1;
                ans = win_size;
            } else {
                r = win_size - 1;
            }

        }
        return ans;
    }
};

Leetcode Problem:

• Minimum Number of Swaps to Make the String Balanced

Summary

• The problem is to find the minimum number of swaps required to make a given string of even length balanced.

Approach

• The approach used is to use a stack data structure to keep track of the opening brackets
• The stack is used to check if a closing bracket matches with the top of the stack
• If a match is found, the top of the stack is popped
• If no match is found, the current bracket is pushed into the stack
• After processing the entire string, the minimum number of swaps required to balance the string is calculated by dividing the number of remaining opening brackets by 2 and adding 1, and then dividing by 2.

Complexity

• O(n) where n is the length of the string

Explanation

• The provided solution code uses a stack to keep track of the opening brackets
• The stack is initialized as a private member of the Solution class
• In the minSwaps function, the code iterates over the string and checks if the stack is empty
• If the stack is empty, the current character is pushed into the stack
• If the stack is not empty, the top of the stack is checked with the current character
• If they match, the top of the stack is popped
• If they do not match, the current character is pushed into the stack
• After processing the entire string, the minimum number of swaps required to balance the string is calculated by dividing the number of remaining opening brackets by 2 and adding 1, and then dividing by 2.

Solution Code:

struct _stack{
    char arr[1000001];
    int top;
    _stack(){
        top = 0;
    }
    void push(char a){
        arr[top++] = a;
    }
    bool empty(){
        return top == 0;
    }
    char peek(){
        if(empty()) return -1;
        return arr[top-1];
    }
    void pop(){
        if(empty()) return;
        top--;
    }
};

class Solution {
public:
    _stack st;
    int minSwaps(string s) {
        int res = 0;
        for(int i = 0 ; i < s.size(); i++){
            if(st.empty()){
                st.push(s[i]);
                continue;
            }
            char a = st.peek();
            char b = s[i];
            if(a == '[' && b == ']'){
                st.pop();
                continue;
            } else{
                st.push(b);
            }
        }
        return (st.top/2+1)/2;
    }
};

Leetcode Problem:

• Minimum String Length After Removing Substrings

Summary

• Given a string of uppercase English letters, find the minimum possible length of the resulting string after removing any occurrences of the substrings "AB" or "CD".

Approach

• This problem is solved using a recursive approach where we try to remove the first occurrence of "AB" or "CD" from the string and then check if the resulting string can be further reduced
• If not, we return the current minimum length.

Complexity

• O(2^n) due to the recursive calls, where n is the length of the input string.

Explanation

• The solution starts by initializing the minimum length to the length of the input string
• Then, it iterates over the string and checks for the first occurrence of "AB" or "CD"
• If found, it recursively calls the function with the substring obtained by removing the found substring from the start of the string, and updates the minimum length if the resulting string has a smaller length
• This process continues until no more occurrences of "AB" or "CD" can be found in the string.

Solution Code:

class Solution {
public:
    int minLength(string s) {
        int ans = s.size();
        for(int i = 0 ; i < s.size(); i++){
            if (s.substr(i, 2).compare("AB") == 0){
                ans = min(ans, minLength(s.substr(0, i) + s.substr(i+2)));
                break;
            } else if (s.substr(i, 2).compare("CD") == 0){
                ans = min(ans, minLength(s.substr(0, i) + s.substr(i+2)));
                break;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Sentence Similarity III

Summary

• Two sentences are considered similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal.

Approach

• The approach is to first find the longest common prefix of the two sentences
• If the prefix is empty, the sentences are not similar
• Otherwise, we check if the remaining part of the shorter sentence can be inserted between the words of the longer sentence to make them equal.

Complexity

• O(n), where n is the length of the shorter sentence.

Explanation

• We first find the longest common prefix of the two sentences by iterating through the characters of the sentences
• If the prefix is empty, we return false
• Otherwise, we check if the remaining part of the shorter sentence can be inserted between the words of the longer sentence to make them equal
• We do this by iterating through the remaining part of the shorter sentence and checking if each word matches the corresponding word in the longer sentence
• If we find a mismatch, we return false
• If we reach the end of the remaining part of the shorter sentence without finding a mismatch, we return true.

Solution Code:

class Solution {
public:
    bool areSentencesSimilar(string sentence1, string sentence2) {
        string t;
        if (sentence1.size() < sentence2.size()){
            t = sentence1;
            sentence1 = sentence2;
            sentence2 = t;
        }
        int lastSpace = -1;
        int i = 0;
        for( ; i < sentence2.size(); i++){
            if(sentence2[i] == sentence1[i] && sentence2[i] == ' '){
                lastSpace = i;
            }
            if (sentence1[i] != sentence2[i]) break;
        }
        if (i == sentence2.size() && sentence1[i] == ' ') return true;
        int s1_len = sentence1.size();
        int s2_len = sentence2.size();
        int before_idx = sentence1.size() - (s2_len - lastSpace);
        if (before_idx >= 0 && sentence1[before_idx] != ' ') return false;
        for(i = lastSpace+1; i < s2_len; i++){
            int s1_idx = sentence1.size() - (s2_len - i);
            if(s1_idx >= s1_len) return false;
            if(sentence1[s1_idx] != sentence2[i]) return false;
        }
        return true;
    }
};

Leetcode Problem:

• Construct the Lexicographically Largest Valid Sequence

Summary

• Given an integer n, find a sequence that satisfies the following conditions: 1 occurs once, each integer between 2 and n occurs twice, and the distance between the two occurrences of each integer is exactly i.

Approach

• The approach is to use a depth-first search (DFS) to try all possible sequences
• We start by initializing a vector to store the sequence and then call the DFS function
• In the DFS function, we try all possible numbers from n to 1, and for each number, we try to insert it into the sequence
• If the number is 1, we insert it at the first position
• If the number is not 1, we try to insert it at the position that is i steps away from the previous occurrence of the number, where i is the number itself
• We use a visited array to keep track of the numbers that have been tried, and we return false if we cannot find a valid sequence.

Complexity

• O(n^2 * 2^n) due to the recursive nature of the DFS function and the fact that we are trying all possible sequences.

Explanation

• The provided solution code uses a depth-first search (DFS) approach to try all possible sequences
• The DFS function is recursive and tries all possible numbers from n to 1
• For each number, it tries to insert it into the sequence
• If the number is 1, it inserts it at the first position
• If the number is not 1, it tries to insert it at the position that is i steps away from the previous occurrence of the number, where i is the number itself
• The solution uses a visited array to keep track of the numbers that have been tried, and it returns false if it cannot find a valid sequence
• The time complexity is O(n^2 * 2^n) due to the recursive nature of the DFS function and the fact that we are trying all possible sequences.

Solution Code:

class Solution {
public:
    int nextIdx(vector& ans){
        for(int i = 0 ; i < ans.size(); i++){
            if(ans[i] == -1)
                return i;
        }
        return -1;
    }
    int visited[21];
    bool dfs(int N, vector& ans){
        bool success = true;
        for(int i = 0 ; i < ans.size(); i++){
            if(ans[i] == -1){
                success = false;
                break;
            }
        }

        if(success){
            return true;
        }
        for(int i = N; i > 0; i--){
            if(visited[i]){
                continue;
            }
            visited[i] = true;
            int idx = nextIdx(ans);
            ans[idx] = i;
            if(i != 1){
                if(idx+i >= (2*N-1)  || ans[idx+i] != -1){
                    ans[idx] = -1;
                    visited[i] = false;
                    continue;
                } else{
                    ans[idx+i] = i;
                }
            }
            if(dfs(N, ans)){
                return true;
            }
            ans[idx] = -1;
            if(i != 1)
                ans[idx+i]= -1;
            visited[i] = false;
                   
        }
        return false;
    }
    vector constructDistancedSequence(int n) {
        vector ans;
        for(int i = 0; i < ((n << 1)-1) ; i++){
            ans.push_back(-1);
        }
        dfs(n, ans);
        return ans;   
    }
};

Leetcode Problem:

• Find the Punishment Number of an Integer

Summary

• This problem requires finding the punishment number of a given positive integer n
• The punishment number is the sum of squares of all integers i such that 1 <= i <= n and the decimal representation of i*i can be partitioned into contiguous substrings with integer values summing up to i.

Approach

• The solution uses a recursive approach with backtracking to find all possible partitions of i*i into contiguous substrings with integer values summing up to i
• It starts from the smallest possible value of i and checks all possible partitions of i*i
• If a valid partition is found, it adds the square of i to the result and moves on to the next value of i.

Complexity

• O(n * 6^6) where n is the input number, due to the recursive backtracking and the loop that generates all possible partitions of i*i.

Solution Code:

class Solution {
public:
    bool check_punishment(int num,vector& nums, int depth, int goal_num){
        if(num == 0){
            if(nums[0] == goal_num) return false;
            int sum = 0;
            for(int i = 0 ; i < nums.size(); i++){
                sum += nums[i];
            }
            if(sum == goal_num){
                return true;
            } else{
                return false;
            }
        }
        int pow = 10;
        for(int i = 1; i <= 6; i++){
            nums.push_back(num % pow);
            if(check_punishment(num/pow, nums, depth+1, goal_num)){
                nums.pop_back();
                return true;
            }
            pow *= 10;
            nums.pop_back();
        }
        return false;
    }
    int punishmentNumber(int n) {
        vector nums;
        int ans = 0;
        for(int i = 1; i <= n; i++){
            int pow = 10;
            for(int j = 1; j <= 6; j++){
                int nn = i * i;
                nums.push_back(nn % pow);
                if(check_punishment(nn/pow, nums, 1, i)){
                    nums.pop_back();
                    ans += nn;
                    break;
                }
                pow *= 10;
                nums.pop_back();
            }
        }
        
        return ans + 1;
    }
};