国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

筆試算法之王大錘發(fā)獎(jiǎng)金問題（JS）

missonce / 3103人閱讀

摘要：筆試算法之王大錘發(fā)獎(jiǎng)金問題需求論資排輩發(fā)獎(jiǎng)金按照工齡發(fā)獎(jiǎng)金，任意兩個(gè)相鄰的員工之間，工齡高的發(fā)工資必須多。所以，假設(shè)連續(xù)降低了個(gè)人，那么這些人的獎(jiǎng)金一共為最后，還要判斷最開始左邊出現(xiàn)的工齡最高的人是否需要追加。

筆試算法之王大錘發(fā)獎(jiǎng)金問題 需求

論資排輩發(fā)獎(jiǎng)金： 按照工齡發(fā)獎(jiǎng)金，任意兩個(gè)相鄰的員工之間，工齡高的發(fā)工資必須多。

每人至少發(fā)100。

發(fā)的獎(jiǎng)金總數(shù)最少

思路一

先給每人算100

兩次遍歷：

第一次從左到右遍歷，出現(xiàn)右邊比左邊工齡高的，給右邊的多發(fā)100.

第二次從右往左遍歷，出現(xiàn)左邊比右邊工齡高的，然而左邊工資卻不比右邊高的話，給左邊的多發(fā)100.

將獎(jiǎng)金數(shù)組內(nèi)的值累加，返回結(jié)果。

JS實(shí)現(xiàn)思路一 
function calcBonus(peopleArr) {
            var resultArr = [];
            var n = peopleArr.length
            for (let i = 0; i < n; i++) {
                resultArr[i] = 100;
            }
            for (let i = 1; i < n; i++) {
                if (peopleArr[i] > peopleArr[i - 1]) {
                    resultArr[i] = resultArr[i - 1] + 100;
                }
            }
            for (let i = n - 1; i > -1; i--) {
              // 判斷左邊的是否比右邊工齡高，且工資不比右邊的高
                if (peopleArr[i - 1] > peopleArr[i] && resultArr[i - 1] < resultArr[i] + 100) {
                    resultArr[i - 1] = resultArr[i] + 100;
                }
            }
            var result = 0;
            for (let i = 0; i < n; i++) {
                result += resultArr[i]
            }
            return result;
        }

// 測試用例：
var peopleArr1 = [9, 6, 3] 
calcBonus(peopleArr1) //300, 200, 100 => 600
var peopleArr2 = [1, 4, 5, 9, 3, 2] 
calcBonus(peopleArr2)// 100, 200, 300, 400, 200, 100 => 1300

時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(N)

思路二

只遍歷一次，直接求出最終需要發(fā)的獎(jiǎng)金和：

先給第一個(gè)人發(fā)100；

右邊和左邊的工齡相等，同樣發(fā)100；

右邊比左邊的工齡高，追加100

右邊的工齡比左邊的低，那么需要深入討論：

假設(shè)目前出現(xiàn)左邊出現(xiàn)的工齡為最高，一直向后找到最后一個(gè)工齡不再降低的人為止。

然后向前推，每往前一個(gè)，就追加100，追加到第一個(gè)工齡開始降低的人，相當(dāng)于等差數(shù)列。所以，假設(shè)連續(xù)降低了n個(gè)人，那么這些人的獎(jiǎng)金一共為 100n * (n + 1) / 2

最后，還要判斷最開始左邊出現(xiàn)的工齡最高的人是否需要追加。如果他的獎(jiǎng)金不大于右邊的，那么就需要追加100n減去他的原獎(jiǎng)金的再加上100.

為更好理解，可看以下兩個(gè)測試用例：

var peopleArr3 = [1, 5, 4, 2, 3, 1] // 100, 300, 200, 100, 200, 100 => 1000
var peopleArr4 = [1, 2, 3, 4, 5, 3, 2, 1] // 100, 200, 300, 400, 500, 300, 200, 100 => 2100

PS: 為方便計(jì)算，可將單位值設(shè)為1，那么最后的result * 100即可。

JS實(shí)現(xiàn)思路二 
function calcBonus2(peopleArr) {
            var result = 1;
            var n = peopleArr.length;
            var curMax = 1;
            var count = 0;
            for(let i = 1; i < n; i++) {
                if(peopleArr[i] >= peopleArr[i - 1]){
                    if(count){
                        accCount();
                    }
                    curMax = peopleArr[i] == peopleArr[i - 1] ? 1 : curMax + 1
                    result += curMax
                }else {
                    ++count
                }
            }
            if(count) {
                accCount();
            }
            function accCount() {
                result += count * (count + 1) / 2;
                if(count >= curMax){
                            result += count - curMax + 1;
                            count = 0;
                            curMax = 1;
                        }
            }
            return result * 100;
        }

calcBonus2(peopleArr3); // 1000
calcBonus2(peopleArr4); // 2100

時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

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

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/106639.html

相關(guān)文章

  • js設(shè)計(jì)模式--策略模式

    摘要：將不變的部分和變化的部分隔開是每個(gè)設(shè)計(jì)模式的主題，策略模式也不例外，策略模式的目的就是將算法的使用與算法的實(shí)現(xiàn)分離開來。 前言 本系列文章主要根據(jù)《JavaScript設(shè)計(jì)模式與開發(fā)實(shí)踐》整理而來，其中會加入了一些自己的思考。希望對大家有所幫助。 文章系列 js設(shè)計(jì)模式--單例模式 js設(shè)計(jì)模式--策略模式 js設(shè)計(jì)模式--代理模式 概念 策略模式的定義是:定義一系列的算法，把它們一個(gè)...

    bigdevil_s 評論0 收藏0

  • JavaScript設(shè)計(jì)模式與開發(fā)實(shí)踐系列之策略模式

    摘要：本系列為設(shè)計(jì)模式與開發(fā)實(shí)踐作者曾探學(xué)習(xí)總結(jié)，如想深入了解，請支持作者原版策略模式策略模式的定義定義一系列的算法，把它們一個(gè)個(gè)封裝起來，并且使它們可以互相替換。 本系列為《JavaScript設(shè)計(jì)模式與開發(fā)實(shí)踐》（作者：曾探）學(xué)習(xí)總結(jié)，如想深入了解，請支持作者原版 策略模式 策略模式的定義：定義一系列的算法，把它們一個(gè)個(gè)封裝起來，并且使它們可以互相替換。 舉個(gè)形象的例子，使用策略模式計(jì)算...

    spademan 評論0 收藏0

  • JS策略模式《JavaScript設(shè)計(jì)模式與開發(fā)實(shí)踐》閱讀筆記

    摘要：策略模式可以避免代碼中的多重判斷條件。策略模式在程序中或多或少的增加了策略類。此文僅記錄本人閱讀設(shè)計(jì)模式與開發(fā)實(shí)踐這個(gè)本時(shí)的感受，感謝作者曾探寫出這么好的一本書。設(shè)計(jì)模式中很重要的一點(diǎn)就是將不變和變分離出來。參考設(shè)計(jì)模式與開發(fā)實(shí)踐曾探 策略模式的定義是：定義一系列的算法，把它們一個(gè)個(gè)封裝起來，并且是它們可以相互替換。 策略模式可以避免代碼中的多重判斷條件。 策略模式很好的體現(xiàn)了開放-...

    Amos 評論0 收藏0

  • PHP面試常考之設(shè)計(jì)模式——策略模式

    摘要：策略模式介紹策略模式定義了一系列的算法，并將每一個(gè)算法封裝起來，而且使它們還可以相互替換。策略模式讓算法獨(dú)立于使用它的客戶而獨(dú)立變化。使用策略模式的好處策略模式提供了管理相關(guān)的算法族的辦法。使用策略模式可以避免使用多重條件轉(zhuǎn)移語句。 你好，是我琉憶，PHP程序員面試筆試系列圖書的作者。 本周（2019.3.11至3.15）的一三五更新的文章如下： 周一：PHP面試常考之設(shè)計(jì)模式——工...

    Drinkey 評論0 收藏0

  • 博士生AI崗位面試經(jīng)驗(yàn)分享：這樣可以讓您的薪水翻一倍

    摘要：本文就是作者根據(jù)自己求學(xué)和求職心路歷程，對博士生求職崗位的經(jīng)驗(yàn)分享。此外，地域范圍也僅限在歐洲，其他地方的薪資標(biāo)準(zhǔn)和福利都不一樣。機(jī)器學(xué)習(xí)面試這類面試有些只會測試一般的機(jī)器學(xué)習(xí)知識。這類面試一般分為兩部分。 showImg(http://upload-images.jianshu.io/upload_images/13825820-a135ab6933a4f7b7.jpg?imageM...

    FrozenMap 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<