Как я могу найти решение проблемы Dialpad?

Question

PS Это не домашний вопрос и не полный код.вопрос начинается как -

Вам выдаются старые сенсорные номера смартфонов с клавиатурой и приложением для калькулятора.

Цель: цель состоит в том, чтобы набрать номер на клавиатуре.Но так как телефон старый, некоторые номера и некоторые операции не могут быть затронуты.Например,2,3,5,9 клавиши не отвечают, т.е. вы не можете их использовать, но вы всегда можете сделать число, используя другие числа и операции в калькуляторе.Там может быть несколько способов сделать число.Калькулятор имеет 1-9 и +, -, *, /, = как операции.После того как вы сделали номер в калькуляторе, вы можете скопировать номер и использовать его.Вы должны найти минимальное число касаний, необходимое для получения номера.

Я пытался откатить назад и несколько других источников для возможного способа решения такого вопроса.

Ввод:

Будет несколько тестовых случаев. Каждый тестовый случай будет состоять из 4 строк

1. Первая строка будет состоять из N, M, O

   • N: нет изклавиши, работающие в Dialpad (из 0,1,2,3,4,5,6,7,8,9)
   • M: поддерживаемые типы операций (+, -, *, /)
   • O: максимально допустимое количество касаний

2. вторая строка ввода содержит работающие цифры, например, 0,2,3,4,6.

3. Третья строка содержит значения описывающих операций, 1 (+), 2 (-), 3 (*), 4 (/)
4. четвертая строка содержит число, которое мы хотим сделать.

Вывод:

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

Образец теста:

1 // No of test cases
5 3 5 // N ,M, O
1 2 4 6 0 // digits that are working (total number of digits = N),
1 2 3 // describing operations allowed (1–> ‘+’, 2–> ‘-‘, 3–> ‘*’ , 4–> ‘/’ )(total number is equals to M)
5 // number we want to make

Ответ 3 Как 4?1 + 4 =, «=» также считается касанием.

Answer 1

Это проблема динамического программирования, которую можно решить с помощью словаря.Требуются следующие структуры данных:

1. operation: клавиши сопоставления словаря, которые можно нажимать анонимным функциям, определяя, что он делает с состоянием.Обратите внимание, что числа также являются сложными операциями, например, 1, примененный к текущему состоянию 2, дает вам состояние 21.
2. to_state: словарь отображает состояния на самый быстрый путь, который получаетв это состояние.Где путь - это список, похожий на Lisp [last_operation, [..., [second_operation, [first_operation, None]]...] Так что путь к вашему примеру будет ['=', ['4', ['+', ['1', None]]]].
3. upcoming: очередь [state, path], в которую можно попасть из известных состояний.Он начинается с ['', None].
4. target_state: состояние, в котором мы хотим оказаться.

Сердце кода в Python будет таким:

while (True):
    state, path = upcoming.shift()
    if state in to_state:
        pass # We have a better route here.
    else:
        to_state[state] = path
        for op, func in operation.iteritems():
            next_state = func(state)
            next_path = [op, path]
            if next_state == 'error':
                pass # Don't need this.
            elif next_state == target_state:
                return next_path
            else:
                upcoming.push([next_state, next_path])

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

Конечно, тогда вам нужно написать все функции, написать входной код, чтобы прочитать загадку, и превратить путь обратно в ответ в желаемой форме.Это.Так что впереди еще много работы.