查找具有未知数字的数字之间的最小可能差异

Question

我有一些案例如下

1？ 2?
?2? ??3
？？
?5 ?0

现在我应该做的是找到一些值来代替问号，这将使两个数字之间的差异最小化。

答案应该像

19 20
023 023
0 0
05 00

注意：2个值的最小绝对差后产生的数必须是最小的。如前所述，最后一种情况可能是 15 和 10，绝对差为 5，但它是无效的。

我尝试了一些排列组合的想法，分别替换两个数字的问号，然后找出数字，但数字的长度可能高达每个数字 18 位。因此，我认为这不是一个好主意。

然后我尝试搜索类似的问题，但没有帮助。我仍然认为 regex 可能有助于解决这个问题，但我仍然不知道如何去做。

欢迎任何帮助！！谢谢！

语言应为Php..我正在使用Php.

Answer 1

好的，我有办法了。

解释：

使用正则表达式获取两个数字，然后从左到右成对比较它们，首先假设它们相等。这意味着它们都尽可能解析为相同的数字，如果它们都是 ?.

则为 0

有一对数不相等后，开始将小的?设置为9，大的?设置为0，让它们尽可能靠近。

Here 就是其中的一个例子。

function minDiff($str) {
    preg_match("/([\d\?]+) ([\d\?]+)/", $str, $matches);
    
    $first = $matches[1];
    $second = $matches[2];
    
    $biggest = 0; // -1 = first, 0 = none, 1 = second
    
    $firstResult = 0;
    $secondResult = 0;
    
    for ($i = 0; $i < strlen($first); $i++) {
        $powerValue = strlen($first) - $i - 1;
        if ($biggest != 0) { // not equal
            if (!strcmp($first[$i], '?') && !strcmp($second[$i], '?')) {
                if ($biggest > 0) { // second is biggest
                    $firstResult += 9 * pow(10, $powerValue);
                } else { // first is biggest
                    $secondResult += 9 * pow(10, $powerValue);
                }
            } elseif (!strcmp($first[$i], '?')) {
                if ($biggest > 0) { // second is biggest
                    $firstResult += 9 * pow(10, $powerValue);
                }
                $secondResult += $second[$i] * pow(10, $powerValue);
            } elseif (!strcmp($second[$i], '?')) {
                if ($biggest < 0) { // first is biggest
                    $secondResult += 9 * pow(10, $powerValue);
                }
                $firstResult += $first[$i] * pow(10, $powerValue);
            } else {
                $firstResult += $first[$i] * pow(10, $powerValue);
                $secondResult += $second[$i] * pow(10, $powerValue);
            }
        } else { // both equal (so far)
            if (!strcmp($first[$i], '?')) {
                $firstResult += $second[$i] * pow(10, $powerValue);
                $secondResult += $second[$i] * pow(10, $powerValue);
            } elseif (!strcmp($second[$i], '?')) {
                $firstResult += $first[$i] * pow(10, $powerValue);
                $secondResult += $first[$i] * pow(10, $powerValue);
            } else {
                if (intval($first[$i]) > intval($second[$i])) {
                    $biggest = -1;
                } elseif (intval($first[$i]) < intval($second[$i])) {
                    $biggest = 1;
                }
                $firstResult += $first[$i] * pow(10, $powerValue);
                $secondResult += $second[$i] * pow(10, $powerValue);
            }
            
            // Find if next number will change
            if (($i + 1) < strlen($first) && strcmp($first[$i + 1], '?') && strcmp($second[$i + 1], '?')) {
                $diff = preg_replace('/\?/', '0', substr($first, $i + 1)) - preg_replace('/\?/', '0', substr($second, $i + 1));
                echo "$diff\n";
                // Check to see if you need to add 1 to the value for this loop
                if ($diff > pow(10, $powerValue) / 2) {
                    $secondResult += pow(10, $powerValue);
                    $biggest = 1;
                } elseif ($diff < pow(10, $powerValue) / -2) {
                    $firstResult += pow(10, $powerValue);
                    $biggest = -1;
                }
            }
        }
    }
    
    echo "first: ".str_pad($firstResult, strlen($first), "0", STR_PAD_LEFT)."\n";
    echo "second: ".str_pad($secondResult, strlen($second), "0", STR_PAD_LEFT)."\n\n";
}

查找具有未知数字的数字之间的最小可能差异

Find Minimum Possible difference between numbers with unknown digits

php

regex

numbers

difference

解释：