Найти, если любая перестановка ряда находится в пределах диапазона

Question

мне нужно найти, если любая перестановка числа существует в заданном диапазоне, я просто нужно вернуться Да или Нет

Для например: Number = 122 и Range = [200, 250] , Ответ будет Yes, так как 221 существует в пределах диапазона.

PS:

1. Для задачи, что у меня в руке, число для поиска будет иметь только две различные цифры (Это будет содержать только 1 и 2, Например: 1112221121).
2. Это не вопрос домашней работы. Это было задано в интервью.
3. Подход, который я предложил, заключался в том, чтобы найти все перестановки заданного числа и проверить. Или проведите цикл по диапазону и проверьте, не найдена ли какая-либо перестановка числа.

Answer 1

Проверка каждой перестановки является слишком дорогостоящей и ненужной.

Во-первых, вы должны смотреть на них как строки, а не числа,

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

Рассмотрите, как набор возможных цифр, которые может удерживать каждая переменная, ограничен диапазоном. Каждая пара цифр/переменных будет либо (a) всегда действительной (b) всегда недействительной; или (c) его обоснованность зависит от конкретных переменных.

Теперь смоделируйте эти зависимости и независимость как график. В случае (в) редко, это будет легко найти время, пропорциональное O (10N) = O (N)

Answer 2

Вы могли бы попробовать реализовать какой-то бинарный поиск:

Если у вас есть 6 и 4 двойки в вашем номере, тогда сначала у вас есть интервал

[1111112222; 2222111111]

Если ваш диапазон не перекрывается с этим интервалом, вы закончите. Теперь разделить этот интервал в середине, вы получите

(1111112222 + 222211111)/2

Теперь найти наибольшее число, состоящее из 1-х и 2-х соответствующего числа, меньше точки разделения. (Вероятно, этот шаг можно было бы улучшить, вычисляя расщепление непосредственно каким-то эффективным способом на основе 1 и 2 или интерпретируя 1 и 2 как 0 и 1 двоичного числа. Можно было бы также рассмотреть возможность использования среднего геометрического числа двух чисел, так как кандидаты могут быть более равномерно распределены между левым и правым.)

[Изменить: Я думаю, что у меня есть это: предположим, что границы имеют форму pq и pr (т. е. p является общим префиксом), а затем строить от q и ra симметричной строки s с 1 в начале и конце строки и 2 в середине и взять ps в качестве точки разделения (поэтому из 1111112222 и 1122221111 вы должны построить 111122222211, префикс - p = 11). ]

Если это число содержится в ассортименте, вы готовы.

Если нет, посмотрите, находится ли диапазон выше или ниже и повторяется с помощью [старой нижней границы, разделения] или [split; old upper bound].

Answer 3

Числа имеют большое имущество, которое я думаю, что может помочь вам здесь:

Для заданного числа стоимостного KXXXX, где дается K, мы можем сделать вывод, что K0000 < = а < K9999 ,

Используя это свойство, мы можем попытаться построить перестановку, которая находится в пределах диапазона:

Давайте возьмем ваш пример:

Диапазон = [200, 250]

Number = 122

Во-первых, мы можем определить, что первое число должно быть 2. У нас есть два 2, так что мы до сих пор хороши.

Второе число должно быть между 0 и 5. У нас есть два кандидата, 1 и 2. Все еще неплохо. Давайте проверим первое значение 1:

Любое число было бы хорошо здесь, и у нас еще есть неиспользуемый 2. Мы нашли нашу перестановку (212), и для этого ответ Да.

Если мы нашли противоречие со значением 1, нам нужно отступить и попробовать значение 2 и так далее.

Если ни одно из решений недействительно, верните No.

Этот алгоритм может быть реализован с использованием обратного слежения и должен быть очень эффективным, так как у вас есть только 2 значения для проверки в каждой позиции. Сложность этого алгоритма равна 2^l, где l - количество элементов.

Answer 4

Предположим, что указанная вами дальность: ABC и DEF (каждый символ представляет собой цифру).

Algorithm permutationExists(range_start, range_end, range_index, nos1, nos2) 

    if (nos1>0 AND range_start[range_index] < 1 < range_end[range_index] and 
      permutationExists(range_start, range_end, range_index+1, nos1-1, nos2)) 
       return true 
    elif (nos2>0 AND range_start[range_index] < 2 < range_end[range_index] and 
      permutationExists(range_start, range_end, range_index+1, nos1, nos2-1)) 
       return true 
    else 
       return false 

Я предполагаю, что каждый номер будет рядом цифр. Данное число представлено как {numberOf1s, numberOf2s}. Я пытаюсь установить цифры (первые 1 с, а затем 2 с) в пределах диапазона, если не декларация возвращает false.

PS: Возможно, я ошибаюсь. Я не знаю, может ли это работать. Я не дал ему много думал, на самом деле ..

UPDATE

я не прав в том, как я выразить алгоритм. Есть несколько изменений, которые необходимо сделать в нем. Вот рабочий код (он работал для большинства моих тестовых случаев): http://ideone.com/1aOa4

Answer 5

Вам действительно нужно проверить не более двух возможных перестановок.

Предположим, что ваш номер входа содержит только цифры X и Y, с X < Y. В вашем примере X = 1 и Y = 2.Я проигнорирую все особые случаи, когда у вас закончилась одна или другая цифра.

Этап 1: Обращайтесь с общим префиксом.

Пусть А - первая цифра в нижней границе диапазона и пусть В - первая цифра в верхней границе диапазона. Если A < B, то мы выполняем фазу 1 и переходим к Фазе 2.

В противном случае A = B. Если X = A = B, тогда используйте X в качестве первой цифры перестановки и повторите фазу 1 следующей цифры. Если Y = A = B, то используйте Y как первую цифру перестановки и повторите фазу 1 следующей цифры.

Если ни X, ни Y не равны A и B, остановите. Ответ №

Этап 2: Выполнен с общим префиксом.

На данный момент, A < B. Если A < < X B, а затем использовать X в качестве первой цифры перестановки и заполнения оставшихся цифр, однако вы хотите. Ответ: Да. (И аналогично, если A < Y < B.)

В противном случае проверьте следующие четыре случая. Не более двух случаев потребует реальной работы.

• Если A = X, попробуйте использовать X в качестве первой цифры перестановки, за которой следуют все Y, а затем остальные X. Другими словами, сделайте остальную часть перестановки максимально возможной. Если эта перестановка находится в зоне действия, то ответ будет да. Если эта перестановка не находится в диапазоне, то никакая перестановка, начинающаяся с X, не может быть выполнена.
• Если B = X, попробуйте использовать X в качестве первой цифры перестановки, а затем остальную часть X, за которой следуют все Y. Другими словами, сделайте остальную часть перестановки настолько малой, насколько это возможно. Если эта перестановка находится в зоне действия, то ответ будет да. Если эта перестановка не находится в диапазоне, то никакая перестановка, начинающаяся с X, не может быть выполнена.
• Аналогичные случаи, если A = Y или B = Y.

Если ни один из этих четырех случаев не прошел успешно, тогда ответ №. Обратите внимание, что не более одного из случаев Х и не более одного из случаев Y могут совпадать.

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