W**********2
发帖数: 30 | 1 求各位大侠指点一道G家题： 题目是给一组integer 问可否用加减乘除使结果等于某个
target。比如｛1，2，3，60，7｝，target＝48 结果是true 2*（60/3）+1+7=48. 这
题怎么做呢， 用DFS吗？怎么加括号呢？ 谢谢各位大大 | x*****c
发帖数: 21 | 2 好像lc上面有类似的题目。
要是我做基本思路是divide and conquer。把{1，2，3，60，7}分成两部分：{1}(+-*/
) {2,3,60,7}, {1,2}(+-*/){3,60,7}, {1,2,3}(+-*/){60,7}, {1,2,3,60}(+-*/){7}
，左右两边再继续分别往下分。最后相当于一个二叉树的post-order traversal。
要是说错了求拍砖。
【在 W**********2 的大作中提到】
: 求各位大侠指点一道G家题： 题目是给一组integer 问可否用加减乘除使结果等于某个
: target。比如｛1，2，3，60，7｝，target＝48 结果是true 2*（60/3）+1+7=48. 这
: 题怎么做呢， 用DFS吗？怎么加括号呢？ 谢谢各位大大
| r*******g
发帖数: 1335 | 3 24点游戏，不知道什么办法好，我在其它地方看到过一个思路：
1，每次选不同的两个数，求出他们的4种可能答案，把原来两个数删除，插入新的数到
后面
2，对新的N-1个数，重复步骤1。
所以这是个dfs。
这个做法貌似看起来会重复考虑很多东西，但是我真不知道怎么避免。这里面难点是，
假设你生成了A/B/C三个数所有的运算结果，我不知道怎么从这个结果生成A/B/C/D 4个
数的运算结果，中间可能依然很多重复的。 | c*****m
发帖数: 271 | 4 初看也以为是这个题，后来看数字顺序可变，感觉你楼下的解法靠谱
*/
【在 x*****c 的大作中提到】
: 好像lc上面有类似的题目。
: 要是我做基本思路是divide and conquer。把{1，2，3，60，7}分成两部分：{1}(+-*/
: ) {2,3,60,7}, {1,2}(+-*/){3,60,7}, {1,2,3}(+-*/){60,7}, {1,2,3,60}(+-*/){7}
: ，左右两边再继续分别往下分。最后相当于一个二叉树的post-order traversal。
: 要是说错了求拍砖。
| c*****m
发帖数: 271 | 5 当你生成了a/b/c三个数的运算结果之后，结果只是一个数啊，再和D组成两个数，算４
种可能的答案。可能我误解了你说的意思
【在 r*******g 的大作中提到】
: 24点游戏，不知道什么办法好，我在其它地方看到过一个思路：
: 1，每次选不同的两个数，求出他们的4种可能答案，把原来两个数删除，插入新的数到
: 后面
: 2，对新的N-1个数，重复步骤1。
: 所以这是个dfs。
: 这个做法貌似看起来会重复考虑很多东西，但是我真不知道怎么避免。这里面难点是，
: 假设你生成了A/B/C三个数所有的运算结果，我不知道怎么从这个结果生成A/B/C/D 4个
: 数的运算结果，中间可能依然很多重复的。
| h**k
发帖数: 3368 | 6 从a/b/c的所有运算结果再加d是不可能生成a/b/c/d所有运算结果的。
你还要加上从a/b/d的所有运算结果加c
a/c/d加上b，等等
【在 c*****m 的大作中提到】
: 当你生成了a/b/c三个数的运算结果之后，结果只是一个数啊，再和D组成两个数，算４
: 种可能的答案。可能我误解了你说的意思
| r*******g
发帖数: 1335 | 7 对的，所以不知道怎么通过cache来加快运算。
【在 h**k 的大作中提到】
: 从a/b/c的所有运算结果再加d是不可能生成a/b/c/d所有运算结果的。
: 你还要加上从a/b/d的所有运算结果加c
: a/c/d加上b，等等
| m******y
发帖数: 219 | 8 照着leetcode原题改的，这个case可以过，但是仅仅用curr_res == target来加入结果
感觉不够，必须要所有的数都visited。
public class Solution {
public static void main(String[] args) {
int[] nums = {1,2,3, 60, 7};
System.out.println(get(nums, 48));
}
public static List get(int[] nums, int target) {
List result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
boolean[] visited = new boolean[nums.length];
helper(nums, 0, 0, target, visited, "", result);
return result;
}
public static void helper(int[] nums, int prev_num, int curr_res,int
target, boolean[] visited, String path, List result) {
if (curr_res == target) {
result.add(new String(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (!visited[i]) {
visited[i] = true;
if (path.length() == 0) {
helper(nums, nums[i], nums[i], target, visited, path +
nums[i], result);
} else {
helper(nums, nums[i], curr_res + nums[i], target,
visited, path + "+" + nums[i], result);
helper(nums, -nums[i], curr_res - nums[i], target,
visited, path + "-" + nums[i], result);
helper(nums, prev_num * nums[i], curr_res - prev_num +
prev_num * nums[i], target, visited, path + "*" + nums[i], result);
helper(nums, prev_num / nums[i], curr_res - prev_num +
prev_num / nums[i],target, visited, path + "/" + nums[i], result);
}
visited[i] = false;
}
}
}
}
Output:[1+2*60/3+7, 1-2*3+60-7, 1-2*3-7+60, 1-3*2+60-7, 1-3*2-7+60, 1+60-2*3
-7, 1+60*2/3+7, 1+60-3*2-7, 1+60/3*2+7, 1+60-7-2*3, 1+60-7-3*2, 1*60-2-3-7,
1*60-2-7-3, 1*60-3-2-7, 1*60-3-7-2, 1*60-7-2-3, 1*60-7-3-2, 1*60/7*2*3, 1*60
/7*3*2, 1+7+2*60/3, 1+7+60*2/3, 1+7+60/3*2, 1-7-2*3+60, 1-7-3*2+60, 1-7+60-2
*3, 1-7+60-3*2, 2*60/3+1+7, 2*60/3+7+1, 3-1-2*7+60, 3-1+60-2*7, 3-1+60-7*2,
3-1-7*2+60, 3-2*7-1+60, 3-2*7+60-1, 3+60-1-2*7, 3+60-1-7*2, 3+60-2*7-1, 3+60
-7*2-1, 3-7*2-1+60, 3-7*2+60-1, 60+1-2*3-7, 60+1-3*2-7, 60+1-7-2*3, 60+1-7-3
*2, 60-1-2*7+3, 60-1*2-3-7, 60-1*2-7-3, 60-1+3-2*7, 60-1+3-7*2, 60-1*3-2-7,
60-1*3-7-2, 60-1-7*2+3, 60-1*7-2-3, 60-1*7-3-2, 60*1-2-3-7, 60*1-2-7-3, 60*1
-3-2-7, 60*1-3-7-2, 60*1-7-2-3, 60*1-7-3-2, 60*1/7*2*3, 60*1/7*3*2, 60/1-2-3
-7, 60/1-2-7-3, 60/1-3-2-7, 60/1-3-7-2, 60/1-7-2-3, 60/1-7-3-2, 60/1/7*2*3,
60/1/7*3*2, 60-2-1*3-7, 60-2-1*7-3, 60-2*1-3-7, 60-2*1-7-3, 60-2/1-3-7, 60-2
/1-7-3, 60-2-3-1*7, 60-2-3*1-7, 60-2-3/1-7, 60-2-3-7, 60-2*3+1-7, 60-2*3-7+1
, 60-2-7-1*3, 60-2-7*1-3, 60-2-7/1-3, 60-2-7-3, 60-2*7-1+3, 60-2*7+3-1, 60*2
/3+1+7, 60*2/3+7+1, 60+3-1-2*7, 60+3-1-7*2, 60+3-2*7-1, 60+3-7*2-1, 60-3-1*2
-7, 60-3-1*7-2, 60-3*1-2-7, 60-3*1-7-2, 60-3/1-2-7, 60-3/1-7-2, 60-3-2-1*7,
60-3-2*1-7, 60-3-2/1-7, 60-3-2-7, 60-3*2+1-7, 60-3*2-7+1, 60-3-7-1*2, 60-3-7
*1-2, 60-3-7/1-2, 60-3-7-2, 60/3*2+1+7, 60/3*2+7+1, 60-7+1-2*3, 60-7+1-3*2,
60-7-1*2-3, 60-7-1*3-2, 60-7*1-2-3, 60-7*1-3-2, 60-7/1-2-3, 60-7/1-3-2, 60-7
-2-1*3, 60-7-2*1-3, 60-7-2/1-3, 60-7-2-3, 60-7-2*3+1, 60-7*2-1+3, 60-7*2+3-1
, 60-7-3-1*2, 60-7-3*1-2, 60-7-3/1-2, 60-7-3-2, 60-7-3*2+1, 60/7*1*2*3, 60/7
*1*3*2, 60/7/1*2*3, 60/7/1*3*2, 60/7*2*1*3, 60/7*2/1*3, 60/7*2*3, 60/7*3*1*2
, 60/7*3/1*2, 60/7*3*2, 7+1+2*60/3, 7+1+60*2/3, 7+1+60/3*2, 7+2*60/3+1, 7+60
*2/3+1, 7+60/3*2+1] | r*******g
发帖数: 1335 | 9 lc哪道原题？
【在 m******y 的大作中提到】
: 照着leetcode原题改的，这个case可以过，但是仅仅用curr_res == target来加入结果
: 感觉不够，必须要所有的数都visited。
: public class Solution {
: public static void main(String[] args) {
: int[] nums = {1,2,3, 60, 7};
: System.out.println(get(nums, 48));
: }
: public static List get(int[] nums, int target) {
: List result = new ArrayList<>();
: if (nums == null || nums.length == 0) return result;
| p**r
发帖数: 5853 | 10 西瓜，俺感觉不用加括号啊2*60/3+1+7=48
俺比较笨，俺觉得就是暴力法遍历+approach
List nums
List operators
这个两个list之间的遍历
优化可以考虑nums先sort
然后用乘先比较target，再用+接近，或者/大幅减小，或-接近，
考虑有0的情况，和正负的情况。
说错请各位拍砖。
【在 W**********2 的大作中提到】
: 求各位大侠指点一道G家题： 题目是给一组integer 问可否用加减乘除使结果等于某个
: target。比如｛1，2，3，60，7｝，target＝48 结果是true 2*（60/3）+1+7=48. 这
: 题怎么做呢， 用DFS吗？怎么加括号呢？ 谢谢各位大大
| I******c
发帖数: 163 | 11 leetcode上类似的题目是
241. Different Ways to Add Parentheses
leetcode这道题是要求出所有可能的答案。我当时的解法就是recursive. 在不同的地
方把整数分成两半，然后递归求这两半整数所有可能的值，然后就汇总。
现在对于google这道题，我的理解是数组顺序也是固定的（从给定的例子），我们可以
使用类似的办法，找出表达式可能的结果，看给定的target在不在里面就可以。 | I*******g
发帖数: 7600 | 12 using dynamic programming (cache):
public class Operations
{
static class OperationFormula
{
public int value;
public String formula;
public OperationFormula(int x, String y){
value = x;
formula = y;
}
}
static Map, HashSet> map = new
HashMap,HashSet>();
public static void main( String[] args )
{
int target = 48;
Integer[] item = new Integer[]{1, 2, 3, 60, 7};
HashSet data = new HashSet(Arrays.asList(item));
HashSet out = processDataSet(data);
for(OperationFormula op: out){
if (op.value == target){
System.out.println(op.formula);
}
}
}
public static HashSet processDataSet(HashSet
dataSet){
HashSet out = new HashSet();
if (map.containsKey(dataSet))
out = map.get(dataSet);
else{
if(dataSet.size() == 2){
Iterator it = dataSet.iterator();
int x = it.next(); int y = it.next();
out.add(new OperationFormula(x+y, x + "+" + y));
out.add(new OperationFormula(x*y, x + "*" + y));
out.add(new OperationFormula(x-y, x + "-" + y));
out.add(new OperationFormula(y-x, y + "-" + x));
if(y != 0)
out.add(new OperationFormula(x/y, x + "/" + y));
if(x != 0)
out.add(new OperationFormula(y/x, y + "/" + x));
}
else{
for(int i:dataSet){
HashSet newSet = new HashSet(dataSet);
newSet.remove(i);
HashSet temp = processDataSet(newSet);
for(OperationFormula op: temp){
out.add(new OperationFormula(i + op.value, i + "+" +
op.formula )) ;
out.add(new OperationFormula(i * op.value, i + "*(" +
op.formula + ")")) ;
out.add(new OperationFormula(i - op.value, i + "-(" +
op.formula + ")")) ;
out.add(new OperationFormula(op.value - i, op.formula
+ "-" + i )) ;
if(op.value != 0)
out.add(new OperationFormula(i / op.value, i + "/
(" + op.formula + ")")) ;
if(i != 0)
out.add(new OperationFormula(op.value / i, "(" +
op.formula + ")/" + i + "")) ;
}
}
}
map.put(dataSet, out);
}
return out;
}
}
【在 W**********2 的大作中提到】
: 求各位大侠指点一道G家题： 题目是给一组integer 问可否用加减乘除使结果等于某个
: target。比如｛1，2，3，60，7｝，target＝48 结果是true 2*（60/3）+1+7=48. 这
: 题怎么做呢， 用DFS吗？怎么加括号呢？ 谢谢各位大大
| h*********6
发帖数: 7 | |
|
