成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專(zhuān)欄INFORMATION COLUMN

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

MartinDai / 1508人閱讀

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

做有意思的題是要付出代價(jià)的，代價(jià)就是死活做不出來(lái)。
一、題目

接雨水：

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

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

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

思路2

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

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

  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)用。也就是說(shuō)最后求出來(lái)是以最大值為界，左邊一個(gè)水洼，右邊一個(gè)水洼（杠精：“[2,1,3,1,4,1,2]這個(gè)例子中最大值4左邊有兩個(gè)水洼，垃圾博主”，）左邊一個(gè)水洼集，右邊一個(gè)水洼集。

思路3

???????雖然左右兩個(gè)水洼，但是決定他們范圍的兩個(gè)點(diǎn)中的最大值都肯定都是整個(gè)數(shù)組的最大值，也就是說(shuō)決定他們積水量的值也就是較小值是存在于左右兩邊的，那我為什么要各種調(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;
};

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

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

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

???????你不要過(guò)來(lái)?。。?！

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/104649.html

相關(guān)文章

  • Leetcode[42] Trapping Rain Water

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

    jonh_felix 評(píng)論0 收藏0

  • leetcode42 Trapping Rain Water

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

    GitCafe 評(píng)論0 收藏0

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

    摘要：一種是利用去找同一層的兩個(gè)邊，不斷累加寄存。雙指針?lè)ǖ乃枷胂日业阶笥覂蛇叺牡谝粋€(gè)峰值作為參照位，然后分別向后向前每一步增加該位與參照位在這一位的差值，加入，直到下一個(gè)峰值，再更新為新的參照位。 Problem Given n non-negative integers representing an elevation map where the width of each bar i...

    bluesky 評(píng)論0 收藏0

  • [Leetcode] Trapping Rain Water 積水問(wèn)題

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

    caohaoyu 評(píng)論0 收藏0

  • 407. Trapping Rain Water II

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

    wenzi 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<