筆試算法之王大錘發獎金問題（JS）

missonce 發布于2019-08-26 10:42 / 3096人閱讀

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

筆試算法之王大錘發獎金問題 需求

論資排輩發獎金：按照工齡發獎金，任意兩個相鄰的員工之間，工齡高的發工資必須多。

每人至少發100。

發的獎金總數最少

思路一

先給每人算100

兩次遍歷：

第一次從左到右遍歷，出現右邊比左邊工齡高的，給右邊的多發100.

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

將獎金數組內的值累加，返回結果。

JS實現思路一

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

時間復雜度為O(N)，空間復雜度為O(N)

思路二

只遍歷一次，直接求出最終需要發的獎金和：

先給第一個人發100；

右邊和左邊的工齡相等，同樣發100；

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

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

假設目前出現左邊出現的工齡為最高，一直向后找到最后一個工齡不再降低的人為止。

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

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

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

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: 為方便計算，可將單位值設為1，那么最后的result * 100即可。

JS實現思路二

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

時間復雜度O(n)，空間復雜度O(1)

云服務器 GPU云服務器前端基礎js筆試 webrtc之vad算法看動畫學算法之:hashtable 最大流問題算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/106639.html

js設計模式--策略模式

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

bigdevil_s 2019-08-23 14:27 評論0 收藏0
JavaScript設計模式與開發實踐系列之策略模式

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

spademan 2019-08-19 17:48 評論0 收藏0
JS策略模式《JavaScript設計模式與開發實踐》閱讀筆記

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

Amos 2019-08-22 17:57 評論0 收藏0
PHP面試常考之設計模式——策略模式

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

Drinkey 2019-07-01 12:35 評論0 收藏0
博士生AI崗位面試經驗分享：這樣可以讓您的薪水翻一倍

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

FrozenMap 2019-06-26 18:54 評論0 收藏0