'2025/03/15'에 해당되는 글 1건

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