'2025/02 글 목록 (11 Page)

Minimum Bit Flips to Convert Number

알고리즘 2025. 2. 12. 08:48

Leetcode Problem:
Minimum Bit Flips to Convert Number

Summary

Find the minimum number of bit flips to convert start to goal.

Approach

This solution works by continuously dividing both start and goal by 2 (using bitwise right shift) until they are both 0
In each iteration, it checks if the least significant bit of start and goal are different
If they are, it increments the answer by 1
This is because flipping the least significant bit of either start or goal (or both) requires one bit flip.

Complexity

O(log min(start, goal))

Explain

The time complexity of this solution is O(log min(start, goal)) because in each iteration, the size of start and goal is halved
The space complexity is O(1) because only a constant amount of space is used.

Solution Code:


class Solution {
public:
    int minBitFlips(int start, int goal) {
        int ans = 0;
        while(!(start == 0 && goal == 0)){
            if((start & 1) != (goal & 1)) ans++;
            start >>= 1;
            goal >>= 1;
        }
        return ans;
    }
};

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

XOR Queries of a Subarray (0)	2025.02.12
Count the Number of Consistent Strings (0)	2025.02.12
Insert Greatest Common Divisors in Linked List (0)	2025.02.12
Spiral Matrix IV (0)	2025.02.12
Linked List in Binary Tree (0)	2025.02.12

짬뽕얼큰하게

,

Insert Greatest Common Divisors in Linked List

알고리즘 2025. 2. 12. 08:45

Leetcode Problem:
Insert Greatest Common Divisors in Linked List

Summary

Inserting greatest common divisors between adjacent nodes in a linked list

Approach

The approach used is to traverse the linked list and for each pair of adjacent nodes, calculate the greatest common divisor (GCD) using the Euclidean algorithm
A new node is then inserted between the two nodes with the calculated GCD
The process is repeated until all nodes have been processed.

Complexity

O(n), where n is the number of nodes in the linked list

Explain

The provided C++ code defines a solution to the problem
The `_gcd` function calculates the GCD of two numbers using the Euclidean algorithm
The `insertGreatestCommonDivisors` function traverses the linked list, calculates the GCD of each pair of adjacent nodes, and inserts a new node with the calculated GCD between the two nodes
The process is repeated until all nodes have been processed, resulting in a linked list with the GCDs inserted between adjacent nodes.

Solution Code:


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int _gcd(int a, int b){
        if(a % b == 0) return b;
        return _gcd(b, a%b);
    }
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* ptr = head;
        while(ptr->next != nullptr){
            int a = ptr->val;
            int b = ptr->next->val;
            ListNode* newNode = new ListNode(_gcd(a, b), ptr->next);
            ptr->next = newNode;
            ptr = newNode->next;
        }
        return head;
    }
};

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

Count the Number of Consistent Strings (0)	2025.02.12
Minimum Bit Flips to Convert Number (0)	2025.02.12
Spiral Matrix IV (0)	2025.02.12
Linked List in Binary Tree (0)	2025.02.12
Remove All Occurrences of a Substring (0)	2025.02.11

짬뽕얼큰하게

,

Spiral Matrix IV

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

Leetcode Problem:
Spiral Matrix IV

Summary

Generate a spiral matrix from a linked list of integers

Approach

Use a spiral traversal algorithm to fill the matrix in a clockwise direction

Complexity

O(R*C + N)

Explain

The solution uses a spiral traversal algorithm to fill the matrix in a clockwise direction
The algorithm starts from the top-left corner of the matrix and moves in a spiral pattern until all elements have been visited
The matrix is represented as a 2D vector, and the algorithm uses two arrays `dy` and `dx` to keep track of the direction of movement
The `R` and `C` variables represent the number of rows and columns in the matrix, respectively
The algorithm also uses a `while` loop to iterate through the linked list and fill the matrix with the corresponding values
The remaining empty spaces in the matrix are filled with -1.

Solution Code:


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector> ans;
    
    int R, C;
    vector> spiralMatrix(int m, int n, ListNode* head) {
        int dy[] = {0, 1, 0, -1};
        int dx[] = {1, 0, -1, 0};
        R = m;
        C = n;

        vector> ans(m, vector(n, -1));
        int r = 0;
        int c = 0;
        int dir = 0;
        while(head){
            ans[r][c] = head->val;
            int nr = r + dy[dir];
            int nc = c + dx[dir];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C || ans[nr][nc] != -1){
                dir = (dir + 1) %4;
                nr = r + dy[dir];
                nc = c + dx[dir];
            }
            r = nr;
            c = nc;
            head = head->next;
        }
        return ans;
    }
};

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

Minimum Bit Flips to Convert Number (0)	2025.02.12
Insert Greatest Common Divisors in Linked List (0)	2025.02.12
Linked List in Binary Tree (0)	2025.02.12
Remove All Occurrences of a Substring (0)	2025.02.11
Delete Nodes From Linked List Present in Array (0)	2025.02.11

짬뽕얼큰하게

,

Linked List in Binary Tree

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

Leetcode Problem:
Linked List in Binary Tree

Summary

Check if all elements in a linked list are present in a binary tree

Approach

This solution first traverses the linked list and stores its elements in a vector
Then it creates a hash table to store the indices of the elements in the vector
It then checks if the binary tree contains all the elements of the linked list by traversing the tree and using the hash table to keep track of the current position in the linked list.

Complexity

O(n*m) where n is the number of nodes in the binary tree and m is the number of nodes in the linked list

Explain

The solution works by first storing the elements of the linked list in a vector
It then creates a hash table to store the indices of the elements in the vector
This is done by iterating over the vector and storing the index of each element in the hash table
The hash table is used to keep track of the current position in the linked list when traversing the binary tree
If the binary tree contains all the elements of the linked list, the solution returns true
Otherwise, it returns false.

Solution Code:


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * 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 listNode;
    int pi[100];
    int match;
    bool traversal(TreeNode* root, int match){
        if (match == listNode.size()) return true;
        if(root == nullptr) return false;
        while(match != 0 && root->val != listNode[match]){
            match = pi[match -1];
        }
        if(root->val == listNode[match]){
            match++;
        }
        if (traversal(root->left, match)){
            return true;
        }
        if (traversal(root->right, match)){
            return true;
        }
        return false;
    }
    bool isSubPath(ListNode* head, TreeNode* root) {
        while(head){
            listNode.push_back(head->val);
            head = head->next;
        }
        match = 0;
        for(int i = 1; i < listNode.size(); i++){
            while(match != 0 && listNode[i] != listNode[match]){
                match = pi[match-1];
            }
            if(listNode[i] == listNode[match]){
                match++;
            }
            pi[i] = match;
        }
        if (traversal(root, 0)){
            return true;
        }
        return false;
    }
};

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

Insert Greatest Common Divisors in Linked List (0)	2025.02.12
Spiral Matrix IV (0)	2025.02.12
Remove All Occurrences of a Substring (0)	2025.02.11
Delete Nodes From Linked List Present in Array (0)	2025.02.11
Find Missing Observations (0)	2025.02.11

짬뽕얼큰하게

,

Remove All Occurrences of a Substring

알고리즘 2025. 2. 11. 23:11

Leetcode Problem:
Remove All Occurrences of a Substring

Summary

Given a string s and a substring part, remove all occurrences of part from s

Approach

Use a stack data structure to keep track of the characters in s and check for occurrences of part
If part is found, remove it from the stack by popping the characters one by one.

Complexity

O(n*m) where n is the length of s and m is the length of part

Explain

The solution iterates over the string s and checks for occurrences of part by comparing the characters at the end of part with the characters in the stack
If part is found, it removes it from the stack by popping the characters one by one
The time complexity is O(n*m) because in the worst case, the stack size can be n and the number of occurrences of part can be m.

Solution Code:


class Solution {
public:
    vector st;
    string removeOccurrences(string s, string part) {
        for(int i = 0 ; i < s.size(); i++){
            st.push_back(s[i]);
            if(st.size() >= part.size()){
                bool success = true;
                for(int j = 0; j < part.size(); j++){
                    if(st[st.size()-j -1] != part[part.size() - j - 1]){
                        success = false;
                        break;
                    }
                }
                if(success){
                    for(int j = 0 ; j < part.size(); j++){
                        st.pop_back();
                    }
                }
            }
        }
        string ans = "";
        for(int i = 0 ; i < st.size(); i++){
            ans += st[i];
        }
        return ans;
    }
};

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

Spiral Matrix IV (0)	2025.02.12
Linked List in Binary Tree (0)	2025.02.12
Delete Nodes From Linked List Present in Array (0)	2025.02.11
Find Missing Observations (0)	2025.02.11
Walking Robot Simulation (0)	2025.02.11

짬뽕얼큰하게

,

Delete Nodes From Linked List Present in Array

알고리즘 2025. 2. 11. 09:09

Leetcode Problem:
Delete Nodes From Linked List Present in Array

Summary

Given an array of integers and the head of a linked list, return the head of the modified linked list after removing nodes with values that exist in the array.

Approach

Use a set to store the values in the array, then traverse the linked list and create a new linked list with only the nodes that have values not in the set.

Complexity

O(n + m) where n is the number of nodes in the linked list and m is the number of elements in the array

Explain

The solution works by first creating a set of the values in the array
Then it traverses the linked list, checking if each node's value is in the set
If it is, the node is skipped
If not, a new node is created with the same value and it becomes the head of the modified linked list
This process continues until all nodes have been traversed.

Solution Code:


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    set s;
    ListNode* ans;
    void traversal(ListNode* head){
        if (head == nullptr) return;
        traversal(head->next);
        if( s.find(head->val) != s.end()) return;

        ListNode* temp = new ListNode(head->val, ans);
        ans = temp;
    }
    ListNode* modifiedList(vector& nums, ListNode* head) {
        for(int i = 0 ; i < nums.size(); i++){
            s.insert(nums[i]);
        }
        traversal(head);
        return ans;    
    }
};

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

Linked List in Binary Tree (0)	2025.02.12
Remove All Occurrences of a Substring (0)	2025.02.11
Find Missing Observations (0)	2025.02.11
Walking Robot Simulation (0)	2025.02.11
Sum of Digits of String After Convert (0)	2025.02.11

짬뽕얼큰하게

,

Find Missing Observations

알고리즘 2025. 2. 11. 09:06

Leetcode Problem:
Find Missing Observations

Summary

Find the missing 6-sided dice rolls to achieve a given average value.

Approach

This solution calculates the total sum of all rolls by multiplying the mean by the total number of rolls
It then subtracts the sum of the known rolls from the total sum to find the sum of the missing rolls
The solution then iterates through the missing rolls, assigning the average value to each roll and adjusting the value if necessary to ensure the total sum is divisible by the total number of rolls.

Complexity

O(n)

Explain

The time complexity of this solution is O(n) because it iterates through the missing rolls once
The space complexity is O(n) because it stores the missing rolls in a vector.

Solution Code:


class Solution {
public:
    vector missingRolls(vector& rolls, int mean, int n) {
        vector ans;
        int m = rolls.size();
        int totalSum = (m + n) * mean;
        for(int i = 0 ; i < m; i++){
            totalSum -= rolls[i];
        }
        if(totalSum < n || totalSum > n*6) return ans;
        for(int i = 0 ; i < n; i++){
            ans.push_back(totalSum/n);
            if (totalSum % n != 0){
                ans[i] += 1;
                totalSum--;
            }
        }
        return ans;
    }
};

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

Remove All Occurrences of a Substring (0)	2025.02.11
Delete Nodes From Linked List Present in Array (0)	2025.02.11
Walking Robot Simulation (0)	2025.02.11
Sum of Digits of String After Convert (0)	2025.02.11
Find the Student that Will Replace the Chalk (0)	2025.02.11

짬뽕얼큰하게

,

Walking Robot Simulation

알고리즘 2025. 2. 11. 09:03

Leetcode Problem:
Walking Robot Simulation

Summary

Find the maximum squared Euclidean distance that a robot can reach in a grid while avoiding obstacles.

Approach

This solution uses a set to store the positions of obstacles and a loop to iterate through the robot's commands
It also uses arrays to represent the possible directions (north, east, south, west) and the current position of the robot
The solution updates the current position of the robot and calculates the maximum squared Euclidean distance at each step.

Complexity

O(n), where n is the number of commands.

Explain

The solution starts by initializing a set to store the positions of obstacles and a variable to store the maximum squared Euclidean distance
It then iterates through the robot's commands, updating the current position of the robot and calculating the maximum squared Euclidean distance at each step
If the robot encounters an obstacle, it skips the current command and continues to the next one
The solution returns the maximum squared Euclidean distance reached by the robot.

Solution Code:


class Solution {
public:
    set> s;
    int robotSim(vector& commands, vector>& obstacles) {
        int ans = 0;
        for(int i = 0 ; i < obstacles.size(); i++){
            int x = obstacles[i][0];
            int y = obstacles[i][1];
            s.insert({y, x});
        }
        int dir = 0;
        int dy[] = {1, 0, -1, 0};
        int dx[] = {0, 1, 0, -1};
        int y = 0;
        int x = 0;
        for(int i = 0 ; i < commands.size(); i++){
            if(commands[i] == -1){
                dir = (dir + 1) %4;
                continue;
            } else if(commands[i] == -2){
                dir = (dir + 3) %4;
                continue;
            } 
            for(int j = 0 ; j < commands[i]; j++){
                int ny = y + dy[dir];
                int nx = x + dx[dir];
                if (ny < -30000 || ny > 30000 || nx < -30000 || nx > 30000) continue;
                if (s.find({ny, nx}) != s.end()){
                    continue;
                }

                y = ny;
                x = nx;
                ans = max(ans, (y*y) + (x * x));
            }
        }
        return ans;
        
    }
};

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

Delete Nodes From Linked List Present in Array (0)	2025.02.11
Find Missing Observations (0)	2025.02.11
Sum of Digits of String After Convert (0)	2025.02.11
Find the Student that Will Replace the Chalk (0)	2025.02.11
Convert 1D Array Into 2D Array (0)	2025.02.11

짬뽕얼큰하게

,

Sum of Digits of String After Convert

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

Leetcode Problem:
Sum of Digits of String After Convert

Summary

This problem involves converting a string into an integer by replacing each letter with its position in the alphabet, then transforming the integer by summing its digits repeatedly k times.

Approach

The approach used is to first convert the string into an integer by subtracting the ASCII value of 'a' from each character and adding 1
Then, the integer is transformed by summing its digits using a helper function
This process is repeated k times.

Complexity

O(n*k) where n is the length of the string and k is the number of transformations.

Explain

The solution code defines a class Solution with two methods: getSum and getLucky
The getSum method takes a string as input and returns the sum of its digits
The getLucky method takes a string and an integer as input and returns the resulting integer after performing the transformations
The getLucky method first converts the string into an integer, then repeatedly transforms the integer by summing its digits using the getSum method
The process is repeated k times, and the final result is returned.

Solution Code:


class Solution {
public:
    int getSum(string s){
        int sum = 0;
        for(int i = 0 ; i < s.size(); i++){
            sum += s[i] - '0';
        }
        return sum;
    }
    int getLucky(string s, int k) {
        string num = "";
        for(int i = 0 ; i < s.size(); i++){
            num += to_string(s[i] - 'a' + 1);
        }
        int transform;
        while(k--){
            transform = getSum(num);
            num = to_string(transform);
        }
        
        return transform;
    }
};

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

Find Missing Observations (0)	2025.02.11
Walking Robot Simulation (0)	2025.02.11
Find the Student that Will Replace the Chalk (0)	2025.02.11
Convert 1D Array Into 2D Array (0)	2025.02.11
Path with Maximum Probability (0)	2025.02.11

짬뽕얼큰하게

,

Find the Student that Will Replace the Chalk

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

Leetcode Problem:
Find the Student that Will Replace the Chalk

Summary

Find the index of the student who will replace the chalk pieces

Approach

The solution uses the modulo operator to find the remaining chalk pieces after each student's turn
It then iterates through the chalk array to find the student who will run out of chalk first.

Complexity

O(n) where n is the number of students

Explain

The solution works by first calculating the total amount of chalk available
It then uses the modulo operator to find the remaining chalk pieces after each student's turn
The student who will run out of chalk first is the one whose index is returned
This approach ensures that the student who will replace the chalk is found efficiently, even for large inputs.

Solution Code:


class Solution {
public:
    int chalkReplacer(vector& chalk, int k) {
        long long sum = 0;
        for(int i = 0 ; i < chalk.size(); i++){
            sum += chalk[i];
        }
        k = k % sum;
        for(int i = 0 ; i < chalk.size(); i++){
            k -= chalk[i];
            if (k < 0) return i;
        }
        return 0;
    }
};

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

Walking Robot Simulation (0)	2025.02.11
Sum of Digits of String After Convert (0)	2025.02.11
Convert 1D Array Into 2D Array (0)	2025.02.11
Path with Maximum Probability (0)	2025.02.11
Most Stones Removed with Same Row or Column (0)	2025.02.11

짬뽕얼큰하게

,

일	월	화	수	목	금	토
						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

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

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

Leetcode Problem: Minimum Bit Flips to Convert Number

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: Insert Greatest Common Divisors in Linked List

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: Spiral Matrix IV

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: Linked List in Binary Tree

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: Remove All Occurrences of a Substring

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: Delete Nodes From Linked List Present in Array

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: Find Missing Observations

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: Walking Robot Simulation

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: Sum of Digits of String After Convert

Summary

Approach

Complexity

Explain

Solution Code:

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

Leetcode Problem: Find the Student that Will Replace the Chalk

Summary

Approach

Complexity

Explain

Solution Code:

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

공지사항

카테고리

태그목록

글 보관함

달력

링크

짬뽕얼큰하게

LATEST FROM OUR BLOG

LATEST COMMENTS

Leetcode Problem:
Minimum Bit Flips to Convert Number

Leetcode Problem:
Insert Greatest Common Divisors in Linked List

Leetcode Problem:
Spiral Matrix IV

Leetcode Problem:
Linked List in Binary Tree

Leetcode Problem:
Remove All Occurrences of a Substring

Leetcode Problem:
Delete Nodes From Linked List Present in Array

Leetcode Problem:
Find Missing Observations

Leetcode Problem:
Walking Robot Simulation

Leetcode Problem:
Sum of Digits of String After Convert

Leetcode Problem:
Find the Student that Will Replace the Chalk