Учитывая число, найдите, является ли оно блестящим или нет

Ответ 1

Здесь один из способов его решения с помощью динамического программирования:

Предположим, что в качестве ввода мы имеем число d ₀ d ₁... d _N.

Идея состоит в том, чтобы создать таблицу, в которой ячейка (i, j) хранит продукт d _i & middot; d _{я + 1} & middot;... & middot; д <суб > Jсуб > . Это можно сделать эффективно, поскольку ячейку at (i, j) можно вычислить, умножив число в (i-1, j) на d _i.

Так как я (начальный индекс) должен быть меньше или равен j (конечный индекс), мы сосредоточимся на нижнем левом треугольнике таблицы.

После создания таблицы мы проверяем наличие повторяющихся записей.

Здесь конкретное примерное решение для ввода 2673:

• Мы выделяем матрицу М с размерами 4 & times; 4.

• Начнем с заполнения диагоналей: M _{i, i} с d _i:

• Затем переходим строки за строкой и заполняем M _{i, j} с d _i & middot; M _{i-1, jк югу >}

• Результат выглядит как

• Чтобы проверить наличие дубликатов, мы собираем продукты (2, 12, 6, 84, 42, 7, 252, 126, 21, 3), сортируем их (2, 3, 6, 7, 12, 21, 42, 84, 126, 252) и прокрутите, чтобы увидеть, равны ли два последовательных числа. Если это так, мы возвращаем false, иначе true.

В коде Java:

Здесь рабочее решение DP, O (n ²).

public static boolean isColorful(int num) {

    // Some initialization
    String str = "" + num;
    int[] digits = new int[str.length()];
    for (int i = 0; i < str.length(); i++)
        digits[i] = str.charAt(i) - '0';
    int[][] dpmatrix = new int[str.length()][str.length()];

    // Fill in diagonal: O(N)
    for (int i = 0; i < digits.length; i++)
        dpmatrix[i][i] = digits[i];

    // Fill in lower left triangle: O(N^2)
    for (int i = 0; i < str.length(); i++)
        for (int j = 0; j < i; j++)
            dpmatrix[i][j] = digits[i] * dpmatrix[i-1][j];

    // Check for dups: O(N^2)
    int[] nums = new int[digits.length * (digits.length+1) / 2];
    for (int i = 0, j = 0; i < digits.length; i++, j += i)
        System.arraycopy(dpmatrix[i], 0, nums, j, i+1);

    Arrays.sort(nums);

    for (int i = 0; i < nums.length - 1; i++)
        if (nums[i] == nums[i+1])
            return false;

    return true;
}

Для читателей, интересующихся DP, я могу порекомендовать несколько аналогичный вопрос/ответ здесь:

• Найти количество вхождений подпоследовательности в строке

Ответ 2

Использование динамического программирования - это, вероятно, путь: Вместо вычисления всех подстрок O (n ^ 2), а затем используя команды умножения ~ n для вычисления каждого из них, сохраните результаты предыдущей какуляции в матрице M, где M (i, j) является результатом подстроки длина j, начиная с позиции i.

(т.е. если ваш номер 123456789, то M (1,5) равен 5!, а M (1,6) равен 6!, что требует только умножения M (1,5) на 6 - постоянная работа)

Это улучшит время работы от O (n ^ 3) для n цифр до O (n ^ 2).

Ответ 3

Решение по динамическому программированию действительно не требуется, поскольку нет блестящих чисел с большим количеством цифр (если какая-либо цифра появляется более одного раза, номер не является блестящим).

Здесь - список каждого блестящего номера. Всего 57 281.

Этот файл занял менее секунды, чтобы сгенерировать его на моем ПК, даже без использования динамического программирования:)

Ответ 4

если мы не рассматриваем число как большую строку, тогда может помочь хеширование;

 int brill(int A) {
    map<long long int,bool> m;
    vector<int> arr(10,0);
    int i=0;
    while(A){
        arr[i++]=A%10;
        A/=10;
    }

    for(int j=0;j<i;j++){

        long long int temp=1;

        for(int k=j;k>=0;k--){
            temp*=arr[k];

            if(m.find(temp)!=m.end()){
                return 0;
            }
            else{
                m[temp]=true;
            }
        }
    }
    return 1;

}

Ответ 5

n - строка, содержащая число.

Так как число не может превышать 8 цифр до того, как состояние отказа будет установлено O (1).

function isBrill(n) {
  var set = {};
  set[parseInt(n.charAt(0))] = true;
  for(var i=0; i < n.length - 1; i++) {
    var a = parseInt(n.charAt(i));
    var b = parseInt(n.charAt(i+1));
    if(set[b] === true) { return false; }
    set[b] = true;
    if(set[a * b] === true) { return false; }
    set[a * b] = true;
  }
  return true;
}
isBrill("263"); // true
isBrill("236"); // false