'2025/02/19'에 해당되는 글 7건

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