iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 23
0
Software Development

用JS來刷刷HackerRank系列 第 29

(25)HackerRank-Interview-Arrays-Array Manipulation(javaScript ans)

題目
Array Manipulation
舉例輸入

5 3
1 2 100
2 5 100
3 4 100

舉例輸出

200


解析
題旨:這個陣列長度五,進行元素加法三次
1~2位置元素+100=>[100,100,0,0,0]
2~5位置元素+100=>[100,200,100,100,100]
3~4位置元素+100=>[100,200,200,200,100]
那麼我們照題目按直覺直接寫

function arrayManipulation(n, queries) {
    let ansArray = new Array(n);
    let max = 0
    // 陣列通通給0
    queries.forEach(el => {
        //從哪裡開始加,加到哪,加多少
        let iStart = el[0] - 1
        let iEnd = el[1] - 1
        let plus = el[2]
        //進行加法
        for (let i = iStart; i <= iEnd; i++) {
            ansArray[i] = (ansArray[i] || 0) + plus;
            //判斷現在最大的數
            if (ansArray[i] > max) {
                max = ansArray[i]
            }
        }

    })
    return max;
}

是的,不知道哪個很變態很多很大的參數又被執行了,顯示time out

於是乎我們只能思考別的方法

既然不允許我們對每個元素進行運算
那麼我們換個思考
這個區間被加最多次,一定最大
那麼我們只要知道這個區間被加了幾次
我們就可以知道最大的數可能為多少

因此...

function arrayManipulation(n, queries) {
    let ansArray = [];
    queries.forEach(el => {
        let [iStart, iEnd, plus] = el
        //從這裡開始都有被加,所以標記+plus
        ansArray[iStart] = (ansArray[iStart] ? (ansArray[iStart] + plus) : plus);
        if (iEnd + 1 <= n) {
            //從這裡都沒被加,所以相對於其他少加,要扣掉
            ansArray[iEnd + 1] = (ansArray[iEnd + 1] ? (ansArray[iEnd + 1] - plus) : -plus);
        }

    })

    let max = 0,
        sum = 0;
    //判斷被加最多的可能為多少
    for (var i = 0; i < ansArray.length; i++) {
        sum += (ansArray[i] || 0);
        max = Math.max(max, sum);
    }
    return max;
}
 

上一篇
(24)HackerRank-Interview-Arrays-Minimum Swaps 2(javaScript ans)
下一篇
(30)HackerRank-Interview-Sorting-Sorting: Bubble Sort(javaScript ans)
系列文
用JS來刷刷HackerRank30

尚未有邦友留言

立即登入留言