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

Leetcode Problem:

• Delete Characters to Make Fancy String

Summary

• The problem is to delete the minimum possible number of characters from a string to make it a fancy string, where no three consecutive characters are equal.

Approach

• The approach used is to iterate through the string and check for consecutive characters
• If three consecutive characters are equal, they are skipped
• Otherwise, they are added to the result string.

Complexity

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

Explanation

• The solution code initializes a string `ss` with the first character of the input string
• It then iterates through the rest of the string, checking for consecutive characters
• If three consecutive characters are equal, they are skipped
• Otherwise, they are added to the result string
• The code also keeps track of the count of consecutive characters and resets it when a different character is encountered.

Solution Code:

class Solution {
public:
    string makeFancyString(string s) {
        string ss = string(1,s[0]);
        int repeat_cnt = 1;
        char before_char = s[0];
        for(int i = 1 ;  i < s.size(); i++){
            if (before_char == s[i]){
                repeat_cnt++;
                if(repeat_cnt >= 3) continue;
            } else {
                repeat_cnt = 1;
            }
            ss += s[i];
            before_char = s[i];
        }
        return ss;
    }
};

Leetcode Problem:

• Minimum Total Distance Traveled

Summary

• Minimum Total Distance for Robots to Reach Factories

Approach

• Dynamic Programming with Memoization

Complexity

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

Explanation

• This solution sorts the robots and factories by position, then uses dynamic programming with memoization to calculate the minimum total distance
• The `calculateMinDistance` function recursively tries two options: assigning the current robot to the current factory and skipping the current factory for the current robot
• The minimum of these two options is stored in the memo table to avoid repeated calculations.

Solution Code:

class Solution {
public:
    long long minimumTotalDistance(vector& robot,
                                   vector>& factory) {
        // Sort robots and factories by position
        sort(robot.begin(), robot.end());
        sort(factory.begin(), factory.end());

        // Flatten factory positions according to their capacities
        vector factoryPositions;
        for (auto& f : factory)
            for (int i = 0; i < f[1]; i++) factoryPositions.push_back(f[0]);

        int robotCount = robot.size(), factoryCount = factoryPositions.size();
        vector> memo(robotCount,
                                       vector(factoryCount, -1));

        // Recursively calculate minimum total distance with memoization
        return calculateMinDistance(0, 0, robot, factoryPositions, memo);
    }

    long long calculateMinDistance(int robotIdx, int factoryIdx,
                                   vector& robot,
                                   vector& factoryPositions,
                                   vector>& memo) {
        // All robots assigned
        if (robotIdx == robot.size()) return 0;
        // No factories left to assign
        if (factoryIdx == factoryPositions.size()) return 1e12;
        // Check memo
        if (memo[robotIdx][factoryIdx] != -1) return memo[robotIdx][factoryIdx];

        // Option 1: Assign current robot to current factory
        long long assign = abs(robot[robotIdx] - factoryPositions[factoryIdx]) +
                           calculateMinDistance(robotIdx + 1, factoryIdx + 1,
                                                robot, factoryPositions, memo);

        // Option 2: Skip current factory for the current robot
        long long skip = calculateMinDistance(robotIdx, factoryIdx + 1, robot,
                                              factoryPositions, memo);

        return memo[robotIdx][factoryIdx] =
                   min(assign, skip);  // Take the minimum and store in memo
    }
};

Leetcode Problem:

• The k-th Lexicographical String of All Happy Strings of Length n

Summary

• This problem is to find the kth happy string of a given length n, where happy string is a string that consists only of letters a, b, c and s[i]!= s[i + 1] for all values of i from 1 to n - 1.

Approach

• The approach used in this solution is a recursive function that generates all happy strings of a given length n
• The function uses a dynamic programming approach to keep track of the number of happy strings generated so far and returns the kth string when k is reached.

Complexity

• O(3^n) because in the worst case, for each position in the string, there are 3 possible choices for the character, and this choice is made n times.

Explanation

• The solution uses a recursive function getHappyString that takes four parameters: n (the length of the string), k (the position of the string we want to find), depth (the current position in the string), and res (the string generated so far)
• The function first checks if the length of the string is equal to the depth
• If it is, it increments the count of happy strings and checks if the count is equal to k
• If it is, it returns the string
• If not, it returns an empty string
• If the length of the string is not equal to the depth, the function loops through each character in the set {a, b, c} and recursively calls itself with the next depth and the current character appended to the result string
• If the recursive call returns a non-empty string, it returns that string
• Otherwise, it returns an empty string.

Solution Code:

class Solution {
public:
    char c[3] = {'a', 'b', 'c'};
    int cnt;
    string getHappyString(int n, int k, int depth = 0, string res = "") {
        if(n == depth){
            cnt++;
            if(cnt == k){
                return res;
            }
            return "";
        }
        for(int i = 0 ; i < 3; i++){
            if(depth != 0 && res[depth-1] == c[i]){
                continue;
            }
            string ans = getHappyString(n, k, depth + 1, res + c[i]);
            if(ans.size() != 0){
                return ans;
            }
        }
        return "";
    }
};

Leetcode Problem:

• Minimum Number of Removals to Make Mountain Array

Summary

• Given an integer array nums, return the minimum number of elements to remove to make nums a mountain array.

Approach

• Dynamic programming approach to solve the problem
• Two arrays dp1 and dp2 are used to store the maximum number of elements that can be removed to make the left and right parts of the array a mountain array respectively.

Complexity

• O(n^2) where n is the size of the input array nums

Explanation

• The dp1 array is used to store the maximum number of elements that can be removed to make the left part of the array a mountain array
• The dp1 array is filled in a bottom-up manner
• For each element in the array, the maximum number of elements that can be removed to make the left part of the array a mountain array is updated
• The dp2 array is used to store the maximum number of elements that can be removed to make the right part of the array a mountain array
• The dp2 array is also filled in a bottom-up manner
• For each element in the array, the maximum number of elements that can be removed to make the right part of the array a mountain array is updated
• Finally, the minimum number of elements that need to be removed to make the entire array a mountain array is calculated by iterating over the array and checking if the current element is greater than or equal to the previous element
• If it is, then the minimum number of elements that need to be removed is updated.

Solution Code:

class Solution {
public:
    int dp1[1001];
    int dp2[1001];
    int minimumMountainRemovals(vector& nums) {
        int N = nums.size();
        dp1[N - 1] = 1;
        for(int i = N-2; i>= 0; i--){
            dp1[i] = 1;
            for(int j = i + 1; j < N; j++){
                if(nums[j]< nums[i]){
                    dp1[i] = max(dp1[i], dp1[j] + 1);
                }
            }
        }

        dp2[0] = 1;
        for(int i = 1 ; i < nums.size(); i++){
            dp2[i] = 1;
            for(int j = i -1; j >= 0; j--){
                if(nums[j]< nums[i]){
                    dp2[i] = max(dp2[i], dp2[j] + 1);
                }
            }
        }
        int res = 0;
        for(int i = 1 ; i< N-1; i++){
            if(nums[i-1] >= nums[i]) continue;
            int j_max = 0;
            bool success = false;
            for(int j = i + 1; j < N; j++){
                if(nums[i] <= nums[j]){
                    continue;
                }
                success = true;
                j_max = max(j_max, dp1[j]);
            }
            if (success)
                res = max(res, j_max + dp2[i]);
        }
        return N -res;
    }
};

Leetcode Problem:

• Maximum Number of Moves in a Grid

Summary

• This problem requires finding the maximum number of moves that can be performed in a grid while following certain rules.

Approach

• The approach used is a breadth-first search (BFS) algorithm
• It starts from the first column of the grid and explores all possible cells that can be reached from each cell
• The algorithm keeps track of the number of moves made and updates the maximum number of moves found so far.

Complexity

• O(R*C) where R is the number of rows and C is the number of columns in the grid.

Solution Code:

struct _pair{
    int r;
    int c;
};
struct _queue{
    _pair arr[1000001];
    int front = 0;
    int rear = 0;
    void pop(){
        front++;
    }
    void push(_pair a){
        arr[rear++] = a;
    }
    _pair peek(){
        return arr[front];
    }
    bool empty(){
        return front == rear;
    }
    
};
class Solution {
public:
    int visited[1000][1000];
    _queue que;
    
    int maxMoves(vector>& grid) {
        int dy[] = {1, -1, 0};
        int dx[] = {1, 1, 1};
        int R = grid.size();
        int C = grid[0].size();
        int ans = 0;
        for(int i = 0 ; i < grid.size(); i++){
            que.push({i, 0});
            visited[i][0] = 0;
        }
        while(!que.empty()){
            _pair num = que.peek();
            que.pop();
            ans = max(ans, visited[num.r][num.c]);
            for(int i = 0 ; i < 3; i++){
                int ny = num.r + dy[i];
                int nx = num.c + dx[i];
                if(ny < 0 || ny >= R || nx < 0 || nx >= C || 
                    visited[num.r][num.c] + 1 <= visited[ny][nx] ||
                    grid[num.r][num.c] >= grid[ny][nx]){
                    continue;
                }
                visited[ny][nx] = visited[num.r][num.c] + 1;
                que.push({ny, nx});
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Longest Square Streak in an Array

Summary

• The problem is to find the length of the longest square streak in a given integer array
• A square streak is a subsequence where each element (except the first) is the square of the previous number
• The solution should return the length of the longest square streak or -1 if no square streak exists.

Approach

• The approach used in the solution is to first mark all numbers in the array as visited
• Then, for each number in the array, it checks if it is the square of any other number
• If it is, it counts the number of consecutive squares starting from that number
• The maximum count is updated if a longer square streak is found.

Complexity

• O(n * sqrt(m)) where n is the size of the array and m is the maximum number in the array

Explanation

• The solution uses a boolean array isNum to keep track of visited numbers
• It iterates over each number in the array and checks if it is the square of any other number
• If it is, it counts the number of consecutive squares starting from that number
• The maximum count is updated if a longer square streak is found
• The time complexity is O(n * sqrt(m)) because in the worst case, for each number in the array, it checks all numbers up to sqrt(m).

Solution Code:

class Solution {
public:
    bool isNum[100001] = {false};
    int longestSquareStreak(vector& nums) {
        for(int i = 0 ; i < nums.size(); i++){
            isNum[nums[i]] = true;
        }
        
        int ans = -1;
        for(int i = 0 ; i < 100001; i++){
            if (!isNum[i]) continue;
            long long j = i;
            int cnt = 0;
            while(j <= 100000 && isNum[j]){
                cnt++;
                j = j*j;
            }
            if(cnt >= 2)
                ans = max(ans, cnt);
        }
        return ans;
    }
};

Leetcode Problem:

• Count Square Submatrices with All Ones

Summary

• Given a matrix of ones and zeros, return how many square submatrices have all ones.

Approach

• Dynamic programming is used to solve this problem
• A 2D array dp is created to store the size of the largest square submatrix ending at each cell
• The solution is calculated by iterating through the matrix and updating the dp array
• The size of the largest square submatrix ending at each cell is calculated by taking the minimum of the sizes of the largest square submatrices ending at the cell above, the cell to the left, and the cell to the top-left, and adding 1 to it.

Complexity

• O(m*n) where m and n are the number of rows and columns in the matrix respectively.

Explanation

• The solution starts by initializing a 2D array dp of size 301x301 with all elements set to 0
• Then it iterates through the matrix
• If the current cell is 0, it skips it
• If the current cell is 1, it calculates the size of the largest square submatrix ending at the current cell by taking the minimum of the sizes of the largest square submatrices ending at the cell above, the cell to the left, and the cell to the top-left, and adds 1 to it
• The size of the largest square submatrix ending at the current cell is then stored in the dp array
• Finally, the solution is calculated by summing up the values in the dp array.

Solution Code:

class Solution {
public:
    int countSquares(vector>& matrix) {
        int dp[301][301] = {0};
        int res = 0;
        for(int i = 0 ; i < matrix.size(); i++){
            for(int j = 0 ; j < matrix[i].size();j++){
                if(matrix[i][j] == 0){
                    continue;
                }
                if(i-1 < 0 || j-1 < 0){
                    dp[i][j] = matrix[i][j];
                    res += dp[i][j];
                    continue;
                }
                dp[i][j] = min(dp[i-1][j],min(dp[i-1][j-1], dp[i][j-1])) + 1;
                res += dp[i][j];
            }
        }
        
        return res;
    }
};

Leetcode Problem:

• Remove Sub-Folders from the Filesystem

Summary

• Given a list of folders, return the folders after removing all sub-folders in those folders.

Approach

• The approach used is to create a Trie data structure to store the folders
• Each folder is inserted into the Trie by traversing the nodes based on the characters in the folder path
• Then, a traversal is performed on the Trie to find all the top-level folders (i.e., the ones that do not have any sub-folders).

Complexity

• O(N), where N is the total number of characters in all the folder paths.

Explanation

• The solution first inserts all the folder paths into the Trie
• Then, it performs a traversal on the Trie to find all the top-level folders
• The traversal is done recursively, and it checks each node in the Trie to see if it has any sub-folders
• If a node has no sub-folders, it is added to the result vector
• The time complexity of this solution is O(N), where N is the total number of characters in all the folder paths
• This is because each character in the folder paths is visited once during the insertion and traversal operations.

Solution Code:

struct _node{
    bool tail;
    _node* next[27];
    _node(){
        tail = false;
        for(int i = 0 ; i< 27;i++){
            next[i] = nullptr;
        }
    }
};




class Solution {
public:
    _node trie;
    void insert(string s){
        _node* ptr = ≜
        for (char c : s){

            int idx = c == '/' ? 26 : c - 'a';
            if(ptr->next[idx] == nullptr){
                ptr->next[idx] = new _node();
            }
            ptr = ptr->next[idx];
        }
        ptr->tail = true;
    }
    void traversal(_node* root, string s, vector& ans){
        if (root == nullptr) return;
        for(int i = 0; i < 26; i++){
            traversal(root->next[i],s + ""+(char)('a'+i), ans);
        }
        if (root->tail){
            ans.push_back(s);
            return;
        }
        traversal(root->next[26],s + "/", ans);
    }
    vector removeSubfolders(vector& folder) {
        for(string s : folder){
            insert(s);
        }
        vector ans;
        traversal(&trie, "", ans);
        return ans;
    }
};

Leetcode Problem:

• Flip Equivalent Binary Trees

Summary

• The problem is to determine if two binary trees are flip equivalent, which means that we can make one tree equal to the other by swapping the left and right child subtrees of some nodes.

Approach

• The solution uses a custom dynamic array class to store the traversal of each node in the binary tree
• It then uses a depth-first search approach to delete the nodes in the second tree, simulating the flip operation
• If the two trees are flip equivalent, the second tree should be empty after the deletion process.

Complexity

• O(n log n) due to the dynamic array resizing and deletion operations, where n is the number of nodes in the binary tree.

Solution Code:

struct _vector{
    int size;
    int capacity;
    int* arr;
    _vector(){
        size = 0;
        capacity = 2;
        arr = new int[capacity];
    }
    void push(int a){
        if (size == capacity){
            capacity *= 2;
            int* tmp = new int[capacity];
            for(int i = 0 ; i < size;  i++){
                tmp[i] = arr[i];
            }
            delete[] arr;
            arr = tmp;
        }
        arr[size++] = a;
    }
    bool del(int v){
        for(int i = 0 ; i < size; i++){
            if(arr[i] == v){
                arr[i] = arr[--size];
                return true;
            }
        }
        return false;
    }
    int operator[](int idx){
        return arr[idx];
    }
};


/**
 * 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 {
    _vector v[101];
public:
    void addTraversal(TreeNode* root){
        if (root == nullptr) return;
        v[root->val].push(root->left == nullptr ? -1:root->left->val );
        v[root->val].push(root->right == nullptr ? -1 : root->right->val);
        addTraversal(root->left);
        addTraversal(root->right);
    }
    bool delTraversal(TreeNode* root){
        if(root == nullptr) return true;
        if (!v[root->val].del(root->left == nullptr ? -1 : root->left->val)){
            return false;
        }
        if (!v[root->val].del(root->right == nullptr ? -1 : root->right->val)){
            return false;
        }
        if(!delTraversal(root->left)){
            return false;
        }
        if(!delTraversal(root->right)){
            return false;
        }
        return true;
    }
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        addTraversal(root1);
        if(!delTraversal(root2)){
            return false;
        }
        for(int i = 0 ; i < 101; i++){
            if(v[i].size > 0) return false;
        }
        return true;
    }
};

Leetcode Problem:

• Construct Smallest Number From DI String

Summary

• Find the lexicographically smallest possible string num that meets the conditions given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing.

Approach

• The approach used is to first initialize a character array num with the digits from 1 to 9
• Then, for each character in the pattern, if the character is 'I', we shift all the digits to the right to maintain the increasing order
• If the character is 'D', we shift all the digits to the left to maintain the decreasing order
• Finally, we construct the string num by concatenating the digits in the array.

Complexity

• O(n), where n is the length of the pattern string.

Explanation

• The provided solution code uses a character array num to store the digits from 1 to 9
• It then iterates over the pattern string, shifting the digits in the array as needed to maintain the increasing or decreasing order
• Finally, it constructs the string num by concatenating the digits in the array
• The time complexity is O(n) because it needs to iterate over the pattern string once
• The space complexity is also O(n) because it needs to store the digits in the array.

Solution Code:

class Solution {
public:
    string smallestNumber(string pattern) {
        char num[10] = {0};
        num[0] = '1';
        for(int i = 1; i <= pattern.size(); i++ ){
            num[i] = '1'+i;
            int j = i;
            while(j > 0 && pattern[j-1] == 'D'){
                char t = num[j];
                num[j] = num[j-1];
                num[j-1] = t;
                j--;
            }
        }
        string ans = "";
        ans += num[0];
        for(int i = 1; i <= pattern.size(); i++){
            ans += num[i];
        }
        return ans;
    }
};