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 に答える