一种聪明的算法，用于查找数字数之和等于数字不支付中段数的次数。

Question

所以，我的朋友今天早上给我发了一个拼图：

查找一天中不同的时间数(使用24小时显示，假设上午的时间表示为8:15，而不是08:15)，其中段数等于数字之和。例如：8:15有电子格式的7+2+5=14段，数字之和为8+1+5=14，因此它符合情况。

因此，我在C# 3.0中提出了以下简单的(但智障的蛮力)解决方案：

// Number of segments in each digit
var digitMap = 
    new Dictionary<char, int>
    {
        {'0',6},{'1',2},{'2',5},{'3',5},{'4',4},
        {'5',5},{'6',5},{'7',3},{'8',7},{'9',5}
    };

var numMatches = (
            from h in Enumerable.Range(0,24)
            from m in Enumerable.Range(0,60)
            select h.ToString() + m.ToString().PadLeft(2,'0') into t 
            let chars = t.ToCharArray()
            where chars.Sum(c => int.Parse(c.ToString())) == chars.Sum(c => digitMap[c])
            select t).Count();

然而，他补充了一个警告：

布鲁特力法是不允许的。

我已经考虑了一段时间了，我正努力想出一个更聪明的算法。我沿着预先过滤不可能的路线前进(例如，数字之和小于6的时候，因为这是最小段和)，但最后我想这只会导致一个更小的解空间，然后被强制执行。

无论如何，我认为这是一个足够有趣的问题，把它扔到那里，看看是否有人能想出一个更聪明的方法。

Answer 1

每个数字总是有相同的偏移量。8总是会使你的部分更低，1总是使你的分段更高，5总是一样，等等。一旦你知道了这个值，你就可以非常快地生成有效的组合，结束你的和是相等的。

Answer 2

不要存储映射到段数的值，而是存储映射到其偏移量的数字值。显然，任何产生零的组合都是可行的。但我们可以进一步缩小范围。

请注意，某些数字“破坏”了组合。例如，任何使用两个零(-12)的组合都会破坏它；没有足够的剩余数字给您+12。因此，在10分钟间隔的1000和2000小时内的所有时间(1000,1010，.)，就像早上时间在前10分钟(1000.1009)内的任何时间一样。

其中三个“破坏”组合消除了三分之二的搜索空间。我将把它作为练习留给读者(我不相信这不是某种家庭作业)。

Answer 3

由于不允许像(08:15)这样的小时内的前导零点，我们假设午夜是由(0:00)表示的。

让我们定义一个数字:=段和数的段偏移量(SO)。

让我们有一个数字映射M到它们的段偏移量。

小时段最小SO = -4 ( 7:xx)小时段最大SO =9( 20:xx)

现在，要确定字符串hhmm是否满足您的条件，我们可以从hhmm字符串的末尾开始扫描，计算mm部件的段偏移和，如果该值的负值超出了[-4,9]范围，那么我们可以拒绝对该字符串的任何进一步计算。这将减少你的方法的野蛮程度。