筆記試験のアルゴリズムの王のハンマーはボーナスの問題を出します

需要

年功序列によるボーナス:年功序列によるボーナス、隣接する2人の従業員の間で、年功序列の高い給料は多くなければならない.

一人当たり少なくとも100発.

ボーナス総数最少

考え方1

1人当たり100

2回遍歴:

初めて左から右へ遍歴し、右が左より勤続年数の高いものが出現し、右への多発100.

2回目は右から左へ遍歴し、左が右より勤続年数が高いのに、左が右より給料が高くない場合は、左への多発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)である.

考え方2

一度だけ遍歴して、最終的に必要なボーナスと:

最初の人に100を先に送る.

右と左の勤続年数は同じで、同じように100を出す.

右は左より勤続年数が高く、100を追加

右の勤続年数が左より低い場合は、深く検討する必要があります.

現在左に出現する勤続年数が最も高く、最後の勤続年数が下がらない人を見つけるまで.

そして前に進むごとに100を追加し、最初の勤続年数が下がり始めた人に追加するのは、等差数列に相当する.だから、仮にn人を連続的に下げたとしたら、彼らのボーナスは全部で100 n*(n+1)/2

最後に、一番最初に左に出てくる勤続年数が一番高い人が追加する必要があるかどうかを判断する.もし彼のボーナスが右より大きくなければ、100 nを追加して元のボーナスを差し引いたものに100を加える必要があります.

よりよく理解するには、次の2つのテスト例を参照してください.

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)