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

Leetcode Problem:

• Construct Smallest Number From DI String

Summary

• Find the lexicographically smallest possible string num that meets the conditions given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing.

Approach

• The approach used is to first initialize a character array num with the digits from 1 to 9
• Then, for each character in the pattern, if the character is 'I', we shift all the digits to the right to maintain the increasing order
• If the character is 'D', we shift all the digits to the left to maintain the decreasing order
• Finally, we construct the string num by concatenating the digits in the array.

Complexity

• O(n), where n is the length of the pattern string.

Explanation

• The provided solution code uses a character array num to store the digits from 1 to 9
• It then iterates over the pattern string, shifting the digits in the array as needed to maintain the increasing or decreasing order
• Finally, it constructs the string num by concatenating the digits in the array
• The time complexity is O(n) because it needs to iterate over the pattern string once
• The space complexity is also O(n) because it needs to store the digits in the array.

Solution Code:

class Solution {
public:
    string smallestNumber(string pattern) {
        char num[10] = {0};
        num[0] = '1';
        for(int i = 1; i <= pattern.size(); i++ ){
            num[i] = '1'+i;
            int j = i;
            while(j > 0 && pattern[j-1] == 'D'){
                char t = num[j];
                num[j] = num[j-1];
                num[j-1] = t;
                j--;
            }
        }
        string ans = "";
        ans += num[0];
        for(int i = 1; i <= pattern.size(); i++){
            ans += num[i];
        }
        return ans;
    }
};

Leetcode Problem:

• Cousins in Binary Tree II

Summary

• Replace the value of each node in the binary tree with the sum of all its cousins' values.

Approach

• The approach is to use a level-order traversal (BFS) to calculate the sum of all cousins for each node
• Then, update the value of each node with the sum of its cousins.

Complexity

• O(n), where n is the number of nodes in the tree, since each node is visited once.

Explanation

• The solution uses a queue to perform a level-order traversal of the tree
• It calculates the sum of all cousins for each node by pushing the node and its children into the queue, then popping the node and adding its children to the queue
• The sum of all cousins is then calculated and used to update the value of the node.

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:
    TreeNode* replaceValueInTree(TreeNode* root) {
            root->val = 0;
    queue q;  q.push(root);
    while(!q.empty()){
        int n = q.size(), sum = 0;
        vector buf;
        while(n--){
            TreeNode* node = q.front(); q.pop();
            buf.push_back(node);
            if(node->left) { q.push(node->left); sum += node->left->val; }
            if(node->right){ q.push(node->right); sum += node->right->val; }
        }
        for(auto node: buf){
            int  t = sum;
            if(node->left)  t -= node->left->val;
            if(node->right) t -= node->right->val;
            if(node->left)  node->left->val = t;
            if(node->right) node->right->val = t;
        }
    }
    return root;
    }
};

Leetcode Problem:

• Kth Largest Sum in a Binary Tree

Summary

• Find the kth largest level sum in a binary tree

Approach

• Use a level-order traversal to calculate the sum of each level, then use merge sort to sort the sums and find the kth largest sum

Complexity

• O(n log n) due to the merge sort operation, where n is the number of nodes in the tree

Explanation

• The traversal function is used to calculate the sum of each level and store it in an array
• The merge sort function is then used to sort the array and find the kth largest sum
• If the number of levels in the tree is less than k, the function returns -1

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:
    long long arr[100001];
    long long tmp[100001];
    int maxDepth = 0;
    void merge(int l, int mid, int r){
        int i = l;
        int j = mid + 1;
        int cur = i;
        while(i <= mid && j <= r){
            if(arr[i] >= arr[j]){
                tmp[cur++] = arr[i++];
            } else{
                tmp[cur++] = arr[j++];
            }
        }
        while(i <= mid){
            tmp[cur++] = arr[i++];
        }
        for(i = l; i < cur; i++){
            arr[i] = tmp[i];
        }
    }
    void merge_sort(int l, int r){
        if(l >= r) return;
        int mid = (l + r) / 2;
        merge_sort(l, mid);
        merge_sort(mid+1, r);
        merge(l, mid, r);
    }
    void traversal(TreeNode* root, int depth){
        if (root == nullptr) return;
        maxDepth = max(maxDepth, depth);
        arr[depth] += root->val;
        traversal(root->left, depth+1);
        traversal(root->right, depth+1);
    }
    long long kthLargestLevelSum(TreeNode* root, int k) {
        traversal(root, 0);
        if (maxDepth + 1 < k){
            return -1;
        }
        merge_sort(0, 100000);
        return arr[k-1];
    }
};

Leetcode Problem:

• Split a String Into the Max Number of Unique Substrings

Summary

• Given a string s, return the maximum number of unique substrings that the given string can be split into.

Approach

• The approach used in this solution is a recursive depth-first search (DFS) approach
• The solution uses two data structures, a vector and a hash map, to store unique substrings and their corresponding hash values
• The DFS function recursively splits the string into substrings, checks if the substring is unique, and updates the maximum number of unique substrings found.

Complexity

• O(n * 2^n), where n is the length of the string, due to the recursive nature of the DFS function and the use of a hash map to store unique substrings.

Explanation

• The solution starts by initializing a vector and a hash map to store unique substrings and their corresponding hash values
• The DFS function is then called to recursively split the string into substrings
• For each substring, the solution checks if it is unique by checking if it exists in the hash map
• If it is unique, the solution updates the maximum number of unique substrings found
• The solution then recursively calls itself with the remaining part of the string and the updated maximum number of unique substrings
• Finally, the solution returns the maximum number of unique substrings found.

Solution Code:

#define BUCKET_SIZE 1024
struct _vector{
    string *arr;
    int size;
    int capacity;
    _vector(){
        capacity = 2;
        arr = new string[capacity];
        size = 0;
    }
    void push(string a){
        if (size == capacity){
            capacity *= 2;
            string* tmp = new string[capacity];
            for(int i = 0 ; i < size; i++){
                tmp[i] = arr[i];
            }
            delete[] arr;
            arr = tmp;
        }
        arr[size++] = a;
    }
    string operator[](int index){
        return arr[index];
    }
    void del(string s){
        int i;
        for(i = 0 ; i < size; i++){
            if(s.compare(arr[i]) == 0){
                arr[i] = arr[--size];
                break;
            }
        }
    }
};


struct _hashMap{
    _vector v[BUCKET_SIZE];
    int getHash(string& s){
        unsigned int hash = 31;
        for(int i = 0 ; i < s.size(); i++){
            hash *= s[i]-'a';
            hash %= BUCKET_SIZE;
        }
        return hash;
    }
    bool getString(string s){
        int bucket = getHash(s);
        int size = v[bucket].size;
        for(int i = 0 ; i < size; i++){
            if (v[bucket][i].compare(s) == 0){
                return true;
            }
        }
        return false;
    }
    void push(string s){
        int bucket = getHash(s);
        v[bucket].push(s);
    }
    void pop(string s){
        int bucket = getHash(s);
        v[bucket].del(s);
    }
};

class Solution {
public:
    _vector v;
    _hashMap hm;
    int ans = 0;
    void go(string s, int depth){
        ans = max(ans, depth);
        for(int i = 1 ; i <=s.size(); i++){
            string ss = s.substr(0, i);
            if(hm.getString(ss)){
                continue;
            }
            hm.push(ss);
            go(s.substr(i), depth + 1);
            hm.pop(ss);
        }
    }

    int maxUniqueSplit(string s) {
        go(s, 0);
        
        return ans;
    }
};

Leetcode Problem:

• Parsing A Boolean Expression

Summary

• Given a boolean expression, evaluate the expression and return the result.

Approach

• This solution uses a stack to parse the boolean expression
• It first pushes each character of the expression into the stack
• When it encounters a '(', it pops characters from the stack until it finds a ')'
• Then it processes the operator and the operands, and pushes the result back into the stack
• Finally, it returns the result at the top of the stack.

Complexity

• O(n), where n is the length of the expression
• This is because each character in the expression is pushed and popped from the stack once.

Explanation

• The parseBoolExpr function takes a string expression as input and returns a boolean value
• It uses a stack to parse the expression
• The stack is used to keep track of the operators and operands
• The function processes each operator and the operands, and pushes the result back into the stack
• Finally, it returns the result at the top of the stack.

Solution Code:

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

class Solution {
public:
    _stack st;
    vector v;
    char strToInt[256];
    bool process(char oper, vector& v){
        if (oper == '!'){
            return !(strToInt[v[0]]);
        }
        if (oper == '|'){
            bool res = strToInt[v[0]];
            for(int i = 1; i < v.size(); i++){
                res |= strToInt[v[i]];
                if(res) return true;
            }
        }
        bool res = strToInt[v[0]];
        for(int i = 1; i < v.size(); i++){
            res &= strToInt[v[i]];
        }
        return res;
    }

    bool parseBoolExpr(string expression) {
        strToInt['f'] = 0;
        strToInt['t'] = 1;
        bool res;
        for(char c: expression){
            if (c != ')'){
                if(c == ',') continue;
                st.push(c);
                continue;
            } 
            while(st.peek() != '('){
                v.push_back(st.pop());
            }
            st.pop();
            char oper = st.pop();
            res = process(oper,v );
            st.push(res ? 't':'f');
            v.clear();
        }
        return st.peek() == 't' ? true: false;
    }
};

Leetcode Problem:

• Find Kth Bit in Nth Binary String

Summary

• Given two positive integers n and k, the binary string S_n is formed by a recursive process
• The problem asks to find the k-th bit in S_n.

Approach

• The approach used is to build the binary string S_n by concatenating the inverted and reversed previous string, and then find the k-th bit in the resulting string.

Complexity

• O(n log n)

Explanation

• The solution iterates through each bit position in the binary string S_n
• For each position, it checks if the current bit position is less than or equal to the current size of the string
• If so, it returns the bit at the current position
• Otherwise, it appends a new bit to the end of the string, inverts and reverses the previous string, and updates the size of the string
• This process is repeated until the k-th bit is found.

Solution Code:

class Solution {
public:
    char arr[2<<20 + 1] = {0};
    char findKthBit(int n, int k) {
        int size = 1;
        for(int i = 0 ; i < n ; i++){
            int s = size;
            if (k <= s) return arr[k-1] + '0';
            arr[s++] = 1;
            for(int i = size-1; i >= 0; i--){
                arr[s++] = arr[i] ^ 1;
            }
            size = s;
        }
        return arr[k - 1] + '0';
    }
};

Leetcode Problem:

• Maximum Swap

Summary

• Given an integer, find the maximum valued number by swapping two digits at most once.

Approach

• Use a stack to store the digits of the input number, and then iterate through the stack to find the largest possible swap
• If a swap is possible, perform it and return the result
• If no swap is possible, return the original number.

Complexity

• O(log n) where n is the input number, because we are iterating through the stack and performing constant time operations for each digit.

Explanation

• The solution uses a stack to store the digits of the input number
• It starts by pushing the digits onto the stack in reverse order, along with their corresponding powers of 10
• Then, it iterates through the stack to find the largest possible swap
• If a swap is possible, it performs the swap and returns the result
• If no swap is possible, it returns the original number.

Solution Code:

struct number{
    int n;
    int pow;
};
struct _stack{
    number arr[20];
    int top;
    _stack(){
        top = 0;
    }
    void push(number a){
        arr[top++] = a;
    }
    number pop(){
        return arr[--top];
    }
    number peek(){
        return arr[top - 1];
    }
    bool empty(){
        return top == 0;
    }
};


class Solution {
public:
    _stack st;
    int maximumSwap(int num) {
        vector mostRight;
        int tmpNum = num;
        int pow = 1;
        while(tmpNum){
            int n = tmpNum % 10;
            while (!st.empty() && st.peek().n < n){
                st.pop();
            }
            if(st.empty()){
                st.push({n, pow});
                mostRight.push_back({n, pow});
            } else{
                mostRight.push_back({st.peek().n, st.peek().pow});
            }
            pow *= 10;
            tmpNum /= 10;
        }
        int idx = mostRight.size() - 1;
        while(pow/10){
            pow /= 10;
            int n = (num % (pow*10)) / pow;
            if (mostRight[idx].n != n){
                num -= n * pow;
                num -= mostRight[idx].n * mostRight[idx].pow;
                num += n * mostRight[idx].pow;
                num += mostRight[idx].n * pow;
                return num;
            }

            idx--;
        }
        return num;
    }
};

Leetcode Problem:

• Longest Happy String

Summary

• Given three integers a, b, and c, return the longest possible happy string
• A happy string is a string that only contains the letters 'a', 'b', and 'c' and does not contain any of 'aaa', 'bbb', or 'ccc' as a substring
• If there are multiple longest happy strings, return any of them
• If there is no such string, return the empty string "".

Approach

• The solution uses a recursive approach to build the longest possible happy string
• It first checks if the input values are valid and then recursively calls itself to build the string
• The base case is when one of the letters (a, b, or c) is 0, in which case it returns the string with the minimum of 2 or the count of that letter.

Complexity

• O(a + b + c) due to the recursive calls, where a, b, and c are the counts of letters 'a', 'b', and 'c' respectively.

Explanation

• The solution starts by checking the base cases where one of the letters is 0
• If a is less than b, it swaps them and calls itself recursively
• If b is less than c, it swaps them and calls itself recursively
• If b is 0, it returns the string with the minimum of 2 or the count of 'a'
• It then calculates the minimum counts of 'a' and 'b' that can be used to build the string and recursively calls itself with the remaining counts of 'a', 'b', and 'c'.

Solution Code:

class Solution {
public:

    string longestDiverseString(int a, int b, int c, char aa='a', char bb='b', char cc='c') {
        if (a < b){
            return longestDiverseString(b, a, c, bb, aa, cc);
        }
        if (b < c){
            return longestDiverseString(a, c, b, aa, cc, bb);
        }
        if (b == 0){
            return string(min(2, a), aa);
        }
        int use_a = min(2, a);
        int use_b = a - use_a >= b ? 1 : 0;
        return string(use_a, aa) + string(use_b, bb) + longestDiverseString(a-use_a, b - use_b, c, aa, bb, cc);
    }
};

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