灌溉花園的最少水龍頭數(shù)目【LC1326】

在 x 軸上有一個一維的花園?；▓@長度為 n，從點 0 開始，到點 n 結(jié)束。

花園里總共有 n + 1 個水龍頭，分別位于 [0, 1, ..., n] 。

給你一個整數(shù) n 和一個長度為 n + 1 的整數(shù)數(shù)組 ranges ，其中 ranges[i] （下標(biāo)從 0 開始）表示：如果打開點 i 處的水龍頭，可以灌溉的區(qū)域為 [i - ranges[i], i + ranges[i]] 。

請你返回可以灌溉整個花園的 最少水龍頭數(shù)目 。如果花園始終存在無法灌溉到的地方，請你返回 -1 。

過了的那一刻很是震驚 也許是昨天周賽剛看的01背包，也許不大恰當(dāng)，但是我做出來了

01背包

• 思路：每個水龍頭有選或者不選兩種可能，因此轉(zhuǎn)化為01背包問題

  • 物品為每個水龍頭的灌溉范圍
  • 背包容量為灌溉范圍，表示背包能灌溉$0?j$范圍內(nèi)的花園。
  • 定義狀態(tài)$dp[j]$表示 灌溉范圍為$0?j$時，所需要的最少水龍頭數(shù)目。$dp[n]$即為最終結(jié)果
  • 如果位置$i$的水龍頭的灌溉范圍為$[l,r]=[i?ranges[i],i+ranges[i]]$，枚舉每一個灌溉范圍小于$r$的背包，更新需要的水龍頭數(shù)目。

• 一維動態(tài)規(guī)劃

  1. 確定dp數(shù)組（dp table）以及下標(biāo)的含義

     $dp[j]$表示 灌溉范圍為$0?j$時，所需要的最少水龍頭數(shù)目。

  2. 確定遞推公式

     對于每一個位置的水龍頭，更新其能灌溉的右范圍

     • 位置i不放水龍頭：$dp[j]=dp[j]$

     • 位置i放水龍頭，該水龍頭的灌溉范圍記為$[l,r]$：

       • 如果$l\le 0$，那么$dp[j]=1$

       • 如果$l>0$，那么能否灌溉$[0,j]$與$[0,l]$所需要的水龍頭數(shù)目相關(guān)
         $$dp[j]=dp[l]+1$$

  3. dp數(shù)組如何初始化

     當(dāng)位置0的灌溉范圍一定大于等于0，那么灌溉原點需要的最少水龍頭數(shù)目為1

     初始情況時其他的范圍均灌溉不到，因此初始化為任意不可能的數(shù)值，我選擇初始化為$n+2$，當(dāng)最終結(jié)果$dp[n]<n+2$時，就表示可以灌溉整個花園

     dp[0]= 1;
     dp[1,n] = n + 1;
     

  4. 確定遍歷順序

     一維dp

     先遍歷物品，再從后往前遍歷背包重量，將物品i放進(jìn)能放進(jìn)的背包j中

  5. 舉例推導(dǎo)dp數(shù)組

  class Solution {public int minTaps(int n, int[] ranges) {int[] dp = new int[n + 1];Arrays.fill(dp, n + 2);dp[0] = 1;for (int i = 0; i <= n; i++){int l = i - ranges[i], r = i + ranges[i];for (int j = Math.min(r, n); j >= 0; j--){if (l <= 0){dp[j] = 1;}else{dp[j] = Math.min(dp[l] + 1, dp[j]);}}}return dp[n] < n + 2 ? dp[n] : -1;}
  }
  

  • 復(fù)雜度
    • 時間復(fù)雜度：$O(n^2)$,n為數(shù)組長度
    • 空間復(fù)雜度：$O(n)$，dp數(shù)組的額外空間

貪心

• 思路：

  • 首先，對于所有能覆蓋某個左端點的水龍頭，選擇能覆蓋最遠(yuǎn)右端點的那個水龍頭是最優(yōu)的。【貪心】
  • 那么，可以先預(yù)處理$ranges$數(shù)組，求出所有能覆蓋左端點$l$的水龍頭中，右端點最大的那個位置，記錄在數(shù)組 rightMost[i]中。
  • 那么從原點出發(fā)，記錄當(dāng)前所達(dá)到的右端點cur和下一個可以達(dá)到的位置next
    • 當(dāng)next與cur相等時，無法進(jìn)行移動，返回-1
    • 否則，移動到next，步驟+1

  class Solution {public int minTaps(int n, int[] ranges) {int[] rightMost = new int[n + 1];for (int i = 0; i <= n; ++i) {int r = ranges[i];// 這樣寫可以在 i>r 時少寫一個 max// 憑借這個優(yōu)化，恭喜你超越了 100% 的用戶// 說「超越」是因為原來的最快是 2ms，現(xiàn)在優(yōu)化后是 1msif (i > r) rightMost[i - r] = i + r; // 對于 i-r 來說，i+r 必然是它目前的最大值else rightMost[0] = Math.max(rightMost[0], i + r);}int ans = 0;int curRight = 0; // 已建造的橋的右端點int nextRight = 0; // 下一座橋的右端點的最大值for (int i = 0; i < n; ++i) { // 注意這里沒有遍歷到 n，因為它已經(jīng)是終點了nextRight = Math.max(nextRight, rightMost[i]);if (i == curRight) { // 到達(dá)已建造的橋的右端點if (i == nextRight) return -1; // 無論怎么造橋，都無法從 i 到 i+1curRight = nextRight; // 造一座橋++ans;}}return ans;}
  }作者：靈茶山艾府
  鏈接：https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden/solutions/2123855/yi-zhang-tu-miao-dong-pythonjavacgo-by-e-wqry/
  來源：力扣（LeetCode）
  著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
  

  • 復(fù)雜度

    • 時間復(fù)雜度：$O(n)$,n為數(shù)組長度

    • 空間復(fù)雜度：$O(n)$，rightMost數(shù)組的額外空間