짬뽕얼큰하게의 맨땅에 헤딩 :: '2025/02/10 글 목록

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

Clear Digits

알고리즘 2025. 2. 10. 23:41

Leetcode Problem:

Summary

  • Remove all digits from a given string by deleting the first digit and the closest non-digit character to its left.

Approach

  • Use a stack to store the non-digit characters and then join them into a string to get the final result.

Complexity

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

Explain

  • The solution iterates through the string and pushes non-digit characters into the stack
  • When a digit is encountered, it pops the top element from the stack
  • Finally, it joins the characters in the stack into a string and returns it.

Solution Code:


class Solution {
public:
    vector st;
    string clearDigits(string s) {
        for(int i = 0 ; i < s.size(); i++){
            if(s[i] >= 'a' && s[i] <= 'z'){
                st.push_back(s[i]);
            }else{
                if(st.size() != 0){
                    st.pop_back();
                }
            }
        }
        string res = "";
        for(int i = 0 ; i < st.size(); i++){
            res += st[i];
        }
        return res;
    }
};

'알고리즘' 카테고리의 다른 글

Most Stones Removed with Same Row or Column  (0) 2025.02.11
Count Sub Islands  (0) 2025.02.11
N-ary Tree Postorder Traversal  (0) 2025.02.10
Binary Tree Postorder Traversal  (0) 2025.02.10
Find the Closest Palindrome  (0) 2025.02.10
블로그 이미지

짬뽕얼큰하게

,

N-ary Tree Postorder Traversal

알고리즘 2025. 2. 10. 09:07

Leetcode Problem:

Summary

  • Postorder traversal of an n-ary tree

Approach

  • Recursive approach with backtracking to traverse the tree in postorder.

Complexity

  • O(N)

Explain

  • The solution code uses a recursive approach with backtracking to traverse the tree in postorder
  • It starts by checking if the root is null, if so, it returns an empty vector
  • Then it iterates over each child of the root, recursively calls the postorder function on each child, and appends the result to the answer vector
  • Finally, it appends the value of the root to the answer vector and returns the vector
  • The time complexity is O(N) where N is the number of nodes in the tree.

Solution Code:


/*
// Definition for a Node.
class Node {
public:
    int val;
    vector children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector postorder(Node* root) {
        if (root == nullptr) return {};
        vector ans;
        for(int i = 0 ; i < root->children.size(); i++){
            vector tmp = postorder(root->children[i]);
            ans.insert(ans.end(), tmp.begin(), tmp.end());
        }
        
        ans.push_back(root->val);
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Count Sub Islands  (0) 2025.02.11
Clear Digits  (0) 2025.02.10
Binary Tree Postorder Traversal  (0) 2025.02.10
Find the Closest Palindrome  (0) 2025.02.10
Fraction Addition and Subtraction  (0) 2025.02.10
블로그 이미지

짬뽕얼큰하게

,

Binary Tree Postorder Traversal

알고리즘 2025. 2. 10. 09:04

Leetcode Problem:

Summary

  • Postorder traversal of a binary tree nodes' values

Approach

  • Recursive approach with left subtree and right subtree traversals followed by the current node's value.

Complexity

  • O(n) where n is the number of nodes in the tree

Explain

  • The solution uses a recursive approach to traverse the binary tree
  • It first checks if the root is null, if so, it returns an empty vector
  • Then, it recursively calls the postorderTraversal function on the left and right subtrees, and combines the results by inserting the right subtree's values into the left vector and appending the current node's value
  • This process is repeated until the base case is reached, resulting in a postorder traversal of the tree's nodes' values.

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 postorderTraversal(TreeNode* root) {
        if(root==nullptr)
            return {};
        vector left = postorderTraversal(root->left);
        vector right = postorderTraversal(root->right);
        left.insert(left.end(), right.begin(), right.end());
        left.push_back(root->val);

        return left;
    }
};

'알고리즘' 카테고리의 다른 글

Clear Digits  (0) 2025.02.10
N-ary Tree Postorder Traversal  (0) 2025.02.10
Find the Closest Palindrome  (0) 2025.02.10
Fraction Addition and Subtraction  (0) 2025.02.10
Number Complement  (0) 2025.02.10
블로그 이미지

짬뽕얼큰하게

,

Find the Closest Palindrome

알고리즘 2025. 2. 10. 09:01

Leetcode Problem:

Summary

  • The problem requires finding the closest integer (not including itself) which is a palindrome
  • If there is a tie, return the smaller one.

Approach

  • The approach is to first convert the input string into an integer using the strToInt function
  • Then, find the closest palindrome by checking the numbers before and after the middle digit
  • If the length of the string is odd, consider the numbers with one digit less
  • If the length is even, add a 9 to the first half of the number to make it a palindrome
  • Then, calculate the absolute difference between each of these numbers and the input number, and return the number with the minimum difference.

Complexity

  • O(n), where n is the length of the input string
  • This is because the time complexity is dominated by the loop that checks the numbers before and after the middle digit.

Explain

  • The code first converts the input string into an integer using the strToInt function
  • Then, it calculates the middle index of the string
  • If the length of the string is odd, it considers the numbers with one digit less by removing the middle digit
  • If the length is even, it adds a 9 to the first half of the number to make it a palindrome
  • Then, it calculates the absolute difference between each of these numbers and the input number, and returns the number with the minimum difference
  • The time complexity of the code is O(n), where n is the length of the input string, because the time complexity is dominated by the loop that checks the numbers before and after the middle digit.

Solution Code:


class Solution {
public:
    long long strToInt(string n){
        long long pow = 1;
        long long res = 0;
        for(int i =  n.size() -1 ; i >= 0; i--){
            res += pow * (n[i] - '0');
            pow *=10;
        }
        return res;
    }
    string nearestPalindromic(string n) {
        long long N = strToInt(n);
        int len = n.size();
        if (len == 1){
            return to_string(N -1);
        } else if (n.compare("10") == 0 || n.compare("11") == 0){
            return "9";
        }
        int mid = (len + 1) / 2;
        string preNum = n.substr(0,mid);
        string postNum = n.substr(mid);
        string preCmpNum = string(preNum);
        if (len %2){
            preCmpNum = preCmpNum.substr(0, mid-1);
        }
        reverse(preCmpNum.begin(), preCmpNum.end());

        long long pre1 = strToInt(preNum) - 1;
        long long pre2 = strToInt(preNum);
        long long pre3 = strToInt(preNum) + 1;


        string preStr1 = to_string(pre1);
        string preStr2 = to_string(pre2);
        string preStr3 = to_string(pre3);
        string postStr1, postStr2, postStr3;
        bool offset1 = false, offset2 = false, offset3 = false;
        if (len%2){
            offset1 = !offset1;
            offset2 = !offset2;
            offset3 = !offset3;
        }
        if (preStr1.size() != preStr2.size()){
            offset1 = !offset1;
            if(len %2 == 0){
                preStr1 += "9";
            }
            
        }
        if (preStr2.size() != preStr3.size()){
            offset3 = !offset3;
            if (len %2)
                preStr3 = preStr3.substr(0, preStr3.size()-1);
        }
        postStr1 = preStr1.substr(0, preStr1.size() - offset1);
        postStr2 = preStr2.substr(0, preStr2.size() - offset2);
        postStr3 = preStr3.substr(0, preStr3.size() - offset3);
        reverse(postStr1.begin(), postStr1.end());
        reverse(postStr2.begin(), postStr2.end());
        reverse(postStr3.begin(), postStr3.end());

        string number[3];
        long long diff[3];
        number[0] = preStr1 + postStr1;
        number[1] = preStr2 + postStr2;
        number[2] = preStr3 + postStr3;
        diff[0] = abs(strToInt(number[0]) - N);
        diff[1] = abs(strToInt(number[1]) - N);
        diff[2] = abs(strToInt(number[2]) - N);
        
        if (diff[1] == 0) return diff[0] <= diff[2] ? number[0] : number[2];
        
        int minIdx = 0;
        long long minDiff = diff[0];
        for(int i = 1; i < 3; i++){
            if (minDiff > diff[i]){
                minDiff = diff[i];
                minIdx = i;
            }
        }
        
        return number[minIdx];
    }
};

'알고리즘' 카테고리의 다른 글

N-ary Tree Postorder Traversal  (0) 2025.02.10
Binary Tree Postorder Traversal  (0) 2025.02.10
Fraction Addition and Subtraction  (0) 2025.02.10
Number Complement  (0) 2025.02.10
Stone Game II  (0) 2025.02.10
블로그 이미지

짬뽕얼큰하게

,

Fraction Addition and Subtraction

알고리즘 2025. 2. 10. 08:57

Leetcode Problem:

Summary

  • Given a string representing an expression of fraction addition and subtraction, return the calculation result in string format.

Approach

  • The solution uses an istringstream to parse the input string and then applies the Euclidean algorithm to find the greatest common divisor of the numerator and denominator of each fraction, reducing them to their simplest form
  • The final result is then converted to a string and returned.

Complexity

  • O(n), where n is the number of fractions in the input string

Explain

  • The solution works by iterating over each fraction in the input string, applying the Euclidean algorithm to reduce the fraction to its simplest form
  • The final result is then converted to a string and returned
  • The time complexity of the solution is O(n), where n is the number of fractions in the input string, because each fraction is processed once and the operations involved in the Euclidean algorithm take constant time.

Solution Code:


class Solution {
public:
    string fractionAddition(string expression) {
    istringstream in(expression);
    int A = 0, B = 1, a, b;
    char _;
    while (in >> a >> _ >> b) {
        A = A * b + a * B;
        B *= b;
        int g = abs(__gcd(A, B));
        A /= g;
        B /= g;
    }
    return to_string(A) + '/' + to_string(B);
}
};

'알고리즘' 카테고리의 다른 글

Binary Tree Postorder Traversal  (0) 2025.02.10
Find the Closest Palindrome  (0) 2025.02.10
Number Complement  (0) 2025.02.10
Stone Game II  (0) 2025.02.10
2 Keys Keyboard  (0) 2025.02.10
블로그 이미지

짬뽕얼큰하게

,

Number Complement

알고리즘 2025. 2. 10. 08:54

Leetcode Problem:

Summary

  • This problem requires finding the complement of a given integer
  • The complement is the integer that is obtained by flipping all the 0's to 1's and all the 1's to 0's in the binary representation of the given integer.

Approach

  • The approach used in the solution is to use a bitmask to keep track of the bits that have been flipped
  • The bitmask is initialized to 1 and is shifted left by 1 bit in each iteration
  • If the current bit in the bitmask is not set in the given integer, it is added to the result
  • This process continues until the bitmask is greater than or equal to the given integer.

Complexity

  • The time complexity of the solution is O(log n), where n is the given integer
  • This is because the while loop runs for log n iterations, where log n is the number of bits in the binary representation of the given integer.

Explain

  • Here is the solution code with comments: class Solution { public: int findComplement(int num) { // Initialize the result to 0 int res = 0; // Initialize the bitmask to 1 unsigned int bitmask = 1; // Continue the loop until the bitmask is greater than or equal to the given integer while(bitmask < num){ // If the current bit in the bitmask is not set in the given integer, // add the bitmask to the result if(!(bitmask & num)){ res += bitmask; } // Shift the bitmask left by 1 bit for the next iteration bitmask <<= 1; } // Return the result return res; } };

Solution Code:


class Solution {
public:
    int findComplement(int num) {
        int res = 0;
        unsigned int bitmask = 1;
        while(bitmask < num){
            if(!(bitmask & num)){
                res += bitmask;
            }
            bitmask <<= 1;
        }
        return res;
    }
};

'알고리즘' 카테고리의 다른 글

Find the Closest Palindrome  (0) 2025.02.10
Fraction Addition and Subtraction  (0) 2025.02.10
Stone Game II  (0) 2025.02.10
2 Keys Keyboard  (0) 2025.02.10
Ugly Number II  (0) 2025.02.10
블로그 이미지

짬뽕얼큰하게

,

Stone Game II

알고리즘 2025. 2. 10. 08:46

Leetcode Problem:

Summary

  • The problem is to find the maximum number of stones Alice can get in a game where Alice and Bob take turns taking stones from piles.

Approach

  • The approach is to use dynamic programming and memoization to calculate the maximum number of stones Alice can get
  • The idea is to calculate the suffix sums of the piles and then use a recursive function to calculate the maximum number of stones Alice can get by taking stones from the first X piles, where 1 <= X <= 2M.

Complexity

  • O(n * 2M) where n is the number of piles and M is the maximum number of piles Alice can take in a turn.

Explain

  • The solution code first calculates the suffix sums of the piles
  • Then it defines a recursive function take_stones that calculates the maximum number of stones Alice can get by taking stones from the first X piles
  • The function uses memoization to avoid redundant calculations
  • Finally, the solution returns the result of the recursive function with m = 1.

Solution Code:


from functools import lru_cache


class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        suffix_sums = [0 for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            suffix_sums[i] = piles[i] + suffix_sums[i + 1]

        @lru_cache(maxsize=None)
        def take_stones(i, m):
            if i >= n:
                return 0
            if i + 2 * m >= n:
                return suffix_sums[i]
            return suffix_sums[i] - min(
                take_stones(i + x, max(m, x)) for x in range(1, 2 * m + 1)
            )

        return take_stones(0, 1)

'알고리즘' 카테고리의 다른 글

Fraction Addition and Subtraction  (0) 2025.02.10
Number Complement  (0) 2025.02.10
2 Keys Keyboard  (0) 2025.02.10
Ugly Number II  (0) 2025.02.10
Maximum Distance in Arrays  (0) 2025.02.10
블로그 이미지

짬뽕얼큰하게

,

2 Keys Keyboard

알고리즘 2025. 2. 10. 08:43

Leetcode Problem:

Summary

  • The problem is to find the minimum number of operations required to have the character 'A' exactly n times on the screen, given the ability to copy and paste characters.

Approach

  • The approach used is to use a queue to store the nodes representing the state of the notepad, where each node contains the number of actions taken, the number of copied characters, and the number of 'A's on the screen
  • The algorithm starts with the initial state (one 'A' on the screen) and explores all possible next states by either copying or pasting characters, and keeps track of the minimum number of actions required to reach the desired state.

Complexity

  • The time complexity of the solution is O(n^2), where n is the number of 'A's on the screen, as each node is visited at most once.

Explain

  • The solution uses a queue to store the nodes representing the state of the notepad
  • Each node contains the number of actions taken (actionCnt), the number of copied characters (copiedCnt), and the number of 'A's on the screen (aCnt)
  • The algorithm starts with the initial state (one 'A' on the screen) and explores all possible next states by either copying or pasting characters
  • The next states are added to the queue if they have not been visited before
  • The algorithm stops when it reaches the desired state (n 'A's on the screen) and returns the minimum number of actions required to reach that state.

Solution Code:


struct Node{
    int actionCnt;
    int copiedCnt;
    int aCnt;
};

class Solution {
public:
    queue que;
    bool visited[2001][2001];
    int minSteps(int n) {
        que.push({0, 0, 1});
        visited[0][1] = true;
        while(!que.empty()){
            Node nod = que.front();
            que.pop();
            if (nod.aCnt == n){
                return nod.actionCnt;
            }
            int nextCopied = nod.aCnt;
            int nextAcnt = nod.aCnt + nod.copiedCnt;
            if (nextCopied <= 1000 && !visited[nextCopied][nod.aCnt]){
                visited[nextCopied][nod.aCnt] = true;
                que.push({nod.actionCnt + 1,nextCopied, nod.aCnt });
            }
            if (nextAcnt <= 1000 && !visited[nod.copiedCnt][nextAcnt]){
                visited[nod.copiedCnt][nextAcnt] = true;
                que.push({nod.actionCnt + 1,nod.copiedCnt, nextAcnt });
            }
        }
        return 0;
    }
};

'알고리즘' 카테고리의 다른 글

Number Complement  (0) 2025.02.10
Stone Game II  (0) 2025.02.10
Ugly Number II  (0) 2025.02.10
Maximum Distance in Arrays  (0) 2025.02.10
Count Number of Bad Pairs  (0) 2025.02.09
블로그 이미지

짬뽕얼큰하게

,

Ugly Number II

알고리즘 2025. 2. 10. 08:39

Leetcode Problem:

Summary

  • Find the nth ugly number which is a positive integer whose prime factors are limited to 2, 3, and 5.

Approach

  • Use a min-heap to store the ugly numbers and a map to keep track of processed numbers
  • The algorithm starts by pushing 1 into the heap and then repeatedly pops the smallest number, multiplies it by 2, 3, and 5, and pushes the results back into the heap until the nth ugly number is found.

Complexity

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

Explain

  • The solution uses a min-heap to efficiently store and retrieve the ugly numbers
  • The `push` operation is used to add a new ugly number to the heap, and the `pop` operation is used to remove the smallest ugly number from the heap
  • The algorithm also uses a map to keep track of processed numbers to avoid duplicates
  • The time complexity of the solution is O(n log n) due to the heap operations, where n is the input number.

Solution Code:


struct _heap{
    long long arr[10000];
    int size;
    _heap(){
        size = 1;
    }
    void push(long long a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && arr[idx] < arr[idx/2]){
            long long t = arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = t;
            idx/=2;
        }
    }
    long long pop(){
        long long 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] > arr[j+1]){
                j++;
            }
            if(arr[j] < arr[i]){
                long long t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
                i = j;
            }
            else {
                break;
            }
        }
        return ret;
    }
};

class Solution {
public:
    _heap pq;
    unordered_map processed;
    int nthUglyNumber(int n) {
        if (n == 1) return 1;
        int idx = 1;
        pq.push(1); 
        long long num = 1;      
        while(n--){
            num = pq.pop();
            if (processed[num]) {
                n++;
                continue;
            }
            processed[num] = true;
            pq.push(num*2);
            pq.push(num*3);
            pq.push(num*5);
        }
        return num;
    }
};

'알고리즘' 카테고리의 다른 글

Stone Game II  (0) 2025.02.10
2 Keys Keyboard  (0) 2025.02.10
Maximum Distance in Arrays  (0) 2025.02.10
Count Number of Bad Pairs  (0) 2025.02.09
Find K-th Smallest Pair Distance  (0) 2025.02.09
블로그 이미지

짬뽕얼큰하게

,

Maximum Distance in Arrays

알고리즘 2025. 2. 10. 08:36

Leetcode Problem:

Summary

  • Finding the maximum distance between two numbers from different sorted arrays.

Approach

  • This solution uses two pointers to track the minimum and maximum values from each array
  • It keeps track of the indices and values of these numbers to find the maximum distance.

Complexity

  • O(m * log(m)) due to sorting the arrays, where m is the number of arrays.

Explain

  • The solution first initializes variables to store the minimum and maximum values from each array
  • It then iterates through each array to find the minimum and maximum values
  • After finding these values, it checks if the maximum and minimum values are from the same array or different arrays
  • If they are from the same array, it calculates the distance between them
  • If they are from different arrays, it calculates the distance between the maximum value and the minimum value from the same array, and the distance between the maximum value and the minimum value from the other array
  • It then returns the maximum of these distances.

Solution Code:


struct number{
    int idx;
    int value;
};
class Solution {
public:
    int ABS(int x){
        return x < 0 ? -x: x;
    }
    int maxDistance(vector>& arrays) {
        number minNum = {0, 10001};
        number secondMinNum = {0, 10001};

        number maxNum = {0, -10001};
        number secondMaxNum = {0, -10001};

        for(int i = 0 ; i < arrays.size(); i++){
            int minValue = arrays[i][0];
            int maxValue = arrays[i][arrays[i].size() - 1];
            if (minValue 
                secondMinNum.value = minNum.value;
                secondMinNum.idx = minNum.idx;
                minNum.value = minValue;
                minNum.idx = i;
            } else if (minValue < secondMinNum.value){
                secondMinNum.value = minValue;
                secondMinNum.idx = i;
            }

            if (maxValue > maxNum.value){
                secondMaxNum.value = maxNum.value;
                secondMaxNum.idx = maxNum.idx;
                maxNum.value = maxValue;
                maxNum.idx = i;
            } else if (maxValue > secondMaxNum.value){
                secondMaxNum.value = maxValue;
                secondMaxNum.idx = i;
            }
        }
        if (maxNum.idx != minNum.idx){
            return ABS(maxNum.value - minNum.value);
        } else{
            int a = ABS(maxNum.value - secondMinNum.value);
            int b = ABS(secondMaxNum.value - minNum.value);
            return a > b ? a : b;
        }

    }
};

'알고리즘' 카테고리의 다른 글

2 Keys Keyboard  (0) 2025.02.10
Ugly Number II  (0) 2025.02.10
Count Number of Bad Pairs  (0) 2025.02.09
Find K-th Smallest Pair Distance  (0) 2025.02.09
Combination Sum II  (0) 2025.02.09
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/02   »
일 월 화 수 목 금 토
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28

티스토리툴바