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

Path with Maximum Probability

알고리즘 2025. 2. 11. 08:49

Leetcode Problem:

Summary

  • Find the path with the maximum probability of success to go from start to end in an undirected weighted graph.

Approach

  • This solution uses a breadth-first search (BFS) approach with a priority queue
  • It starts from the start node and explores all its neighbors
  • For each neighbor, it calculates the maximum probability of success and updates the visited array
  • The process continues until the end node is reached or all nodes are visited.

Complexity

  • O(n + m * log n) where n is the number of nodes and m is the number of edges

Explain

  • The code defines a graph using an adjacency list representation
  • It initializes a visited array to keep track of visited nodes and a queue to store nodes to be visited
  • The main function takes the number of nodes, edges, and probabilities as input and returns the maximum probability of success
  • It uses a BFS approach to explore all nodes and calculates the maximum probability of success for each node
  • The time complexity is O(n + m * log n) due to the priority queue operations.

Solution Code:


struct Node{
    int nod;
    double prob;
};
struct QNode{
    int nod;
    double probSum;
};
class Solution {
public:
    vector v[10001];
    double visited[10001] = {0};
    queue q;
    double maxProbability(int n, vector>& edges, vector& succProb, int start_node, int end_node) {
        double ans = 0;
        for(int i = 0 ; i < edges.size();i++){
            double prob = succProb[i];
            int a = edges[i][0];
            int b = edges[i][1];
            v[a].push_back({b, prob});
            v[b].push_back({a, prob});
        }
        visited[start_node] = 1;
        q.push({start_node, 1});
        while(!q.empty()){
            QNode nod = q.front();
            q.pop();
            if (nod.nod == end_node){
                if(ans < nod.probSum){
                    ans = nod.probSum;
                }
            }
            for(int i = 0 ; i < v[nod.nod].size(); i++){
                Node nextNod = v[nod.nod][i];
                if(nextNod.nod != end_node && visited[nextNod.nod] >= nod.probSum * nextNod.prob){
                    continue;
                }
                if (visited[nextNod.nod] < nod.probSum * nextNod.prob){
                    visited[nextNod.nod] = nod.probSum * nextNod.prob;
                }
                q.push({nextNod.nod, nod.probSum * nextNod.prob});
            }
        }
        
        return ans;

    }
};

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

Find the Student that Will Replace the Chalk  (0) 2025.02.11
Convert 1D Array Into 2D Array  (0) 2025.02.11
Most Stones Removed with Same Row or Column  (0) 2025.02.11
Count Sub Islands  (0) 2025.02.11
Clear Digits  (0) 2025.02.10
블로그 이미지

짬뽕얼큰하게

,

Most Stones Removed with Same Row or Column

알고리즘 2025. 2. 11. 08:41

Leetcode Problem:

Summary

  • Given a 2D plane with n stones, remove the maximum number of stones that can be removed if a stone can be removed if it shares either the same row or the same column as another stone that has not been removed.

Approach

  • Use a union-find data structure to group stones that share the same row or column
  • Then, count the number of connected components to determine the maximum number of stones that can be removed.

Complexity

  • O(n + m) where n is the number of stones and m is the maximum column or row value

Explain

  • Create two maps to store the columns and rows of each stone
  • Then, iterate over each stone and add its column and row to the corresponding maps
  • After that, create a visited array to keep track of the stones that have been visited
  • Then, iterate over each stone and use a helper function to mark all the stones in the same row or column as visited
  • Finally, count the number of connected components in the visited array to determine the maximum number of stones that can be removed.

Solution Code:


class Solution {
public:
    vector cols[10000];
    vector rows[10000];
    bool visited[1000];
    map getIdx;
    void fill(int r, int c){
        int idx = getIdx[r*10000+c];
        if (visited[idx]) return;
        visited[idx] = true;
        for(int i = 0 ; i < cols[r].size(); i++){
            fill(r, cols[r][i]);
        }
        for(int i = 0 ; i < rows[c].size(); i++){
            fill(rows[c][i], c);
        }
    }
    int removeStones(vector>& stones) {
        for(int i = 0 ; i < stones.size(); i++){
            int r = stones[i][0];
            int c = stones[i][1];
            cols[r].push_back(c);
            rows[c].push_back(r);
            getIdx[r*10000+c] = i;
        }
        int uni = 0;
        for(int i = 0 ; i < stones.size(); i++){
            if(visited[i]) continue;
            uni++;
            fill(stones[i][0], stones[i][1]);
        }
        return stones.size() - uni;
    }
};

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

Convert 1D Array Into 2D Array  (0) 2025.02.11
Path with Maximum Probability  (0) 2025.02.11
Count Sub Islands  (0) 2025.02.11
Clear Digits  (0) 2025.02.10
N-ary Tree Postorder Traversal  (0) 2025.02.10
블로그 이미지

짬뽕얼큰하게

,

Count Sub Islands

알고리즘 2025. 2. 11. 08:38

Leetcode Problem:

Summary

  • Given two binary matrices grid1 and grid2, find the number of islands in grid2 that are sub-islands of islands in grid1.

Approach

  • The approach used is to first fill the grid1 with a unique number representing each island
  • Then, for each cell in grid2, check if it is part of an island in grid1 and if it is a sub-island by recursively checking all its neighboring cells.

Complexity

  • O(m*n*log(m*n)) where m and n are the dimensions of the grid, due to the recursive DFS in the checkSubIsland function.

Explain

  • The solution uses a depth-first search (DFS) approach to fill the grid1 with a unique number representing each island
  • Then, for each cell in grid2, it checks if the cell is part of an island in grid1 by looking up the visited1 grid
  • If the cell is part of an island, it then checks if the cell is a sub-island by recursively calling the checkSubIsland function on all its neighboring cells
  • The count of sub-islands is then incremented and returned as the result.

Solution Code:


class Solution {
public:
    int visited1[501][501];
    int visited2[501][501];
    bool GRID1[501][501];
    bool GRID2[501][501];
    int R, C;
    void fill(int r, int c, int v){
        if (r < 0 || r >= R || c < 0 || c >= C || visited1[r][c] || GRID1[r][c] == 0) return;
        visited1[r][c] = v;
        fill(r + 1, c, v);
        fill(r - 1, c, v);
        fill(r, c + 1, v);
        fill(r, c - 1, v);
    }
    bool checkSubIsland(int r, int c, int v){
        if (r < 0 || r >= R || c < 0 || c >= C || visited2[r][c] || GRID2[r][c] == 0) return true;
        if (visited1[r][c] != v) return false;
        visited2[r][c] = true;
        bool ret = true;
        if (!checkSubIsland(r + 1, c, v)){
            ret = false;
        }
        if (!checkSubIsland(r - 1, c, v)){
            ret = false;
        }
        if (!checkSubIsland(r, c + 1, v)){
            ret = false;
        }
        if (!checkSubIsland(r, c - 1, v)){
            ret = false;
        }

        return ret;
    }
    int countSubIslands(vector>& grid1, vector>& grid2) {
        R = grid1.size();
        C = grid1[0].size();
        for(int i = 0 ; i < R; i++){
            for(int j = 0 ; j < C; j++){
                GRID1[i][j] = grid1[i][j];
                GRID2[i][j] = grid2[i][j];
            }
        }
        int cnt = 1;
        for(int i = 0 ; i < R; i++){
            for(int j = 0 ; j < C; j++){
                if(GRID1[i][j] && !visited1[i][j]){
                    fill(i, j, cnt);
                    cnt++;
                }
            }
        }


        int ans = 0;
        for(int i = 0; i < R; i++){
            for(int j = 0 ; j < C; j++){
                if(GRID2[i][j] && visited1[i][j] && !visited2[i][j]){
                    if(checkSubIsland(i, j, visited1[i][j])){
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
};

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

Path with Maximum Probability  (0) 2025.02.11
Most Stones Removed with Same Row or Column  (0) 2025.02.11
Clear Digits  (0) 2025.02.10
N-ary Tree Postorder Traversal  (0) 2025.02.10
Binary Tree Postorder Traversal  (0) 2025.02.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
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   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

티스토리툴바