计算团队数量-Javascript

Question

我正在尝试用JavaScript解决下面的问题。

有n名士兵排成一行。每个士兵都被分配了一个唯一的评级值。

你必须组成一支由3名士兵组成的队伍，其中包括以下人员规则：

选择3名具有指数(i，j，k(和等级(等级[i]，评级[j]、评级[k](。如果：(rating[i]<rating[j]<rating[k](或(rating[i]>rating[j]>rating[k+(，其中(0<=i<j<k<n( 。返回给定条件下可以组建的团队数量。(士兵可以是多个团队的一部分(。

示例：

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). 

我的想法是保留一个可能组合的数组，当我达到组合中的3个元素时，我会递增res变量。我的尝试：

var numTeams = function(rating) {
let res = 0;
if(!rating || rating.length < 3)  return res;

let combinations = [];
for(let i=0; i<rating.length; i++) {
const size = combinations.length;
for(let j=0; j<size; j++) {
const temp = combinations[j];
if(temp.length === 1 && temp[0] !== rating[i]) {
temp.push(rating[i]);
combinations.push(temp);
} else {
if(temp[0] < temp[1] && temp[1] < rating[i])
res++;
else if(temp[0] > temp[1] && temp[1] > rating[i])
res++;
}
}
combinations.push([rating[i]]);
}

return res;
};

对于示例输入，它返回2，而不是3。

Answer 1

我建议使用三个封装的for循环。通过用外循环的索引的当前值的值初始化索引，例如k = i，条件(0 <= i < j < k < n)被隐含地满足。在最内部的循环中，您可以通过检查rating[i] < rating[k] && rating[k] < rating[l]或rating[i] > rating[k] && rating[k] > rating[l]来检查当前士兵集的combination条件是否为真，并将值添加到包含有效组合的数组中。最后，打印包含有效组合的数组的长度：

var rating = [2,5,3,4,1];
var combinations = [];

for (i = 0; i < rating.length; i = i+1) {
for (k = i; k < rating.length; k = k+1) {
for (l = k; l < rating.length; l = l+1) {
if (rating[i] < rating[k] && rating[k] < rating[l]) {
combinations.push([rating[i], rating[k], rating[l]]);
}
if (rating[i] > rating[k] && rating[k] > rating[l]) {
combinations.push([rating[i], rating[k], rating[l]]);
}
}
}
}
console.log(combinations);
console.log(combinations.length);

输出：

[ [ 2, 3, 4 ], [ 5, 3, 1 ], [ 5, 4, 1 ] ]
3

Answer 2

与答案中提供的三个For循环相比，性能更好https://stackoverflow.com/a/64921918/9240674，我现在也只在rating数组上迭代一次。数组CCD_ 8保存可能成为有效组合的所有变体。条目由用于确定变体是否为有效组合的函数和ratings组成。在rating阵列上的每次迭代中，如果新的rating[i]可能完成当前检查的变化而成为有效的combination，则将其与所有variations进行检查。如果是，则当前variation[k]的ratings被存储在combinations阵列中。

var rating = [2,5,3,4,1];
var variations = [];
var combinations = [];
function less_than(a, b) {
return a < b;
}
function greater_than(a, b) {
return a > b;
}
for (i = 0; i < rating.length; i = i + 1) {
var duplications = [];
for (k = 0; k < variations.length; k = k + 1) {
if (variations[k].ratings.length < 3) {
if (variations[k].comparemethod(rating[i],variations[k].ratings[variations[k].ratings.length-1])) {
// Duplicate current (incomplete) variation
duplications.push({"comparemethod": variations[k].comparemethod, "ratings": variations[k].ratings.slice()});
// Add the current rating to the current variation
variations[k].ratings.push(rating[i]);
}
if (variations[k].ratings.length == 3) {
// we found a valid combination
combinations.push(variations[k].ratings);
}
}
}
// add entries which needed to be duplicated to the variations
variations = variations.concat(duplications);
// add the current rating to the variations
variations.push({comparemethod: less_than,    ratings: [rating[i]]});
variations.push({comparemethod: greater_than, ratings: [rating[i]]});
}

console.log(JSON.stringify(combinations));
console.log(combinations.length);

输出：

[[2,3,4],[5,3,1],[5,4,1]]
3