笔试算法之王大锤发奖金问题（JS）

missonce 发布于2019-08-26 10:42 / 3059人阅读

摘要：笔试算法之王大锤发奖金问题需求论资排辈发奖金按照工龄发奖金，任意两个相邻的员工之间，工龄高的发工资必须多。所以，假设连续降低了个人，那么这些人的奖金一共为最后，还要判断最开始左边出现的工龄最高的人是否需要追加。

笔试算法之王大锤发奖金问题 需求

论资排辈发奖金：按照工龄发奖金，任意两个相邻的员工之间，工龄高的发工资必须多。

每人至少发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 最大流问题算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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