'릿코드'에 해당되는 글 281건

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;
    }
};

Leetcode Problem:

• Recover a Tree From Preorder Traversal

Summary

• Recover a binary tree from a preorder depth-first search traversal.

Approach

• The approach used in the solution is to recursively parse the traversal string and construct the binary tree
• At each node, the depth of the node is determined by the number of dashes before its value
• The solution uses a helper function `makeTree` to recursively construct the tree.

Complexity

• O(n), where n is the number of nodes in the tree, because each node is visited once during the traversal and once during the construction of the tree.

Explanation

• The `makeTree` function takes a pointer to the current node, the current depth, a reference to the traversal string, and a reference to the number of processed characters
• It first checks if all characters have been processed, and if not, it extracts the value of the current node by counting the number of dashes before the next character
• It then recursively constructs the left and right subtrees with the updated depth and processed index
• The `recoverFromPreorder` function initializes the tree construction by calling `makeTree` with the root node and the initial depth and processed index.

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* makeTree(TreeNode* root, int depth, string& traversal, int &processed){
        if(processed == traversal.size()){
            return nullptr;
        }
        
        int i = processed;
        int curDepth = 0;
        while(i < traversal.size() && traversal[i] == '-'){
            i++;
            curDepth++;
        }
        if(curDepth < depth){
            return nullptr;
        }
        int val = 0;
        while(i < traversal.size() && traversal[i] >= '0' && traversal[i] <= '9'){
            val *= 10;
            val += traversal[i] - '0';
            i++;
        }
        processed = i;
     
        root = new TreeNode();
        root->val = val;
        root->left = makeTree(root->left, depth+1, traversal, processed);
        root->right = makeTree(root->right, depth+1, traversal, processed);
        return root;
    }
    TreeNode* recoverFromPreorder(string traversal) {
        int processed = 0;
        TreeNode* root = makeTree(root, 0, traversal, processed);
        return root;
    }
};

Leetcode Problem:

• Sliding Puzzle

Summary

• Find the least number of moves to solve a sliding puzzle

Approach

• Breadth-First Search (BFS) algorithm is used to explore all possible states of the puzzle
• The algorithm starts with the initial state and generates all possible next states by swapping each empty tile with each adjacent tile
• The algorithm continues until it finds the target state or exhausts all possible states.

Complexity

• O(15*6^6) = O(2^8) due to the use of BFS and the size of the search space

Explanation

• The solution code defines a BFS algorithm to solve the sliding puzzle
• It starts with the initial state and generates all possible next states by swapping each empty tile with each adjacent tile
• The algorithm continues until it finds the target state or exhausts all possible states
• The time complexity of the algorithm is O(2^8) due to the use of BFS and the size of the search space.

Solution Code:

struct _node{
    char board[2][3];
    int cnt;
};
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
class Solution {
public:
    bool visited[6][6][6][6][6][6];
    queue<_node> que;
    int slidingPuzzle(vector>& board) {
        _node init;
        for(int i = 0 ; i < 2; i++){
            for(int j = 0; j < 3; j++){
                init.board[i][j] = board[i][j];
            }
        }
        init.cnt = 0;
        que.push(init);
        visited[board[0][0]][board[0][1]][board[0][2]][board[1][0]][board[1][1]][board[1][2]] = true;
        while(!que.empty()){
            _node nod = que.front();
            que.pop();
            if(nod.board[1][2] == 0 && nod.board[0][0] == 1 && 
            nod.board[0][1] == 2 && nod.board[0][2] == 3 &&
            nod.board[1][0] == 4 && nod.board[1][1] == 5){
                return nod.cnt;
            }
            int r=-1, c = -1;
            for(int i = 0; i < 2; i++){
                for(int j = 0; j < 3; j++){
                    if(nod.board[i][j] == 0){
                        r = i;
                        c = j;
                        break;
                    }
                }
                if(r != -1) break;
            }

            for(int i = 0 ; i < 4; i++){
                int nr = r + dy[i];
                int nc = c + dx[i];
                if(nr < 0 || nr >= 2 || nc < 0 || nc >= 3){
                    continue;
                }
                _node next = nod;
                next.cnt++;
                char t = next.board[nr][nc];
                next.board[nr][nc] = next.board[r][c];
                next.board[r][c] = t;
                if(visited[next.board[0][0]][next.board[0][1]][next.board[0][2]][next.board[1][0]][next.board[1][1]][next.board[1][2]] ){
                    continue;
                }

                visited[next.board[0][0]][next.board[0][1]][next.board[0][2]][next.board[1][0]][next.board[1][1]][next.board[1][2]] = true;
                que.push(next);
            }

        }
        return -1;
    }
};

Leetcode Problem:

• Maximum Matrix Sum

Summary

• Given an n x n matrix, find the maximum sum of its elements by multiplying adjacent elements by -1.

Approach

• The solution works by first calculating the sum of the absolute values of all elements in the matrix
• Then, it checks if there is an even number of negative elements
• If there is, it subtracts twice the minimum value from the sum
• This operation effectively flips the sign of the negative elements, which can increase the sum.

Complexity

• O(n^2) where n is the size of the matrix

Explanation

• The solution iterates over each element in the matrix once to calculate the sum and count the number of negative elements
• Then, it checks if there is an odd number of negative elements and subtracts twice the minimum value from the sum if necessary
• This approach ensures that the maximum sum is achieved by flipping the sign of the negative elements.

Solution Code:

class Solution {
public:
    long long maxMatrixSum(vector>& matrix) {
        int cnt = 0;
        int minValue = 100001;
        long long sum = 0;
        bool isZero = false;
        for(int i = 0 ; i < matrix.size(); i++){
            for(int j = 0 ; j < matrix[0].size(); j++){
                sum += abs(matrix[i][j]);
                if(matrix[i][j] < 0){
                    cnt++;
                }
                minValue = min(minValue, abs(matrix[i][j]));
                if(matrix[i][j] == 0){
                    isZero = true;
                }
            }
        }
        if(!isZero && (cnt &1)){
            sum -= minValue*2;
        }
        return sum;
    }
};

Leetcode Problem:

• Rotating the Box

Summary

• Given an m x n matrix of characters boxGrid representing a side-view of a box, rotate the box 90 degrees clockwise and return the resulting matrix.

Approach

• The approach used is to first transpose the boxGrid and then reverse each row of the transposed matrix
• This is because the problem requires us to rotate the box 90 degrees clockwise, which can be achieved by first flipping the box horizontally and then flipping it vertically.

Complexity

• O(m*n) where m is the number of rows and n is the number of columns in the boxGrid.

Explanation

• The solution code first creates a new 2D vector rotateBox to store the resulting matrix
• It then iterates over each row in the boxGrid and performs the following operations: 1
• It starts from the rightmost column and moves towards the left
• If the current cell is a stone (#), it moves the stone to the bottom right corner of the row and marks the stone as empty (.) if it's not the last stone in the row
• 2
• If the current cell is an obstacle (*), it moves the obstacle to the left of the stone
• 3
• If the current cell is empty (.), it simply moves to the next cell
• After processing each row, the code transposes the boxGrid and reverses each row to achieve the rotation
• Finally, it returns the resulting matrix.

Solution Code:

class Solution {
public:
    vector> rotateTheBox(vector>& box) {
        vector> rotateBox;
        for(int i = 0 ; i< box.size(); i++){
            int r = box[0].size() - 1;
            int l = r;
            while(l >= 0){
                if(box[i][l] == '#'){
                    box[i][r] = box[i][l];
                    if(l != r){
                        box[i][l] = '.';
                    }
                    r--;
                } else if(box[i][l] == '*'){
                    r = l - 1;
                }
                l--;
            }

        }
        int R = box.size();
        int C = box[0].size();
        for(int j=0; j < C; j++){
            rotateBox.push_back(vector());
            for(int i = 0; i < R; i++){
                rotateBox[j].push_back(box[R-i-1][j]);
            }
        }
        
        


        return rotateBox;
    }
};

Leetcode Problem:

• Flip Columns For Maximum Number of Equal Rows

Summary

• Find the maximum number of rows that have all values equal after some number of flips in a binary matrix.

Approach

• Use a hash map to store the frequency of each string representation of the columns
• Then, for each string, calculate the maximum number of rows that can be made equal by flipping the bits in the column
• The maximum number of rows that can be made equal across all strings is the maximum of these values.

Complexity

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

Explanation

• The solution works by first creating a hash map where each key is a string representation of a column and the value is the frequency of that column
• Then, for each string, it calculates the maximum number of rows that can be made equal by flipping the bits in the column
• This is done by counting the number of bits that are different between the string and the column
• The maximum number of rows that can be made equal across all strings is the maximum of these values.

Solution Code:

template 
struct _vector{
    T* arr;
    int size;
    int capacity;
    _vector(){
        size = 0;
        capacity = 2;
        arr = new T[capacity];
    }
    void push(T a){
        if(size == capacity){
            capacity *= 2;
            T* tmp = new T[capacity];
            for(int i = 0 ; i < size ; i++){
                tmp[i] = arr[i];
            }
            delete[] arr;
            arr = tmp;
        }
        arr[size++] = a;
    }
    T operator[](int idx){
        return arr[idx];
    }
};

struct _node{
    string s;
    int cnt;
};

struct _node2{
    unsigned int key;
    int idx;
};

#define MAP_SIZE 300
struct _map{
    _vector<_node> arr[MAP_SIZE];
    _vector<_node2> nodeList;
    _map(){
        for(int i = 0 ; i < MAP_SIZE; i++){
            arr[i].size = 0;
        }
        nodeList.size = 0;
    }
    void push(string s){
        unsigned int key = 1;
        for(int i = 0 ; i < s.size(); i++){
            key *= s[i] - 'a';
            key *= 26;
            key %= MAP_SIZE;
        }
        for(int i = 0; i < arr[key].size; i++){
            if(arr[key][i].s.compare(s) == 0){
                arr[key].arr[i].cnt++;
                return;
            }
        }
        arr[key].push({s, 1});
        nodeList.push({key, arr[key].size - 1});
    }
    int size(){
        return nodeList.size;
    }
    _node getItem(_node2 nod){
        return arr[nod.key][nod.idx];
    }
};

class Solution {
public:
    int maxEqualRowsAfterFlips(vector>& matrix) {
        _map hmap;
        for(int i = 0 ; i < matrix.size(); i++){
            string s = "";
            int first = matrix[i][0];
            for(int j = 0 ; j < matrix[i].size(); j++){
                if(first == matrix[i][j]){
                    s += "1";
                } else {
                    s += "0";
                }
            }
            hmap.push(s);
        }
        int ans = 0;
        for(int i = 0; i < hmap.size(); i++){
            ans = max(ans, hmap.getItem(hmap.nodeList[i]).cnt);
        }
        return ans;
    }
};

Leetcode Problem:

• Count Unguarded Cells in the Grid

Summary

• This solution calculates the number of unguarded cells in a grid given the positions of guards and walls.

Approach

• The approach used is to first create a map of the grid where each cell is initially unguarded (0)
• Then, we mark the positions of the walls and guards on the map
• After that, we perform a depth-first search (DFS) from each guard position to mark the cells that can be seen by the guard
• Finally, we count the number of unguarded cells by iterating over the map.

Complexity

• O(m*n + m*n*4) = O(m*n) because the DFS operations are bounded by the number of cells in the grid.

Explanation

• The provided C++ code initializes a 2D map of size m x n with all cells unguarded
• It then marks the positions of the walls and guards on the map
• After that, it performs a depth-first search (DFS) from each guard position to mark the cells that can be seen by the guard
• The DFS function recursively explores the neighboring cells in four directions (north, east, south, and west) and marks them as guarded if they are not already marked as walls or other guards
• Finally, it counts the number of unguarded cells by iterating over the map and returns the result.

Solution Code:

int dy[] = {1, -1, 0, 0};
int dx[] = {0, 0, 1, -1};
class Solution {
public:
    vector< vector> map;
    void fill(int m, int n, int r, int c, int dir, int v){
        if(r < 0 || r >= m || c < 0 || c >= n || map[r][c] == 2 || map[r][c] == v){
            return;
        }
        map[r][c] = v; 
        fill(m, n, r + dy[dir], c + dx[dir], dir, v);
    }
    int countUnguarded(int m, int n, vector>& guards, vector>& walls) {
        for(int i = 0 ; i < m; i++){
            map.push_back(vector());
            for(int j = 0; j < n; j++){
                map[i].push_back(0);
            }
        }
        for(int i = 0; i < walls.size(); i++){
            int r = walls[i][0];
            int c = walls[i][1];
            map[r][c] = 2;
        }
        for(int i = 0 ; i < guards.size(); i++){
            int r = guards[i][0];
            int c = guards[i][1];
            for(int j = 0 ; j < 4; j++){
                fill(m, n, r + dy[j], c + dx[j], j, j < 2 ? 4 : 5);
            }
            map[r][c] = 1;
        }
        int ans = 0;
        for(int i = 0 ; i < m; i++){
            for(int j = 0 ; j < n; j++){
                if(map[i][j] == 0){
                    ans++;
                }
            }
        }
        return ans;
    }
};