Java 使用数字列表和算术运算获取目标数字

给定一个数字列表和一个目标数字，编写一个程序来确定是否可以通过对数字列表应用“+-*/”运算来计算目标数字？你可以假设 () 会在必要时自动添加。应在每两个连续数字之间放置一个运算符。所以每个数字都必须使用。

例如，给定 {1,2,3,4} 和 21，返回 true。因为 (1+2)*(3+4)=21

Java解决方案

这是一个分区问题，可以通过使用深度优先搜索来解决。

public boolean isReachable(ArrayList<Integer> list, int target) {
    if (list == null || list.size() == 0)
        return false;
 
    int i = 0;
    int j = list.size() - 1;
 
    ArrayList<Integer> results = getResults(list, i, j);
 
    for (int num : results) {
        if (num == target) {
            return true;
        }
    }
 
    return false;
}
 
public ArrayList<Integer> getResults(ArrayList<Integer> list,
                                            int left, int right) {
    ArrayList<Integer> result = new ArrayList<Integer>();
 
    if (left > right) {
        return result;
    } else if (left == right) {
        result.add(list.get(left));
        return result;
    }
 
    for (int i = left; i < right; i++) {
 
        ArrayList<Integer> result1 = getResults(list, left, i);
        ArrayList<Integer> result2 = getResults(list, i + 1, right);
 
        for (int x : result1) {
            for (int y : result2) {
                result.add(x + y);
                result.add(x - y);
                result.add(x * y);
                if (y != 0)
                    result.add(x / y);
            }
        }
    }
 
    return result;
}

以上就是关于Java 使用数字列表和算术运算获取目标数字的全部内容，感谢各位的阅读。