'2025/03/06'에 해당되는 글 3건

Leetcode Problem:

• Count Total Number of Colored Cells

Summary

• Calculating the number of colored cells in a grid after n minutes

Approach

• The approach used is to calculate the number of colored cells in each minute and sum them up
• The number of colored cells in each minute is calculated as 2 times the number of odd-numbered cells that have not been colored yet
• The odd-numbered cells are calculated using the formula i * 2 + 1, where i is the current minute
• The initial number of odd-numbered cells is (i - 1) * 2 + 1, where i is 1
• The sum of colored cells in each minute is added to the total sum.

Complexity

• O(n)

Explanation

• The time complexity of the solution is O(n) because the solution iterates over each minute from 1 to n
• The space complexity is O(1) because the solution only uses a constant amount of space to store the variables i, odd, and sum.

Solution Code:

class Solution {
public:
    long long coloredCells(int n) {
        int i = 1;
        int odd = (i - 1) * 2 + 1;
        long long sum = 0;
        for( ; i < n; i++){
            sum += odd*2;
            odd = i * 2 + 1;
        }
        return sum + odd;
    }
};

Leetcode Problem:

• Shortest Common Supersequence

Summary

• Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences.

Approach

• The approach used is dynamic programming
• We first create a 2D array dp where dp[i][j] represents the length of the shortest common supersequence of the first i characters of str1 and the first j characters of str2
• Then we construct the shortest common supersequence by tracing back the dp array.

Complexity

• O(n*m) where n and m are the lengths of str1 and str2 respectively.

Explanation

• The solution first initializes a 2D array dp of size (n+1) x (m+1) where n and m are the lengths of str1 and str2 respectively
• It then fills up the dp array using dynamic programming
• For each cell dp[i][j], if the current characters in str1 and str2 are the same, it increments the value by 1
• Otherwise, it takes the maximum value from the top and left cells
• After filling up the dp array, it constructs the shortest common supersequence by tracing back the dp array
• Finally, it appends any remaining characters from str1 and str2 to the supersequence.

Solution Code:

class Solution {
public:
    int dp[1001][1001];
    string shortestCommonSupersequence(string str1, string str2) {
        int cnt1 = 0;
        for(int i = 0 ; i < str1.size(); i++){
            for(int j = 0 ; j < str2.size(); j++){
                if(str1[i] == str2[j]){
                    dp[i+1][j+1] = dp[i][j] + 1;
                } else{
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }
        string s = "";
        int i = str1.size();
        int j = str2.size();
        while(i > 0 && j > 0){
            if(dp[i][j] == dp[i][j-1]){
                j--;
            } else if(dp[i][j] == dp[i-1][j]){
                i--;
            } else{
                s += str1[i-1];
                i--;
                j--;
            }
        }
        reverse(s.begin(), s.end());
        string res = "";
        int idx1 = 0;
        int idx2 = 0;
        for(int i = 0; i < s.size(); i++){
            while(str1[idx1] != s[i]){
                res += str1[idx1];
                idx1++;
            }
            while(str2[idx2] != s[i]){
                res += str2[idx2];
                idx2++;
            }
            res += s[i];
            idx1++;
            idx2++;
        }
        while(idx1 < str1.size()){
            res += str1[idx1++];
        }
        while(idx2 < str2.size()){
            res += str2[idx2++];
        }

        return res;
    }
};

Leetcode Problem:

• Make Lexicographically Smallest Array by Swapping Elements

Summary

• Given a 0-indexed array of positive integers and a positive integer limit, return the lexicographically smallest array that can be obtained by swapping any two indices if the absolute difference between the two elements is less than or equal to the limit.

Approach

• The solution uses a greedy approach to group the elements into subarrays based on their values
• It first sorts the array and then iterates through the sorted array to create subarrays
• Each subarray contains elements that are within the limit of each other
• Finally, it replaces each element in the original array with the smallest element in its corresponding subarray.

Complexity

• O(n log n) due to the sorting operation, where n is the number of elements in the array.

Solution Code:

class Solution {
public:
    vector lexicographicallySmallestArray(vector& nums, int limit) {
        vector> groups;
        unordered_map valToGrp;
        int numIdx = 0;
        vector nums2;
        for(int i = 0 ; i < nums.size(); i++){
            nums2.push_back(nums[i]);
        }
        sort(nums2.begin(), nums2.end());
        while(numIdx < nums2.size()){
            groups.push_back(vector ());
            long long minv = nums2[numIdx];
            long long maxv = nums2[numIdx];
            while(minv - limit <= nums2[numIdx] && nums2[numIdx] <= maxv + limit){
                groups.back().push_back(nums2[numIdx]);
                valToGrp[nums2[numIdx]] = groups.size() - 1;
                numIdx++;
                if(numIdx >= nums2.size()) break;
                if(minv > nums2[numIdx] && nums2[numIdx] >= minv - limit){
                    minv = nums2[numIdx];
                }
                if(maxv < nums2[numIdx] && nums2[numIdx] <= maxv + limit){
                    maxv = nums2[numIdx];
                }
            }
        }
        unordered_map groupIdx;
        for(int i = 0 ; i < nums.size(); i++){
            int idx = valToGrp[nums[i]];
            nums[i] = groups[idx][groupIdx[idx]];
            groupIdx[idx]++;
        }
        return nums;
    }
};