成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

LeetCode.42 接雨水(Trapping Rain Water)(JS)

MartinDai / 1380人閱讀

摘要：一題目接雨水給定個非負(fù)整數(shù)表示每個寬度為的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。上面是由數(shù)組表示的高度圖，在這種情況下，可以接個單位的雨水藍(lán)色部分表示雨水。提交，答案錯誤。出錯的測試用例為。

做有意思的題是要付出代價的，代價就是死活做不出來。
一、題目

接雨水：

給定 n 個非負(fù)整數(shù)表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。

上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍(lán)色部分表示雨水）。
示例 1:
輸入: [0,1,0,2,1,0,1,3,2,1,2,1]
輸出: 6
二、我的答案 思路1

???????前段時間有在看一個俄羅斯方塊的代碼，所以第一個思路是從下到上一層一層計算，先把數(shù)組中所有的數(shù)-1，然后去掉數(shù)組兩端的-1，再統(tǒng)計數(shù)組中-1的個數(shù)，即為本層接的雨水。這種暴力解法應(yīng)該是可行的，我并沒有把思路落到紙上，各位感興趣可以試一下。

思路2

???????接雨水嘛，兩邊比中間高就能接到，那么我只需要求出所有比左右兩邊高的點，他們兩兩組合就成一個可以接到水的坑，以原題中的示例1為例，下標(biāo)為1，3，7，10的點就是我們所求。代碼如下

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  function fillister (arr) {
    let result = 0
    let baseLine = arr[0] <= arr[arr.length - 1] ? arr[0] : arr[arr.length - 1]
    let difference
    for(let i = 0; i < arr.length; i++) {
      difference = baseLine - arr[i]
      difference > 0 ? result += difference : null
    }
    return result
  }
  let result = 0
  let bigger, smaller, the_dot
  for(let begin = 0; begin < height.length; begin++) {
    bigger = (height[begin - 1] || 0) < height[begin]
    smaller = (height[begin + 1] || 0) < height[begin]
    if (smaller && bigger) {
      if (the_dot !== undefined) {
        result += fillister(height.slice(the_dot, begin + 1))
      }
      the_dot = begin
    }
  }
  return result
};

???????遍歷參數(shù)數(shù)組height，只要符合條件，且不是第一個符合條件的點，就計算該點與之前點之間的積水。提交，答案錯誤。出錯的測試用例為[5,1,2,1,5]。
???????原來按照上述思路，只計算了[5,1,2]和[2,1,5]兩個小水洼，但是[5,1,2,1,5]本身就是個大水洼。意識到計算目標(biāo)點的函數(shù)需要遞歸。
???????根據(jù)這個想法，我進行了大量的編碼，因為這個遞歸調(diào)用的邊界情況比較麻煩，而且越寫越懷疑自己的思路，我始終覺得優(yōu)秀的題解應(yīng)該是簡單的。這里只放出其中對我產(chǎn)生啟發(fā)的一個片段。

  function noNeedToCall (arr) {
    let max = Math.max.apply(null, arr)
    let maxIndex = arr.indexOf(max)
    for(let i = 0, len = arr.length - 1; i < len; i++){
      if(i < maxIndex) {
        if(arr[i] > arr[i + 1]) return false
      } else {
        if(arr[i] < arr[i + 1]) return false
      }
    }
    return true
  }

???????上面這段代碼的作用在于遞歸函數(shù)調(diào)用的最后，判斷是否需要繼續(xù)遞歸。如果在最大值左邊的數(shù)組是遞增或持平，在最大值右邊的數(shù)組是遞減或持平的就不需要遞歸，否則繼續(xù)調(diào)用。也就是說最后求出來是以最大值為界，左邊一個水洼，右邊一個水洼（杠精：“[2,1,3,1,4,1,2]這個例子中最大值4左邊有兩個水洼，垃圾博主”，）左邊一個水洼集，右邊一個水洼集。

思路3

???????雖然左右兩個水洼，但是決定他們范圍的兩個點中的最大值都肯定都是整個數(shù)組的最大值，也就是說決定他們積水量的值也就是較小值是存在于左右兩邊的，那我為什么要各種調(diào)用各種遞歸，直接分左右兩側(cè)共循環(huán)一遍數(shù)組就好了。上代碼

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  const max = Math.max.apply(null, height)
  const maxIndex = height.indexOf(max)
  let i = 0, temp = 0, result = 0
  for (i = 0; i < maxIndex; i++) {
    if (height[i] >= temp) {
      temp = height[i]
    } else {
      result += temp - height[i]
    }
  }
  temp = 0
  for (i = height.length - 1; i > maxIndex; i--) {
    if (height[i] >= temp) {
      temp = height[i]
    } else {
      result += temp - height[i]
    }
  }
  return result
};
三、優(yōu)秀答案 
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    if (!height || !height.length) {
        return 0;
    }
    
    let maxLeftWall = 0;
    let maxRightWall = 0;
    
    let water = 0;
    let i = 0;
    let j = height.length - 1;
    while (i < j) {
        if (height[i] < height[j]) {
            if (height[i] >= maxLeftWall) {
                maxLeftWall = height[i];
            } else {
                water += maxLeftWall - height[i];
            }
            i++;
        } else {
            if (height[j] >= maxRightWall) {
                maxRightWall = height[j];
            } else {
                water += maxRightWall - height[j];
            }
            j--;
        }
    }
    
    return water;
};

???????思路是相似的，不過對于處理最大值的方式不同，代碼放這兒就不細(xì)說了

四、路漫漫其修遠(yuǎn)兮

???????這道題真的難了我好久，從想到求水洼兩端的點，到遞歸調(diào)用的處理，到推翻之前的思路左右分別處理。過程中各種測試用例a通過測試用例b不通過，跟著debugger一點點看然后改然后測試用例b通過測試用例a又不通過。
???????最后思路迸發(fā)出來寫出來提交通過，這種感覺真是爽快，就像是穿著新內(nèi)褲迎接新年來到的早晨一樣。

???????你不要過來?。。?！

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/104649.html

相關(guān)文章

  • Leetcode[42] Trapping Rain Water

    摘要：復(fù)雜度思路因為蓄水多少取決于比較短的那塊板的長度。代碼復(fù)雜度思路考慮說明時候需要計算蓄水量當(dāng)?shù)臅r候，需要計算能儲存的水的多少。每次還需要取出一個作為中間值。如果則一直向里面壓進去值，不需要直接計算。 Leetcode[42] Trapping Rain Water Given n non-negative integers representing an elevation map ...

    jonh_felix 評論0 收藏0

  • leetcode42 Trapping Rain Water

    摘要：我先通過堆棧的方法，找到一個封閉區(qū)間，該區(qū)間可以盛水，該區(qū)間的右節(jié)點可以作為下一個封閉區(qū)間的起點。思路三堆棧的聰明使用在這里，堆棧允許我們漸進的通過橫向分割而非之前傳統(tǒng)的縱向分割的方式來累加計算盛水量。 題目要求 Given n non-negative integers representing an elevation map where the width of each bar...

    GitCafe 評論0 收藏0

  • [LintCode/LeetCode] Trapping Rain Water [棧和雙指針]

    摘要：一種是利用去找同一層的兩個邊，不斷累加寄存。雙指針法的思想先找到左右兩邊的第一個峰值作為參照位，然后分別向后向前每一步增加該位與參照位在這一位的差值，加入，直到下一個峰值，再更新為新的參照位。 Problem Given n non-negative integers representing an elevation map where the width of each bar i...

    bluesky 評論0 收藏0

  • [Leetcode] Trapping Rain Water 積水問題

    摘要：從右向左遍歷時，記錄下上次右邊的峰值，如果左邊一直沒有比這個峰值高的，就加上這些差值。難點在于，當(dāng)兩個指針遍歷到相鄰的峰時，我們要選取較小的那個峰值來計算差值。所以，我們在遍歷左指針或者右指針之前，要先判斷左右兩個峰值的大小。 Trapping Rain Water Given n non-negative integers representing an elevation map ...

    caohaoyu 評論0 收藏0

  • 407. Trapping Rain Water II

    407. Trapping Rain Water II 題目鏈接：https://leetcode.com/problems... 參考discussion里的解法：https://discuss.leetcode.com/... 參考博客里的解釋：http://www.cnblogs.com/grandy... public class Solution { public int tra...

    wenzi 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<