-6

我在这个博客中发现了一个微软面试问题

我为你剪掉了这个问题：

“这是一个包含 _ 0 _ 1 _ 2 _ 3 _ 4 _ 5 _ 6 _ 7 _ 8 _ 9 个数字的句子” 使其符合逻辑。所以关键是在有下划线的地方你需要放一个数字，这样整个句子就成真了。即，字符串中有 1 个 0、5 个 1 等。

我在网上找不到答案。我们和我的室友一起手动强制它 =) 并找到了一种解决方案：

1 0, 7 1, 3 2, 2 3, 1 4, 1 5, 1 6, 2 7, 1 8, 1 9

作为一个编程问题，你会如何处理这个问题？您将如何进行蛮力实施？有没有解决这个问题的聪明方法？有不同的解决方案吗？

4

1 回答 1

2

蛮力解决方案相当简单。

尝试每个字符可能出现的次数。将目标出现次数与实际出现次数分开并比较两者。

initialize a 'target' array to the target number of occurrences of each character
  (initial values don't matter - they are assigned before being checked)

initialize an 'occurrences' array to the actual number of occurrences
  (initial values are all 1's in this case)

call bruteForce(0)

bruteForce(value)
  if value > greatest value
    check data and exit is successful
  for i = 1:9
    target[value] = i
    // fail early - not strictly necessary, but should help running time
    if value >= i && occurrences[i] + 1 > target[i]
      continue
    occurrences[i]++
    // recurse
    bruteForce(value + 1)
    occurrences[i]--

Java 现场演示。

于 2013-11-13T11:30:39.640 回答