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

然而，我真正的问题是，当我事先不知道数组大小时，如何处理数组大小。顺便说一句，谢谢你的小数点……那在面试时会很尴尬。

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 框架中大多数不断增长的数据结构（列表、堆栈、队列等）所做的。

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

编辑以处理案例：

在这种情况下，我建议重载该函数。通过在下面添加

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 回答