'분류 전체보기'에 해당되는 글 298건

Leetcode Problem:

• Move Pieces to Obtain a String

Summary

• Check if a string can be transformed into another string by moving pieces (L, R, _) a certain number of times.

Approach

• This solution uses a two-pointer approach to iterate over both strings simultaneously
• It checks for the next available position for each piece in both strings and moves them accordingly
• If a piece cannot be moved to its next position, it returns false
• If all pieces can be moved to their next positions, it checks if both strings have been fully traversed and returns true if so, otherwise false.

Complexity

• O(n), where n is the length of the input strings.

Explanation

• The solution defines two helper functions, `nextCharIdx`, to find the next available position for each piece in both strings
• It then iterates over both strings using two pointers, `idx1` and `idx2`, which start at the beginning of each string
• It checks if the current positions in both strings match, and if they do, it moves the pieces to the next position
• If a piece cannot be moved to its next position, it returns false
• If all pieces can be moved to their next positions, it checks if both strings have been fully traversed and returns true if so, otherwise false.

Solution Code:

class Solution {
public:
    int nextCharIdx(string& str, int idx){
        for(int i = idx; i < str.size(); i++){
            if(str[i] == 'L' || str[i] == 'R') return i;
        }
        return str.size();
    }
    bool canChange(string start, string target) {
        int idx1, idx2;
        idx1 = idx2 = 0;
        while(true){
            idx1 = nextCharIdx(start, idx1);
            idx2 = nextCharIdx(target, idx2);
            if(idx1 == start.size() || idx2 == target.size()){       
                break;
            }
            if(start[idx1] != target[idx2]) return false;
            if(start[idx1] == 'L'){
                if(idx1 < idx2){
                    return false;
                }
            }
            if(start[idx1] == 'R'){
                if(idx1 > idx2){
                    return false;
                }
            }
            idx1++;
            idx2++;
        }
        if(idx1 == start.size() && idx2 == target.size()){
            return true;
        }
        return false;
    }
};

Leetcode Problem:

• Make String a Subsequence Using Cyclic Increments

Summary

• Given two strings, check if str2 can be made a subsequence of str1 by performing the operation at most once.

Approach

• The approach used is to iterate over each character in str1 and check if it is equal to the current character in str2 or the next character in str1 (cyclically)
• If it is, increment the pointer for str2.

Complexity

• O(n), where n is the length of str1

Explanation

• The solution iterates over each character in str1 and checks if it is equal to the current character in str2 or the next character in str1 (cyclically)
• If it is, increment the pointer for str2
• If the pointer for str2 reaches the end of str2, return true
• Otherwise, return false.

Solution Code:

class Solution {
public:

    bool canMakeSubsequence(string str1, string str2) {
        int j = 0;
        for(int i = 0 ; i < str1.size(); i++){
            char next = str1[i] == 'z' ? 'a' : str1[i] + 1;
            if(j < str2.size() && (str1[i] == str2[j] || str2[j] == next)){
                j++;
            }
        }
        if (j >= str2.size()) return true;
        return false;
    }
};

Leetcode Problem:

• Adding Spaces to a String

Summary

• Given a string and a vector of indices where spaces need to be added, insert spaces before the characters at the given indices.

Approach

• The approach is to iterate over the vector of indices and for each index, insert a space before the character at that index
• After the loop, add the remaining characters to the string.

Complexity

• O(n), where n is the number of indices in the vector.

Explanation

• The code uses a for loop to iterate over the vector of indices
• For each index, it uses the substr function to get the substring of the original string from the start index to the end index
• It then appends a space to the result string and updates the start index to the end index
• After the loop, it uses the substr function again to get the remaining substring of the original string and appends it to the result string
• The result string is then returned.

Solution Code:

class Solution {
public:
    string addSpaces(string s, vector& spaces) {
        int start = 0;
        int end;
        string ans = "";
        for(int i = 0 ; i < spaces.size(); i++){
            end = spaces[i];
            ans += s.substr(start, end-start);
            ans += " ";
            start = end;
        }
        ans += s.substr(start, s.size()-start);

        return ans;
    }
};

Leetcode Problem:

• Check If a Word Occurs As a Prefix of Any Word in a Sentence

Summary

• Check if a search word is a prefix of any word in a sentence.

Approach

• The approach used is to split the sentence into individual words and then check each word to see if it matches the search word
• If a match is found, the index of the word is returned
• If no match is found, -1 is returned.

Complexity

• O(n*m) where n is the number of words in the sentence and m is the length of the search word.

Explanation

• The solution code starts by splitting the sentence into individual words and storing them in a vector
• Then it iterates over each word and checks if it matches the search word
• If a match is found, the index of the word is returned
• If no match is found, -1 is returned
• The time complexity of this solution is O(n*m) because it needs to iterate over each word in the sentence and each character in the search word.

Solution Code:

class Solution {
public:
    vector words;
    int isPrefixOfWord(string sentence, string searchWord) {
        words.push_back(sentence);
        for(int i =0; i < sentence.size(); i++){
            if(sentence[i] == ' '){
                words.push_back(sentence.substr(i+1));
            }
        }
        for(int i = 0 ; i < words.size(); i++){
            int j = 0;
            for( ; j < searchWord.size(); j++){
                if(searchWord[j] != words[i][j]){
                    break;
                }
            }
            if(j == searchWord.size()){
                return i + 1;
            }
        }
        return -1;
    }
};

Leetcode Problem:

• Check If N and Its Double Exist

Summary

• Check if there exist two indices i and j in the given array such that arr[i] == 2 * arr[j] and i!= j.

Approach

• The approach used is to use a boolean array of size 4004 to keep track of the numbers we have seen so far
• For each number in the array, we check if its double or half exists in the boolean array
• If it does, we return true
• If not, we mark the number as seen in the boolean array.

Complexity

• O(n) where n is the size of the array

Explanation

• The given solution uses a boolean array of size 4004 to keep track of the numbers we have seen so far
• For each number in the array, we check if its double or half exists in the boolean array
• If it does, we return true
• If not, we mark the number as seen in the boolean array
• The time complexity of this solution is O(n) where n is the size of the array, as we are iterating through the array once
• The space complexity is also O(n) as we are using a boolean array of size 4004 to keep track of the numbers we have seen so far.

Solution Code:

class Solution {
public:
    int number[4004];
    bool checkIfExist(vector& arr) {
        for(int i = 0 ; i < arr.size(); i++){
            if (arr[i] & 1) {
                if(number[(arr[i] << 1) + 2000]){
                    return true;
                }
            } else{
                if(number[(arr[i] << 1) + 2000]){
                    return true;
                }
                if(number[(arr[i] >> 1) + 2000]){
                    return true;
                }
            }
            number[arr[i] + 2000] = true;
        }
        return false;
    }
};

Leetcode Problem:

• Valid Arrangement of Pairs

Summary

• Find a valid arrangement of pairs where each pair is connected to the previous one

Approach

• Use a depth-first search (DFS) to traverse the graph of pairs, starting from the node with the highest degree
• The DFS visits all nodes in the graph and constructs a path in reverse order

Complexity

• O(n + e), where n is the number of pairs and e is the number of edges

Explanation

• The solution first builds an adjacency list and degree map to represent the graph of pairs
• It then finds the node with the highest degree, which is the starting point for the DFS
• The DFS visits all nodes in the graph and constructs a path in reverse order, which represents a valid arrangement of pairs

Solution Code:

class Solution {
public:
    unordered_map> adj;
    unordered_map deg;

    vector rpath;
    void euler(int i){
        vector stk={i};
        while(!stk.empty()){
            i = stk.back();
            if(adj[i].empty()){
                rpath.push_back(i);
                stk.pop_back();
            } else{
                int j = adj[i].back();
                adj[i].pop_back();
                stk.push_back(j);
            }
        }
    }

    vector> validArrangement(vector>& pairs) {
        const int e = pairs.size();
        adj.reserve(e);
        deg.reserve(e);

        for(auto& edge : pairs){
            int start = edge[0], end=edge[1];
            adj[start].push_back(end);
            deg[start]++;
            deg[end]--;
        }

        int i0=deg.begin()->first;
        for (auto& [v,d]: deg){
            if(d == 1){
                i0 = v;
                break;
            }
        }
        euler(i0);

        vector> ans;
        ans.reserve(e);

        for(int i = rpath.size() - 2; i >= 0 ; i--){
            ans.push_back({rpath[i+1], rpath[i]});
        }
        return ans;

    }
};

Leetcode Problem:

• Minimum Obstacle Removal to Reach Corner

Summary

• This solution solves the Minimum Obstacles to Remove problem where we need to find the minimum number of obstacles to remove from a 2D grid so we can move from the upper left corner to the lower right corner.

Approach

• This solution uses a priority queue to keep track of the cells to visit
• It uses a heap data structure to efficiently select the cell with the minimum number of obstacles to remove
• It also uses a visited matrix to keep track of the cells that have been visited to avoid revisiting them.

Complexity

• O(m * n * log(m * n))

Explanation

• The solution first initializes a visited matrix and a priority queue
• It then starts by pushing the starting cell into the priority queue
• The priority queue is implemented as a binary heap
• The solution then enters a loop where it pops the cell with the minimum number of obstacles to remove from the priority queue and checks its neighbors
• If a neighbor is an obstacle, it pushes the neighbor into the priority queue with an increased number of obstacles to remove
• If a neighbor is not an obstacle, it pushes the neighbor into the priority queue with the same number of obstacles to remove
• The solution continues this process until it reaches the destination cell or until all reachable cells have been visited
• The time complexity of this solution is O(m * n * log(m * n)) because the priority queue operations (push and pop) take O(log(m * n)) time and we perform these operations m * n times.

Solution Code:

struct _node{
    int r;
    int c;
    int moveCnt;
    int removeCnt;
};
struct _heap{
    int size;
    _node arr[1000001];
    _heap(){
        size = 1;
    }
    bool _cmp(_node a, _node b){
        if(a.removeCnt != b.removeCnt){
            return a.removeCnt < b.removeCnt;
        }
        return a.moveCnt < b.moveCnt;

    }
    void push(_node a){
        arr[size++] = a;
        int idx = size -1;
        while(idx > 1 && _cmp(arr[idx], arr[idx/2])){
            _node tmp = arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = tmp;
            idx /= 2;
        }
    }
    _node pop(){
        _node ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if (j >= size){
                break;
            }
            if((j + 1) < size && _cmp(arr[j+1], arr[j])){
                j++;
            }
            if(_cmp(arr[j], arr[i])){
                _node t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else {
                break;
            }
        }

        return ret;

    }
    bool empty(){
        return size == 1;
    }
};
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};

class Solution {
public:
    _heap que;
    int minimumObstacles(vector>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int **visited = new int*[m];
        for(int i = 0 ; i < m; i++){
            visited[i] = new int[n];
            for(int j = 0 ; j < n ;j++){
                visited[i][j] = 1234567890;
            }
        }
        visited[0][0]= 0;
        que.push({0, 0, 0, 0});
        while(!que.empty()){
            _node nod = que.pop();
            if(nod.r == m - 1 && nod.c == n - 1){
                return nod.removeCnt;
            }
            for(int i = 0 ; i< 4; i++){
                int nr = nod.r + dy[i];
                int nc = nod.c + dx[i];
                if(nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc] <= nod.moveCnt+1){
                    continue;
                }
                visited[nr][nc] = nod.moveCnt+1;
                if(grid[nr][nc] == 0){
                    que.push({nr, nc, nod.moveCnt+1, nod.removeCnt});
                } else {
                    que.push({nr, nc, nod.moveCnt+1, nod.removeCnt + 1});
                }
            }
        }

        return -1;
    }
};

Leetcode Problem:

• Construct Binary Tree from Preorder and Postorder Traversal

Summary

• Given two integer arrays, preorder and postorder, where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

Approach

• The approach used is to use a recursive function traversal to construct the binary tree
• The function takes the current node, preorder array index, postorder array index, and the preorder and postorder arrays as parameters
• It creates a new node with the value at the current preorder index, and then recursively constructs the left and right subtrees using the postorder array indices.

Complexity

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

Explanation

• The solution uses a recursive function traversal to construct the binary tree
• The function takes the current node, preorder array index, postorder array index, and the preorder and postorder arrays as parameters
• It creates a new node with the value at the current preorder index, and then recursively constructs the left and right subtrees using the postorder array indices
• The base case for the recursion is when the preorder index is greater than or equal to the length of the preorder array, in which case the function returns null
• The function also checks if the current node value matches the current postorder index, and if so, increments the postorder index
• The function then recursively constructs the left and right subtrees, and finally returns the constructed node.

Solution Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    
public:
    
    TreeNode* traversal(TreeNode* root, vector& preorder, int& preIdx, vector& postorder, int& posIdx){
        if(preIdx >= preorder.size()) return nullptr;
        root = new TreeNode(preorder[preIdx]);

        if(root->val == postorder[posIdx]){
            posIdx++;
            return root;
        }

        ++preIdx;
        root->left = traversal(root->left, preorder, preIdx, postorder, posIdx);
        if(root->left == nullptr){
            preIdx--;
        }
        if(root->val == postorder[posIdx]){
            posIdx++;
            return root;
        }
        ++preIdx;
        root->right = traversal(root->right, preorder, preIdx, postorder, posIdx);
        if(root->left == nullptr){
            preIdx--;
        }
        if(root->val == postorder[posIdx]){
            posIdx++;
        }
        return root;
    }
    TreeNode* constructFromPrePost(vector& preorder, vector& postorder) {
        int preIdx = 0;
        int posIdx = 0;
        return traversal(nullptr, preorder, preIdx, postorder, posIdx);
    }
};

Leetcode Problem:

• Shortest Distance After Road Addition Queries I

Summary

• Given an integer n and a 2D integer array queries, find the length of the shortest path from city 0 to city n-1 after processing the first i+1 queries.

Approach

• Use a queue to perform BFS from city 0 to city n-1
• For each query, add the new road to the queue and update the distance of each visited city.

Complexity

• O(n*Q) where n is the number of cities and Q is the number of queries

Solution Code:

struct _node{
    int n;
    int cnt;
};
class Solution {
public:
    vector adj[500];
    

    vector shortestDistanceAfterQueries(int n, vector>& queries) {
        vector ans;
        for(int i = 0 ; i < n-1; i++){
            adj[i].push_back(i+1);
        }
        for(int i = 0 ; i < queries.size(); i++){
            queue<_node> que;
            bool visited[500] = {false};
            int a = queries[i][0];
            int b = queries[i][1];
            adj[a].push_back(b);
            
            visited[0] = true;
            for(int j = 0 ; j < adj[0].size(); j++){
                que.push({adj[0][j], 1});
                visited[adj[0][j]] = true;
            }

            while(!que.empty()){
                _node nod = que.front();
                que.pop();
                if(nod.n == n-1){
                    ans.push_back(nod.cnt);
                    break;
                }
                for(int j = 0 ; j < adj[nod.n].size(); j++){
                    int next = adj[nod.n][j];
                    if(visited[next]) continue;
                    visited[next] = true;
                    que.push({next, nod.cnt + 1});
                }
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Find Champion II

Summary

• Find the champion in a directed acyclic graph (DAG) tournament

Approach

• Use depth-first search (DFS) to traverse the graph and identify the champion team
• The champion team is the one that has no stronger team.

Complexity

• O(n + m) where n is the number of teams and m is the number of edges in the graph

Solution Code:

class Solution {
public:
    vector adj[101];
    set leaf;
    bool visited[101];
    set start;
    void dfs(int cur){
        if(visited[cur]) return;
        visited[cur] = true;
        if(adj[cur].size() == 0){
            leaf.insert(cur);
            return;
        }
        for(int i = 0 ; i < adj[cur].size(); i++){
            int next = adj[cur][i];
            dfs(next);
        }
    }
    int findChampion(int n, vector>& edges) {
        if (n == 1) return 0;
        for(int  i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            adj[b].push_back(a);
            start.insert(a);
            start.insert(b);
        }
        if(n != start.size()){
            return -1;
        }
        for(auto iter = start.begin(); iter != start.end(); iter++){
            dfs(*iter);
        }
        if(leaf.size() == 1) return *(leaf.begin());
        return -1;
    }
};