打家劫舍 IV【LC2560】

沿街有一排連續(xù)的房屋。每間房屋內都藏有一定的現(xiàn)金?，F(xiàn)在有一位小偷計劃從這些房屋中竊取現(xiàn)金。

由于相鄰的房屋裝有相互連通的防盜系統(tǒng)，所以小偷 不會竊取相鄰的房屋 。

小偷的 竊取能力 定義為他在竊取過程中能從單間房屋中竊取的 最大金額 。

給你一個整數(shù)數(shù)組 nums 表示每間房屋存放的現(xiàn)金金額。形式上，從左起第 i 間房屋中放有 nums[i] 美元。

另給你一個整數(shù) k ，表示竊賊將會竊取的 最少 房屋數(shù)。小偷總能竊取至少 k 間房屋。

返回小偷的 最小 竊取能力。

• 思路：最小化最大值->二分查找

  • 明確題意：求取至少偷k間不相鄰的房屋時，小偷的 最小 竊取能力，即最小化偷取房屋金額的最大值。
  • 尋找單調性（二段性）：偷取能力$y$增加（能偷取的房屋的金額必須小于等于$y$），能偷取不相鄰房屋數(shù)目增加，因此一定存在一個分割點$y$，使得
    • 小于y的值，能夠偷取的房屋數(shù)目 $count$必然不滿足 $count\ge k$；
    • 大于等于y的值，能夠偷取的房屋數(shù)目 $count$必然滿足 $total\ge k$。
  • 二分答案：因此當偷取房屋數(shù)目至少為$k$時，尋找最大偷取數(shù)目的最小值$y$，可以通過二分查找的方法找到最終的$y$，二分查找的下限為min(nums)，上限為max(nums)
  • check函數(shù)：
    • 統(tǒng)計最大偷取數(shù)目為$y$時，能夠偷取的房屋數(shù)目，是否大于$k$，大于則返回true
    • 由于不能偷取相鄰房屋，因此需要記錄上一個偷取的房屋編號

• 實現(xiàn)文章來源地址http://www.zghlxwxcb.cn/news/detail-732127.html

  class Solution {
      public int minCapability(int[] nums, int k) {
          int n = nums.length;
          int l = Integer.MIN_VALUE, r = 0;
          for (int num : nums){
              r = Math.max(r, num);
              l = Math.min(l, num);            
          }
          while (l <= r){
              int mid = (l + r) / 2;
              if (check(nums, mid, k)){
                  r = mid - 1;
              }else{
                  l = mid + 1;
              }
          }
          return l;
  
      }
      public boolean check(int[] nums, int target, int k){
          int n = nums.length;
          int j = -2;
          int count = 0;
          for (int i = 0; i < n; i++){
              if (j + 2 <= i && nums[i] <= target){
                  count++;
                  j = i;
                  if (count >= k) return true;
              }     
          }
          return false;
      }
  
  }
  

  • 復雜度
    • 時間復雜度：$O(n\log C)$，$n$是數(shù)組的長度，C是二分的范圍，即數(shù)組中最最大和最小值的差值。二分查找的時間復雜度是$O(\log C)$，每次二分查找需要判斷是否符合條件的時間復雜度為$O(n)$，因此總的時間復雜度為$O(nlog(nc))$
    • 空間復雜度：$O(1)$

到了這里，關于【每日一題Day331】LC2560打家劫舍 IV | 二分查找 + 貪心的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！