1

我遇到了一个 G+ 帖子，其中有人分享了：

If
  A B C D E F G H I J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z

Equals
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Then
  K + N + O + W + L + E + D + G + E = 96% 
  H + A + R + D + W + O + R + K     = 98%

But
  A + T + T + I + T + U + D + E     = 100%

就这么多，为了它的乐趣，忽略百分比技巧，把剩下的谈话留给 G+ 评论。

但我问自己：从给定的单词列表（一组固定的 n 个单词）中找到所有加起来为 100 的单词的最佳方法（算法）是什么？

4

2 回答 2

3

我认为直接的方法会很好——它是 O( n )：

  1. 创建一个将每个字母与点值相关联的哈希表
  2. 循环遍历列表。对于每个单词，将与哈希表中的字母关联的数字的值相加。如果总和为 100，则打印该单词或以某种方式将其标记为已找到（添加到新列表或其他内容）...

（我想，如果你说“单词”可以任意长，你可能会争论 O( n )；尽管如果单词列表是某种语言中单词的子集，这不是问题。如果你有m是一个单词中的最大字母数，那么算法是 O( nm )。不过，在某些时候你将不得不“查看”每个字母和每个单词，所以我无法想象还有更多省时算法。）

于 2012-07-18T07:22:11.407 回答
2

这里讨论了一个类似的问题。但是，您的具体问题提出了一种更简单的方法。由于单词列表中的单词数量是有限的，并且总是小于最长单词长度的字符排列数，因此最好按照以下方式进行：

假设我们有一个charToNum函数，它将一个字符映射到相应的数字：

for each word in wordlist
  sum := 0
  for each character in word
    sum := sum + charToNum(character)
    if (sum > 100)
      break // Correct result no longer possible
  if (sum == 100)
    Add the word to the result set
于 2012-07-18T07:26:34.247 回答