java - 我怎样才能找到拨号盘问题的解决方案？

Question

P.S 这不是作业题，也不要求完整代码。问题开始为-

您将获得一个带有拨号盘和计算器应用程序的旧触摸智能手机号码。

目标:目标是在拨号盘上输入一个数字。但是由于手机比较旧，有些号码和一些操作是不能碰的。例如。 2、3、5、9 键没有响应，即您不能使用它们但是您始终可以使用计算器中的其他数字和操作来计算数字。可以有多种方法来生成一个数字。计算器有 1-9 和 +,-,*,/,= 作为运算。在计算器中输入数字后，您可以复制该数字并使用它。您必须找到获得数字所需的最少触摸次数。

我尝试了回溯和其他几个来源来寻找解决此类问题的可能方法。

输入:

将有多个测试用例。每个测试用例将由 4 行组成

1. 第一行将由 N,M,O 组成

   • N:拨号盘中可用​​的键数(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:字典映射状态到到达该状态的最快路径。路径是 [last_operation, [..., [second_operation, [first_operation, None]]...] 的类 Lisp 列表，因此您的示例的路径将是 [ '=', ['4', ['+', ['1', 无]]]]。
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 编程，但它有 lambda 形式的匿名函数、Map 形式的字典以及队列的几种实现，包括 LinkedList。所以翻译这段代码应该比较简单。

当然，您必须编写所有函数，编写输入代码来阅读拼图，然后将路径转换回您想要的形式的答案。所以还有很多工作要做。