'LeetCode'에 해당되는 글 281건

Leetcode Problem:

• House Robber IV

Summary

• The problem is to find the minimum capability of a robber to steal money from houses along a street, given the amount of money in each house and the minimum number of houses the robber will steal from.

Approach

• Binary Search Approach: The solution uses a binary search approach to find the minimum capability of the robber
• It initializes two pointers, `l` and `r`, to represent the minimum and maximum possible capability
• It then iterates through the range of possible capabilities, checking if the number of houses that can be robbed is greater than or equal to `k`
• If it is, it updates the maximum capability to the current value and moves the right pointer to the left
• Otherwise, it moves the left pointer to the right.

Complexity

• O(n log m) where n is the number of houses and m is the maximum possible capability

Explanation

• The solution starts by initializing two pointers, `l` and `r`, to represent the minimum and maximum possible capability
• It then iterates through the range of possible capabilities using a binary search approach
• For each capability `mid`, it counts the number of houses that can be robbed and checks if it is greater than or equal to `k`
• If it is, it updates the maximum capability to the current value and moves the right pointer to the left
• Otherwise, it moves the left pointer to the right
• The solution continues until `l` is greater than `r`, at which point it returns the maximum capability as the minimum capability of the robber.

Solution Code:

class Solution {
public:
    int minCapability(vector& nums, int k) {
        int l = 1;
        int r = 1000000000;
        int ans = 0;
        while(l <= r){
            // int mid = l + ((r - l) >> 1);
            int mid = (l + r)/2;
            int cnt = 0;
            for(int i = 0 ; i < nums.size(); i++){
                if(nums[i] <= mid){
                    cnt++;
                    i++;
                }
            }
            if(cnt >= k){
                r = mid - 1;
                ans = mid;
            } else{
                l = mid + 1;

            }
        }
        return ans;
    }
};

Leetcode Problem:

• Zero Array Transformation II

Summary

• Given an integer array and a 2D array of queries, find the minimum possible non-negative value of k such that after processing the first k queries in sequence, the array becomes a Zero Array.

Approach

• This problem can be solved by using binary search to find the minimum possible value of k
• We start by initializing two pointers, l and r, to the start and end of the queries array respectively
• We then calculate the sum of the values to be decremented for each query and update the offset array accordingly
• If the array becomes a Zero Array after processing the current query, we update the answer and move the right pointer to the left
• If not, we move the left pointer to the right
• We repeat this process until we find the minimum possible value of k or until l is greater than r.

Complexity

• O(n log q) where n is the size of the nums array and q is the size of the queries array

Explanation

• The time complexity of this solution is O(n log q) because we are using binary search to find the minimum possible value of k
• In the worst case, we need to process each query in the queries array, which takes O(n) time
• We repeat this process log q times, where log q is the number of iterations of the binary search
• The space complexity is O(n) because we need to store the offset array, which has n elements.

Solution Code:

class Solution {
public:
    int offset[100002];
    int minZeroArray(vector& nums, vector>& queries) {
        int l = 0;
        int r = queries.size();
        int ans = 100001;
        while(l <= r){
            int mid = (l + r) / 2;
            for(int i = 0 ; i < nums.size(); i++){
                offset[i] = 0;
            }
            for(int i = 0; i < mid; i++){
                offset[queries[i][0]] += queries[i][2];
                offset[queries[i][1] + 1] -= queries[i][2];
            }
            for(int i = 1; i < nums.size(); i++){
                offset[i] += offset[i-1];
            }
            bool success = true;
            for(int i = 0 ; i < nums.size() ;i++){
                if((nums[i] - offset[i]) > 0){
                    success = false;
                    break;
                }
            }
            if(success){
                ans = mid;
                r = mid - 1;
            } else{
                l = mid + 1;
            }
        }
        if( ans == 100001) return -1;
        return ans;
    }
};

Leetcode Problem:

• Maximum Count of Positive Integer and Negative Integer

Summary

• Given a sorted array of integers, return the maximum between the number of positive integers and the number of negative integers.

Approach

• The approach used is to simply iterate through the array and count the number of positive and negative integers
• Then, return the maximum of the two counts.

Complexity

• O(n) where n is the number of elements in the array

Explanation

• The solution iterates through the array once, using a single loop to count the number of positive and negative integers
• The time complexity is linear because it only needs to examine each element once
• The space complexity is O(1) because it only uses a constant amount of space to store the counts.

Solution Code:

class Solution {
public:
    int maximumCount(vector& nums) {
        int minus = 0;
        int plus = 0;
        for(int i = 0 ; i < nums.size(); i++){
            if(nums[i] < 0){
                minus++;
            }else if (nums[i] > 0){
                plus++;
            }
        }
        return max(minus, plus);
    }
};

Leetcode Problem:

• Number of Substrings Containing All Three Characters

Summary

• The problem is to find the number of substrings in a given string that contain all three characters 'a', 'b', and 'c' at least once.

Approach

• The solution uses a sliding window approach with two pointers, 'l' and 'r', to track the current substring
• It iterates over the string with 'r' and expands the window to the right
• When all three characters are found in the window, it shrinks the window from the left until all characters are found again.

Complexity

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

Explanation

• The solution uses a 1D array 'cnt' to count the occurrences of each character
• The 'all_include' function checks if all three characters are present in the 'cnt' array
• The 'numberOfSubstrings' function iterates over the string with 'r' and expands the window to the right
• When all three characters are found in the window, it adds the number of substrings that can be formed with the current window to the 'ans' variable
• The window is then shrunk from the left until all characters are found again.

Solution Code:

class Solution {
    int cnt[256] = {0};
public:
    bool all_include(){
        return cnt['a'] > 0 && cnt['b'] > 0 && cnt['c'] > 0;
    }
    int numberOfSubstrings(string s) {
        int l = 0;
        int r = 0;
        int ans = 0;
        while(r < s.size()){
            cnt[s[r]]++;

            while(all_include() && l < r){
                ans += s.size() - r;
                cnt[s[l]]--;
                l++;
            }

            r++;

        }
        return ans;
    }
};

Leetcode Problem:

• Count of Substrings Containing Every Vowel and K Consonants II

Summary

• Count the number of substrings in a given word that contain every vowel at least once and exactly k consonants.

Approach

• Sliding Window Technique with Hash Map, using two helper functions to track vowel and consonant counts.

Complexity

• O(n^2), where n is the length of the word, due to nested loops in the sliding window approach.

Solution Code:

class Solution {
public:
    long countOfSubstrings(string word, int k) {
        return atLeastK(word, k) - atLeastK(word, k + 1);
    }

private:
    long atLeastK(string word, int k) {
        long numValidSubstrings = 0;
        int start = 0;
        int end = 0;
        // Keep track of counts of vowels and consonants.
        unordered_map vowelCount;
        int consonantCount = 0;

        // Start sliding window.
        while (end < word.length()) {
            // Insert new letter.
            char newLetter = word[end];

            // Update counts.
            if (isVowel(newLetter)) {
                vowelCount[newLetter]++;
            } else {
                consonantCount++;
            }

            // Shrink window while we have a valid substring.
            while (vowelCount.size() == 5 and consonantCount >= k) {
                numValidSubstrings += word.length() - end;
                char startLetter = word[start];
                if (isVowel(startLetter)) {
                    if (--vowelCount[startLetter] == 0) {
                        vowelCount.erase(startLetter);
                    }
                } else {
                    consonantCount--;
                }
                start++;
            }

            end++;
        }

        return numValidSubstrings;
    }

    bool isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
};

Leetcode Problem:

• Alternating Groups II

Summary

• Find the number of alternating groups in a circle of red and blue tiles

Approach

• This solution uses a circular approach to find the alternating groups
• It first extends the colors array to make it circular, then it iterates through the array in two passes: one from the start and one from the middle of the array
• In each pass, it checks for the presence of alternating groups and increments the counter if a group is found.

Complexity

• O(N) where N is the number of tiles in the circle

Explanation

• The solution works by first extending the colors array to make it circular
• This is done by adding the first element to the end of the array
• Then, it iterates through the array in two passes: one from the start and one from the middle of the array
• In each pass, it checks for the presence of alternating groups by comparing the current color with the previous color
• If the colors are alternating, it increments the counter
• Finally, it returns the counter as the number of alternating groups

Solution Code:

class Solution {
public:
    int numberOfAlternatingGroups(vector& colors, int k) {
        int N = colors.size();
        for(int i = 0 ; i < N; i++){
            colors.push_back(colors[i]);
        }
        int cnt = 1;
        int cur = colors[0] ^ 1;
        int ans = 0;
        for(int i = 1; i < k; i++){
            if(cur == colors[i]){
                cnt++;
            }else{
                cnt = 1;
            }
            cur = colors[i] ^ 1;
        }
        if(cnt >= k){
            ans++;
        }
        for(int i = k; i < N + k - 1; i++){
            if(cur == colors[i]){
                cnt++;
            }else{
                cnt = 1;
            }
            if(cnt >= k){
                ans++;
            }
            cur = colors[i] ^ 1;
        }
        return ans;
    }
};

Leetcode Problem:

• Minimum Recolors to Get K Consecutive Black Blocks

Summary

• The problem is to find the minimum number of operations required to have at least k consecutive black blocks in a given string of blocks, where each block is either 'W' or 'B'.

Approach

• The solution uses a sliding window approach to track the number of consecutive black blocks
• It initializes a counter for the number of white blocks within the first k blocks and then slides the window to the right, updating the counter and the minimum number of operations required.

Complexity

• O(n), where n is the length of the string, as each character in the string is processed once.

Explanation

• The solution starts by initializing a counter for the number of white blocks within the first k blocks
• It then slides the window to the right, updating the counter and the minimum number of operations required
• If a white block is encountered within the window, the counter is decremented
• If a black block is encountered within the window, the counter is incremented
• The minimum number of operations required is updated at each step to reflect the current number of white blocks within the window.

Solution Code:

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int w = 0;
        for(int i = 0 ; i < k; i++){
            if(blocks[i] == 'W') w++;
        }
        int ans = w;
        for(int i = k; i < blocks.size(); i++){
            if(blocks[i - k] == 'W'){
                w--;
            }
            if(blocks[i] == 'W'){
                w++;
            }
            ans = min(ans, w);
        }
        return ans;
    }
};

Leetcode Problem:

• Closest Prime Numbers in Range

Summary

• Find two prime numbers within a given range with the minimum difference.

Approach

• Use the Sieve of Eratosthenes algorithm to generate prime numbers, then iterate through the range to find the pair with the minimum difference.

Complexity

• O(n log log n) due to the Sieve of Eratosthenes algorithm, where n is the upper bound of the range.

Explanation

• The Sieve of Eratosthenes algorithm is used to generate prime numbers up to the given upper bound
• Then, iterate through the range to find the pair of prime numbers with the minimum difference
• If no such pair exists, return [-1, -1].

Solution Code:

class Solution {
public:
    bool isPrime[1000001] = {false};
    vector closestPrimes(int left, int right) {
        for(int i = 2; i <= right; i++){
            isPrime[i] = true;
        }
        for(int i = 2; i*i <= right; i++){
            if(!isPrime[i]){
                continue;
            }
            for(int j = i *2; j <= right; j += i){
                isPrime[j] = false;
            }
        }
        
        vector ans;
        int beforePrime = 0;
        for(int i = left; i <= right; i++){
            if(!isPrime[i]){
                continue;    
            }
            if(ans.size() < 2){
                ans.push_back(i);
                beforePrime = i;
                continue;
            }
            else{
                if((ans[1] - ans[0]) > (i - beforePrime)){
                    ans[0] = beforePrime;
                    ans[1] = i;
                }
            }
            beforePrime = i;
        }
        if(ans.size() == 2) return ans;
        return {-1, -1};
    }
};

Leetcode Problem:

• Find Missing and Repeated Values

Summary

• Find the repeating and missing numbers in a 2D grid.

Approach

• Use a boolean array to track the presence of each number in the grid, then iterate through the array to find the repeating and missing numbers.

Complexity

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

Explanation

• The solution first initializes a boolean array 'appear' of size n*n+1 to track the presence of each number
• It then iterates through the grid, setting the corresponding index in the 'appear' array to true for each number
• After that, it iterates through the 'appear' array and adds the index that is still false to the result vector
• This process finds the missing number
• The repeating number is found by iterating through the grid and adding the number to the result vector if it is already set to true in the 'appear' array.

Solution Code:

class Solution {
public:
    bool appear[2501] = {false,};
    vector findMissingAndRepeatedValues(vector>& grid) {
        int N = grid.size();
        vector ans;
        for(int i = 0 ; i < N; i++){
            for(int j = 0 ; j < N; j++){
                if(appear[grid[i][j]]){
                    ans.push_back(grid[i][j]);
                }
                appear[grid[i][j]] = true;
            }
        }
        for(int i = 1 ; i <= N*N; i++){
            if(!appear[i]){
                ans.push_back(i);
                return ans;
            }

        }
        return ans;
    }
};

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