0

一个朋友正在做一个在线 Scala 课程并分享了这个。

# Write a recursive function that counts how many different ways you can make
# change for an amount, given a list of coin denominations. For example, there
# are 3 ways to give change for 4 if you have coins with denomiation 1 and 2:
# 1+1+1+1, 1+1+2, 2+2.

如果您正在参加并仍在研究解决方案，请不要阅读此内容！

（免责声明：即使我的 Python 解决方案可能是错误的，如果你在课程中，我不想影响你的想法，不管是哪种方式！我想这是产生学习的想法，而不仅仅是“解决”...）

那一边...

我想我会在 Python 中尝试一下，因为我没有 Scala 印章（我自己不在课程上，只是对学习 Python 和 Java 感兴趣，欢迎“练习”练习）。

这是我的解决方案，我想使用尽可能紧凑的符号将其移植到 Java：

def show_change(money, coins, total, combo):
  if total == money:
    print combo, '=', money
    return 1
  if total > money or len(coins) == 0:
    return 0
  c = coins[0]
  return (show_change(money, coins, total + c, combo + [c]) +
    show_change(money, coins[1:], total, combo))

def make_change(money, coins):
  if money == 0 or len(coins) == 0:
    return 0
  return show_change(money, list(set(coins)), 0, [])

def main():
  print make_change(4, [2, 1])

if __name__ == '__main__':
  main()

问题

  • 如果有帮助，我可以在 Java 中使上述内容变得多么紧凑，允许使用 JDK 外部的库？

我尝试自己进行移植，但它变得非常冗长，我认为通常的“必须有更好的方法来做到这一点”！

这是我的尝试：

import java.util.ArrayList;
import java.util.List;
import com.google.common.collect.Lists;
import com.google.common.primitives.Ints;
public class MakeChange {
  static int makeChange(int money, int[] coins) {
    if (money == 0 || coins.length == 0) {
      return 0;
    }
    return showChange(money, Ints.asList(coins), 0, new ArrayList<Integer>());
  }
  static int showChange(int money, List<Integer> coins, int total,
      List<Integer> combo) {
    if (total == money) {
      System.out.printf("%s = %d%n", combo, total);
      return 1;
    }
    if (total > money || coins.isEmpty()) {
      return 0;
    }
    int c = coins.get(0);
    List<Integer> comboWithC = Lists.newArrayList(combo);
    comboWithC.add(c);
    return (showChange(money, coins, total + c, comboWithC) + showChange(money,
        coins.subList(1, coins.size()), total, combo));
  }
  public static void main(String[] args) {
    System.out.println(makeChange(4, new int[] { 1, 2 }));
  }
}

具体来说，我非常不喜欢的是必须做下面的事情，只是为了传递一个附加了一个元素的列表副本：

    List<Integer> comboWithC = Lists.newArrayList(combo);
    comboWithC.add(c);

请向我展示 Java 的紧凑性和可读性如何。我仍然是两种语言的初学者......

4

1 回答 1

1

确实，您在这里所做的几乎所有事情都可以直接转换为 Java，而没有太多额外的冗长。

例如：

def make_change(money, coins):
  if money == 0 or len(coins) == 0: return 0
  return calculate_change(money, list(set(coins)), 0)

显而易见的 Java 等价物是：

public static int make_change(int money, int coins[]) {
  if (money == 0 || coins.length == 0) return 0;
  return calculate_change(money, coins, 0);
}

一些额外的词在这里和那里，一个额外的行，因为右括号，当然还有显式类型......但除此之外，没有大的变化。

当然，更 Python 和 Javariffic（等效词是什么？）版本将是：

def make_change(money, coins):
  if money == 0 or len(coins) == 0: 
    return 0
  return calculate_change(money, list(set(coins)), 0)

显而易见的 Java 等价物是：

public static int make_change(int money, int coins[]) {
  if (money == 0 || coins.length == 0) {
    return 0;
  }
  return calculate_change(money, coins, 0);
}

因此，Java 获得了一个额外的右大括号和几个空格字符；仍然没什么大不了的。

把整个东西放在一个类中，然后main变成一个方法，增加了大约 3 行。初始化显式数组变量而不是[2, 1]用作文字是 1。和System.out.println比 长几个字符print,比length长 3 个字符len, 每条评论用两个字符//代替 1 个字符#。但我怀疑这些都是你担心的。

最终，总共有一行很棘手：

return (calculate_change(money, coins, total + c, combo + [c]) +
    calculate_change(money, coins[1:], total, combo))

Javaint coins[]没有办法说“给我一个带有当前数组尾部的新数组”。最简单的解决方案是传递一个额外的start参数，因此：

public static int calculate_change(int money, int coins[], int start, int total) {
    if (total == money) {
        return 1;
    }
    if (total > money || coins.length == start) {
        return 0;
    }
    return calculate_change(money, coins, 0, total + coins[start]) +
        calculate_change(money, coins, start + 1 total);
}

事实上，几乎所有东西都可以简单地转换为 C；您只需要为数组的长度传递另一个参数，因为您无法像在 Java 或 Python 中那样在运行时计算它。

你抱怨的那一行是一个有趣的点，值得多加考虑。在 Python 中，你有（实际上）：

comboWithC = combo + [c]

使用 Java 的 List，这是：

List<Integer> comboWithC = Lists.newArrayList(combo);
comboWithC.add(c);

这更冗长。但这是故意的。JavaList<>不应该以这种方式使用。对于小列表，复制周围的所有内容没什么大不了的，但对于大列表，这可能会造成巨大的性能损失。Python 的list设计是基于这样一个假设，即在大多数情况下，您正在处理小列表，并且复制它们非常好，因此编写起来应该很简单。Java 的List设计是基于这样的假设，即有时您正在处理巨大的列表，并且复制它们是一个非常糟糕的主意，因此您的代码应该清楚地表明您确实想要这样做。

理想的解决方案是要么使用不需要复制列表的算法，要么找到一种旨在以这种方式复制的数据结构。例如，在 Lisp 或 Haskell 中，默认列表类型非常适合这种算法，您应该可以在网上找到大约 69105 个“Java 中的 Lisp 样式列表”或“Java 缺点”的配方。（当然，您也可以在 List 周围编写一个简单的包装器，添加一个像 Python 一样的“addToCopy”方法__add__，但这可能不是正确的答案；您想编写惯用的 Java，或者为什么使用 Java 而不是许多其他方法之一JVM 语言？）

于 2012-09-27T23:00:02.467 回答