是的,我有一个家庭作业问题,我已经解决了,但在测试用例上一直出现超时错误,我不明白为什么。
你需要为侄子买生日玩具。但是你只有有限的钱。但是,您想为侄子购买尽可能多的独特玩具。编写一个函数,返回您可以购买的最大数量的独特玩具。
函数的参数是整数数组成本,其中包含每个玩具的成本,以及整数预算,即您可以花费的最大金额。
返回代表您可以购买的最大独特玩具数量的整数
约束
如果 N 是玩具的数量,K 是预算...... 1<=N<=105 1<=K<=109 1<=任何玩具的价格<=109
示例输入
成本:{1, 12, 5, 111, 200, 1000, 10} 预算:50 示例返回值
4 说明
他最多只能买4个玩具。这些玩具的价格如下:1,12,5,10。
所以这就是我写的,它在 10 个测试用例上不断给出超时错误。我不明白为什么
function maxPurchasedToys(costs, budget) {
var costsLess=[];
var removeFromArray=function(arr, value){
for(i in arr){
if(arr[i]==value){
arr.splice(i,1);
break;
}
}
return costsLess;
}
//First let's get a new array consisting only of costs that are equal to or below the budget
costs.map(function(x){x<budget?costsLess.push(x):1;})
var sum=0;
costsLess.map(function(x){sum+=x;});//Get the sum of budget
while(sum>=budget){
var max=Math.max.apply( Math, costsLess );
costsLess=removeFromArray(costsLess,max);//Remove the biggest element to ensure that the costs fall within budget
sum=0;
costsLess.map(function(x){sum+=x;});//Get the new sum of budget
}
return costsLess.length;
}
我尝试了以下案例:原始测试案例 [5000,2000,20,200],50 以及更多。一切顺利
最佳答案
为什么不简单地排序和迭代?
function maxPurchasedToys (costs, budget) {
var i = 0, sum = 0, count = 0,
l = costs.length;
costs.sort(function (a, b) { return a - b });
while ( i < l ) {
if ( budget >= sum + costs[i] ) {
sum = sum + costs[i];
count++;
i++;
} else {
break;
}
}
return count;
}
这是 fiddle :http://jsfiddle.net/Ya5MK/
如果你能够使用 ES5 数组方法(你正在使用 map
,所以我想你可以),使用这个:
function maxPurchasedToys (costs, budget) {
var sum = 0, count = 0;
costs.sort(function (a, b) { return a - b }).some(function (cost) {
if ( budget >= sum + cost ) {
sum = sum + cost;
count++;
} else {
return true;
}
});
return count;
}
这是 fiddle :http://jsfiddle.net/Ya5MK/1/
关于javascript - 最大购买玩具超时,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18555120/