0

所以，是的，我有一个家庭作业类型的问题，我已经解决了，但在测试用例上不断给出超时错误，我不知道为什么。

你需要为侄子的生日买玩具。但你只有有限的钱。但是，您想为您的侄子购买尽可能多的独特玩具。编写一个函数，返回您可以购买的最大独特玩具数量。

函数的参数是整数数组成本，其中包含每个玩具的成本和整数预算，即您可以花费的最大金额。

返回代表您可以购买的最大独特玩具数量的整数

约束

如果 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 等等。一切正常

4

2 回答 2

1

为什么不简单地排序和迭代？

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;
}

这是小提琴：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;
}

这是小提琴：http: //jsfiddle.net/Ya5MK/1/

于 2013-09-01T04:31:44.383 回答
0

您可以尝试使用另一种方法，例如按升序对成本数组进行排序，看看您可以在该数组上获取多远

http://www.w3schools.com/jsref/jsref_sort.asp

function maxPurchasedToys (costs, budget) {
    costs.sort(function(a,b){return a-b});
    count = 0;
    money = budget;
    for (i=0; i<costs.length(); i++){
        if (money > costs[i]){
            money -= costs[i];
            count ++;
        }
        else{
            break;
        }
    }
    return count;
}
于 2013-09-01T04:40:03.460 回答