Найти минимально возможную разницу между числами с неизвестными цифрами

У меня есть несколько случаев следующим образом.

  • 1? 2?
  • ?2? ?? 3
  • ? ?
  • ?5? 0

Теперь, что я должен сделать, это найти некоторые значения вместо вопросительных знаков, которые дадут минимально возможную разницу между двумя числами.

Ответы должны быть похожи

  • 19 20

  • 023 023

  • 0 0

  • 05 00

Примечание: число, которое будет получено после минимальной абсолютной разницы между двумя значениями, должно быть наименьшим. Например, последний случай может быть 15 и 10 с абсолютной разницей 5, но он недействителен.

Я попробовал несколько вариантов сочетаний перестановок для замены вопросительных знаков для обоих чисел по отдельности, а затем выяснил число, но длина номера могла доходить до 18 цифр на число. Поэтому я считаю, что это не будет хорошей идеей.

Затем я попытался найти похожие вопросы, но это не помогло.
Я все еще думаю, что regex может быть полезным для решения этого вопроса, но я застрял с тем, как это сделать.

Любая помощь приветствуется! Thanx!

Язык должен быть Php. Я работаю с Php.

11

Решение

Хорошо, у меня есть решение.

Объяснение:

Использует регулярное выражение для захвата двух чисел, затем сравнивает их в парах слева направо, начиная с предположения, что они равны. Это означает, что они оба разрешают одно и то же число, где это возможно, или 0, если они оба ?,

После того, как есть пара чисел, которые не равны, начинается установка нижних ?к 9и высшие ?к 0, чтобы сделать их как можно ближе.

Вот это пример этого в действии.

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";
}
5

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector