koenjazh-CNfresde
짬뽕얼큰하게의 맨땅에 헤딩 :: 'LeetCode' 태그의 글 목록 (20 Page)

'LeetCode'에 해당되는 글 250건

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
블로그 이미지

짬뽕얼큰하게

,

Count Number of Bad Pairs

알고리즘 2025. 2. 9. 09:45

Leetcode Problem:

Summary

  • The problem requires to find the total number of bad pairs in a given integer array
  • A bad pair is defined as a pair of indices (i, j) where i < j and j - i!= nums[j] - nums[i].

Approach

  • The approach used in the solution is to first modify the input array by adding the difference between the current index and the total length of the array to each element
  • This is done to simplify the calculation of bad pairs
  • Then, a hashmap is used to store the frequency of each modified element
  • Finally, the total number of bad pairs is calculated by subtracting the sum of the first 'N' natural numbers (where N is the length of the array) from the total possible pairs and subtracting the sum of the frequencies of each modified element multiplied by the frequency minus one divided by two.

Complexity

  • O(N) where N is the length of the input array

Explain

  • The solution starts by modifying the input array by adding the difference between the current index and the total length of the array to each element
  • This is done to simplify the calculation of bad pairs
  • Then, a hashmap is used to store the frequency of each modified element
  • The total number of bad pairs is calculated by subtracting the sum of the first 'N' natural numbers (where N is the length of the array) from the total possible pairs and subtracting the sum of the frequencies of each modified element multiplied by the frequency minus one divided by two
  • This is because a pair is bad if the difference between the two elements is not equal to the difference between their indices
  • By using the hashmap, we can efficiently count the number of bad pairs.

Solution Code:


class Solution {
public:
    unordered_map map;
    long long countBadPairs(vector& nums) {
        int N = nums.size();
        for(int i = 0 ; i < N; i++){
            nums[i] += N - i;
        }
        for(int i = 0 ; i < N; i++){
            map[nums[i]]++;
        }
        long long cnt = 0;
        for(auto iter : map){
            if(iter.second >= 2){
                cnt += ((iter.second) * (iter.second-1)) >> 1;
            }
        }
        return (((long long)N * (N-1)) >> 1) - cnt;
    }
};

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

Ugly Number II  (0) 2025.02.10
Maximum Distance in Arrays  (0) 2025.02.10
Find K-th Smallest Pair Distance  (0) 2025.02.09
Combination Sum II  (0) 2025.02.09
Kth Largest Element in a Stream  (0) 2025.02.09
블로그 이미지

짬뽕얼큰하게

,

Find K-th Smallest Pair Distance

알고리즘 2025. 2. 9. 08:51

Leetcode Problem:

Summary

  • Find the kth smallest distance among all pairs of integers in an array.

Approach

  • Binary Search: The solution uses a binary search approach to find the kth smallest distance
  • It sorts the array and then uses two pointers (l and r) to represent the range of possible distances
  • The solution iterates through the range, calculating the number of pairs that have a distance less than or equal to the current mid value
  • If the number of pairs is greater than or equal to k, the solution updates the answer and moves the right pointer to the left
  • Otherwise, it moves the left pointer to the right.

Complexity

  • O(N log N + log k) where N is the length of the array
  • The sorting operation takes O(N log N) time, and the binary search takes O(log k) time.

Explain

  • The solution first sorts the array in ascending order
  • It then initializes two pointers, l and r, to represent the range of possible distances
  • The solution iterates through the range, calculating the number of pairs that have a distance less than or equal to the current mid value
  • If the number of pairs is greater than or equal to k, the solution updates the answer and moves the right pointer to the left
  • Otherwise, it moves the left pointer to the right
  • The solution repeats this process until the left pointer is greater than the right pointer
  • The final answer is the smallest distance that results in k pairs.

Solution Code:


class Solution {
public:
    int smallestDistancePair(vector& nums, int k) {
        sort(nums.begin(), nums.end());
        int N = nums.size();
        int l = 0;
        int r = 1000000;
        int ans = 0;
        while(l <= r ){
            int mid = (l + r) / 2;
            int left = 0;
            int right = 0;
            int cnt = 0;
            int beforeRight = 0;
            while(right < N){
                while(right < N && nums[right] - nums[left] <= mid){
                    right++;
                }
                int NN = right - left;
                cnt += (NN * (NN-1))/2;
                if (left != 0){
                    NN = (beforeRight - left);
                    cnt -= (NN * (NN-1))/2;
                }
                beforeRight = right;
                while(left < right && nums[right] - nums[left] > mid){
                    left++;
                }
            }
            if (cnt >= k){
                if (cnt == k){
                    ans = mid;
                }
                ans = mid;
                r = mid - 1;
            } else{
                l = mid + 1;
            }
        }
        return ans;
    }
};

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

Maximum Distance in Arrays  (0) 2025.02.10
Count Number of Bad Pairs  (0) 2025.02.09
Combination Sum II  (0) 2025.02.09
Kth Largest Element in a Stream  (0) 2025.02.09
Minimum Number of Days to Disconnect Island  (0) 2025.02.09
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/04   »
일 월 화 수 목 금 토
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 29 30

티스토리툴바