0

私は凝った IDE と C# を使ってきたので、頭の体操の質問に慣れてきました。この質問に対する解決策はありますが、私の本当の質問は、配列サイズをどのように処理すればよいですか? リストを使用できないと仮定します。これは C# で書かれています。

配列のサイズが小さすぎるか、現在の状態では単にメモリを浪費している可能性があります。アルゴリズムに集中できるように、ネガティブ コインなどのチェックは省略しました。だから私はこの行を取り除きたい：double [] minList = new double[1000];

インタビューの質問は次のとおりです。合計が値になるコインの最小数を返します (不可能な場合は -1:

public static Main(string [] args) {
    double[] coins = {0.01, 0.05, 0.10, 0.25};
    Console.WriteLine(MinNumberOfCoinsToSum(0.24, coins));
} 

public static int MinNumberOfCoinsToSum(double sum, double [] coins)
{
    double [] minList = new double[1000];

    minList[0] = sum;

    for (int i = 1; i < minList.Length; i++)
    {
        double buffer = minList[i-1];
         for (int j = 0; j < coins.Length; j++)
         {
             if(minList[i-1] - coins[j] >= 0.0)
             {
                    buffer = Math.Min(buffer, minList[i-1] - coins[j]);
             }
          }

          minList[i] = Math.Min(minList[i-1], Math.Round(buffer, 2));

          if (minList[i] == 0.0)
          {
                return i;
          }             
     }
      return -1;
}

さて、あなたが言ったことを取り入れた答えは次のとおりです（ただし、見つからない場合は-1は返されません）：

private static int MinNumberOfCoinsToSumRecursiveDecimalVersion(decimal sum,  decimal [] coins)
    {
        decimal buffer = sum;
        for(int i = 0; i < coins.Length; i++)
        {
            if(sum - coins[i] >= 0)
            {
                buffer = Math.Min(buffer, sum - coins[i]);
            }
        }
        if (buffer == sum && sum == 0m)
            return 0;

        if(buffer == sum && sum != 0m)
        {
            return Int32.MinValue;
        }
        int result = 1 + MinNumberOfCoinsToSumRecursiveDecimalVersion(Math.Min(buffer, sum),  coins);
        return result;
    }

しかし、私の本当の問題は、事前にサイズがわからない場合に配列サイズをどのように処理するかです。ところで、10 進数のメモをありがとう... インタビューで恥ずかしかっただろう.

public int MinNumberForCoinSum(int sum, decimal [] coins) {
    // I assume there is a custom Util class, but it would be checking null, empty, or any other business requirement
    foreach(var verification in VerificationUtil.GetArrayVerifications()) {
        verification.Verify(coins);
    }

    if(sum < 0 ) { Throw new InvalidArgumentException()); }

    return MinNumberOfCoinsToSumRecursiveDecimalVersion(sum, coins);
}
4

2 に答える 2

1

不明なアレイサイズを処理するための従来のソリューションは、初期容量を使用し、容量がいっぱいになったときにサイズ変更を開始することです。成長係数は通常2です。これは、.NET Frameworkで成長するデータ構造のほとんどが行うことです（リスト、スタック、キューなど）。

于 2012-04-05T18:50:10.330 に答える
0

不快に聞こえるかもしれませんが、ご容赦ください。問題は、配列のサイズ変更とは何の関係もありません。これが解決策です。

public static int numberOfCoins(double[] coins, double sum){
    int total = 0;
    Arrays.sort(coins);
    int amount = (int)(sum*100);//convert to int for precision
    for(int i=coins.length-1; i>=0 && amount > 0; i--){
        int coin = (int)(100*coins[i]);//convert to int for precision
        total+=amount/coin;
        amount%=coin;
    }
    if(amount>0)
       return -1;
    return total;
}//numberOfCoins

コードをテストする

public static void main(String... args){
    double[] den = {0.01,.10,.05,.25};
    System.out.println(numberOfCoins(den,1.65));
}

INT ケースを処理するように編集します。

その場合、関数をオーバーロードすることをお勧めします。以下にも追加することによって

public static int numberOfCoins(int[] coins, int sum){
    int total = 0;
    Arrays.sort(coins);
    int amount = sum;
    for(int i=coins.length-1; i>=0 && amount > 0; i--){
        total+=amount/coins[i];
        amount%=coins[i];
    }
    if(amount>0)
        return -1;
    return total;
}//numberOfCoins
于 2012-04-05T21:34:53.323 に答える