该算法题来自于 codewars【语言: javascript】,翻译如有误差,敬请谅解~
- 任务
- 乞丐A和B同时发现一些黄金。他们都想要黄金,他们决定用简单的规则来分配黄金:
他们将黄金分成n个堆,并且排成一行。
每堆的数量和顺序都是随机的。
- 乞丐A和B同时发现一些黄金。他们都想要黄金,他们决定用简单的规则来分配黄金:
他们轮流拿走一堆黄金,最左边或最右边的。
他们总是选择较大的一堆。
也就是说, 如果左边是1,右边是2,就会选择拿2。
如果两边平等,就拿左边的一堆。
- 给定一个整数数组的黄金,并假设A始终是第一个拿的。请计算由A和B获得的黄金的最终金额。返回一个双元素阵列[金额A,金额B]。
- 例如:
- 黄金= [4,2,9,5,2,7],返回[14,15]。
最左边的一堆是4, 最右边的那一堆是7,
A 选择最大的一个 - > 7
- 黄金= [4,2,9,5,2,7],返回[14,15]。
最左边的一堆是4, 最右边的那一堆是2,
B 选择最大的一个 - > 4
最左边的一堆是2, 最右边的那一堆是2,
A 选择最左边的一个 - >取2
最左边的一堆是9, 最右边的那一堆是2,
B 选择最左边的一个 - >取9
最左边的一堆是5, 最右边的那一堆是2,
A 选择最左边的一个 - >取5
只剩下最后一堆 2,
B -- > 取 2
A: 7 + 2 + 5 = 14
B: 4 + 9 + 2 = 15
- 黄金= [10,1000,2,1],返回[12,1001]。
A 取10
B 取1000
A 取2
B 取1
A: 10 + 2 = 12
B: 1000 + 1 = 1001
- 解答
- 其一
const distributionOf = golds => {
let A = 0,B = 0,len = golds.length;
for (let i=0;i<len;i++) {
var max = golds[0] < golds[golds.length - 1] ? golds.pop() : golds.shift();
i == 0 || i%2 == 0 ? A += max : B += max;
}
return [A,B];
}
- 其二
function distributionOf(golds){
const spoils = [0, 0]
let beggar = 0
while (golds.length > 0) {
if (golds[0] >= golds[golds.length - 1])
spoils[beggar] += golds.shift()
else
spoils[beggar] += golds.pop()
beggar = Math.abs(beggar - 1)
}
return spoils
}
- 其三
const distributionOf = (g, a=0, b=g.length-1) => g.reduce((p,_,i) => {
p[i%2] += g[ g[b]>g[a] ? b--:a++];
return p;
} ,[0,0]);
网友评论