算法生成添加到目标的所有数学表达式组合(Java作业/面试)
我试图解决下面的编码挑战问题,但无法在1小时内完成。我对算法的工作原理有一个想法,但我不太确定如何最好地实现它。下面是我的代码和问题
这个问题很难,因为你可以把数字组合在一起,而你一次也不考虑一个数字。我不确定该如何进行该步骤的组合和递归。请注意,解决方案中没有提供括号,但保留了操作顺序The first 12 digits of pi are 314159265358. We can make these digits into an expression evaluating to 27182 (first 5 digits of e) as follows:
3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182
or
3 + 1 - 415 * 92 + 65358 = 27182
Notice that the order of the input digits is not changed. Operators (+,-,/, or *) are simply inserted to create the expression.
Write a function to take a list of numbers and a target, and return all the ways that those numbers can be formed into expressions evaluating to the target
For example:
f("314159265358", 27182) should print:3 + 1 - 415 * 92 + 65358 = 27182 3 * 1 + 4 * 159 + 26535 + 8 = 27182 3 / 1 + 4 * 159 + 26535 + 8 = 27182 3 * 14 * 15 + 9 + 26535 + 8 = 27182 3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182
我的目标是从说开始
{"3"}
then
{"31", "3+1", "3-1", "3*1" "3/1"}
then
{"314", "31+4", "3+1+4", "3-1-4", "31/4", "31*4", "31-4"} etc.
然后每次查看列表中的每个值,看看它是否为目标值。如果是,则将该字符串添加到结果列表中
这是我的密码
public static List<String> combinations(String nums, int target)
{
List<String> tempResultList = new ArrayList<String>();
List<String> realResultList = new ArrayList<String>();
String originalNum = Character.toString(nums.charAt(0));
for (int i = 0; i < nums.length(); i++)
{
if (i > 0)
{
originalNum += nums.charAt(i); //start off with a new number to decompose
}
tempResultList.add(originalNum);
char[] originalNumCharArray = originalNum.toCharArray();
for (int j = 0; j < originalNumCharArray.length; j++)
{
//go through every character to find the combinations?
// maybe recursion here instead of iterative would be easier...
}
for (String s : tempResultList)
{
//try to evaluate
int temp = 0;
if (s.contains("*") || s.contains("/") || s.contains("+") || s.contains("-"))
{
//evaluate expression
} else {
//just a number
}
if (temp == target)
{
realResultList.add(s);
}
}
tempResultList.clear();
}
return realResultList;
}
有人能帮我解决这个问题吗?正在寻找包含编码的答案,因为我需要帮助生成可能性
共 (0) 个答案