请教这道Bloomberg的高频题怎么做

数字游戏 给一个list, list中有两个数. 过程中可以一直往list中加数进去(append在最后), 但必须一直遵守三个条件: 1. list中所有数均需大于0 2. list中所有数都必须为unique 3. 新加入的数必须为已存在list中的某两数的差

要做的事情是把所有可能的过程(一直加到没办法加入新的数字为止)都给打印或是回传

ex. [30, 5], 则最新加入的数只能为25, list变为[30, 5, 25] 继续, 只能再加入20, list成为[30, 5, 25, 20], 接着就有两种选择, 可以加10(30-20) 或是15(20-5). 于是会分出两个branch [30, 5, 25, 20, 10] 跟[30, 5, 25, 20, 15], 然后再把最后一个可能补上之后变成 [30, 5, 25, 20, 10, 15]跟[30, 5, 25, 20, 15, 10]


我的code如下：

    public static void main(String[] args) {       
        ArrayList<ArrayList<Integer>> results = genNums(30, 5);
       
        for (int i = 0; i < results.size(); i++) {
            ArrayList<Integer> result = results.get(i);
            String output = "";
            for (int j = 0; j < result.size(); j++) {
                if (j == 0) {
                    output = String.valueOf(result.get(j));
                } else {
                    output += ", " + String.valueOf(result.get(j));
                }
            }
            System.out.println(output);
        }
    }
   
    public static ArrayList<ArrayList<Integer>> genNums(int num1, int num2) {
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
       
        ArrayList<Integer> result = new ArrayList<Integer>();
        result.add(num1);
        result.add(num2);
       
        genNumsHelper(results, result, 2);
       
        return results;
    }
   
    public static void genNumsHelper(ArrayList<ArrayList<Integer>> results, ArrayList<Integer> result, int size) {
        for (int i = 0; i < size - 1; i++) {
            int diff = Math.abs(result.get(i) - result.get(size - 1));
            
            if (result.contains(diff)) {
                continue;
            }
            
            result.add(diff);
            genNumsHelper(results, result, size + 1);
//            result.remove(result.size() - 1);
        }
       
        results.add(result);
    }

我这么做总是生成相同的结果，不知道错在哪里。请大神指教！

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

1. import java.util.ArrayList;
   
2. import java.util.HashSet;
   
3. 
   
4. public class add {
   
5.         public static void main(String[] args) {
   
6.                 add a = new add();
   
7.                 int[] nums = {30,5};
   
8.                 int j = 0;
   
9.                 ArrayList<ArrayList<Integer>> res = a.find(nums);
   
10.                 for(int i = 0; i < res.size(); i++) {
    
11.                         for( j = 0; j < res.get(i).size(); j++) {
    
12.                                 System.out.print(res.get(i).get(j) + " ");
    
13.                         }
    
14.                         if(j == res.get(i).size()) {
    
15.                                 System.out.println("");
    
16.                         }
    
17.                 }
    
18.         }
    
19.         public ArrayList<ArrayList<Integer>> find(int[] nums) {
    
20.                 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    
21.                 if(nums == null || nums.length < 2) {
    
22.                         return res;
    
23.                 }
    
24.                 ArrayList<Integer> temp = new ArrayList<Integer>();
    
25.                 temp.add(nums[0]);
    
26.                 temp.add(nums[1]);
    
27.                 helper(res, temp);
    
28.                 return res;
    
29.         }
    
30.         private void helper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> temp) {
    
31.                 HashSet<Integer> set = new HashSet<Integer>();
    
32.                 for(int i = 0; i < temp.size(); i++) {
    
33.                         int candidate = Math.abs(temp.get(i) - temp.get(temp.size() - 1));
    
34.                         if(!temp.contains(candidate) && !set.contains(candidate)) {
    
35.                                 temp.add(candidate);
    
36.                                 set.add(candidate);
    
37.                                 helper(res, temp);
    
38.                                 temp.remove(temp.size() - 1);
    
39.                         }
    
40.                 }
    
41.                 if(set.size() == 0) {
    
42.                         res.add(new ArrayList<Integer>(temp));
    
43.                 }
    
44.         }
    
45. }

复制代码

public static ArrayList<ArrayList<Integer>> genNums(int num1, int num2) {
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();

        ArrayList<Integer> result = new ArrayList<Integer>();
        result.add(num1);
        result.add(num2);
        Queue<ArrayList<Integer>> queue = new LinkedList<>();
        queue.offer(result);
        genNumsHelper(results, queue);

        return results;
    }

    public static void genNumsHelper(ArrayList<ArrayList<Integer>> results, Queue<ArrayList<Integer>> queue) {
        while(queue.size() > 0) {
            boolean find = false;
            ArrayList<Integer> result = queue.poll();
            int size = result.size();
            Set<Integer> set = new HashSet<>(result);
            for (int i = 0; i < size - 1; i++) {
                int diff = Math.abs(result.get(i) - result.get(size - 1));
                if (set.contains(diff)) {
                    continue;
                } else {
                    find = true;
                }
                set.add(diff);
                result.add(diff);
                queue.offer(new ArrayList<Integer>(result));
                result.remove(result.size() - 1);
            }
            if (!find) results.add(new ArrayList<Integer>(result));
        }
    }


    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> results = genNums(50, 5);
        for (int i = 0; i < results.size(); i++) {
            ArrayList<Integer> result = results.get(i);
            String output = "";
            for (int j = 0; j < result.size(); j++) {
                if (j == 0) {
                    output = String.valueOf(result.get(j));
                } else {
                    output += ", " + String.valueOf(result.get(j));
                }
            }
            System.out.println(output);
        }
    }

刚发出来就解决了……

    public static void main(String[] args) {       
        ArrayList<ArrayList<Integer>> results = genNums(30, 5);
       
        for (int i = 0; i < results.size(); i++) {
            ArrayList<Integer> result = results.get(i);
            String output = "";
            for (int j = 0; j < result.size(); j++) {
                if (j == 0) {
                    output = String.valueOf(result.get(j));
                } else {
                    output += ", " + String.valueOf(result.get(j));
                }
            }
            System.out.println(output);
        }
    }
   
    public static ArrayList<ArrayList<Integer>> genNums(int num1, int num2) {
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();

        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(num1);
        list.add(num2);

        genNumsHelper(results, list);

        return results;
    }
   
    public static void genNumsHelper(ArrayList<ArrayList<Integer>> results, ArrayList<Integer> list) {
        int size = list.size();
        HashSet<Integer> candidates = new HashSet<Integer>();

        for (int i = 0; i < size - 1; i++) {
            int candidate = Math.abs(list.get(i) - list.get(size - 1));
            if ((!list.contains(candidate)) && (!candidates.contains(candidate))) {
                list.add(candidate);
                candidates.add(candidate);
               
                genNumsHelper(results, list);
                list.remove(list.size() - 1);
            }
        }

        if (candidates.size() == 0) {
            results.add(new ArrayList<Integer>(list));
        }
    }

占楼问问···楼主最近也是要面BB吗？BB还有一道高频提是reverse double，楼主会做吗

JamesJi 发表于 2015-12-13 09:36
占楼问问···楼主最近也是要面BB吗？BB还有一道高频提是reverse double，楼主会做吗

楼主能描述一下Reverse Double是啥吗？完全没概念。

yucheyang2 发表于 2015-12-12 20:51
楼主能描述一下Reverse Double是啥吗？完全没概念。

就是给你31.453，reverse后变为354.13，我写了一段代码可是就是没检测出来哪里有问题···

1. public class reverse {
   
2.         public String reverse(double nums) {
   
3.                 boolean isNeg = false;
   
4.                 if(nums < 0) {
   
5.                         isNeg = true;
   
6.                 }
   
7.                 if(num == 0) {
   
8.                         return 0.0;
   
9.                 }
   
10.                 nums = Math.abs(nums);
    
11.                 String s = nums + "";
    
12.                 String[] res = s.split(".");
    
13.                 int m = doReverse(Integer.valueOf(res[0]));
    
14.                 int n = doReverse(Integer.valueOf(res[1]));
    
15.                 StringBuffer sb = new StringBuffer();
    
16.                 if(isNeg) {
    
17.                         sb.append("-");
    
18.                 }
    
19.                 sb.append(n + "");
    
20.                 sb.append(".");
    
21.                 sb.append(m + "");
    
22.                 return sb.toString();
    
23.         }
    
24.         private int doReverse(int num) {
    
25.                 int res = 0;
    
26.                 while(num > 0) {
    
27.                         int digit = num % 10;
    
28.                         res = res * 10 + digit;
    
29.                         num /= 10;
    
30.                 }
    
31.                 return res;
    
32.         }
    
33.         public static void main(String[] args) {
    
34.                 reverse r = new reverse();
    
35.                 double m = 31.456;
    
36.                 System.out.println(r.reverse(m));
    
37.         }
    
38. }

复制代码

为什么不是直接
boolean isNegative = num < 0.0 : true ? false;

String str = String.valueOf(num).replace("-", "");

StringBuilder sb = new StringBuilder(str.length());
for (int i = str.length() - 1; i >= 0; i--) {
      sb.append(str.charAt(i));
}

double result = Double.parseDouble(sb.toString());
if (Double.isInfinite(result)) {
// write some processing code here.
}

return isNegative ? -result : result;

马上要面

yucheyang2 发表于 2015-12-12 21:47
为什么不是直接
boolean isNegative = num < 0.0 : true ? false;

BB有说不准直接这样倒序来，需要用到类似reverse函数，可是我单独监测reverse是对的，放在一起就报错··实在是很费解

JamesJi 发表于 2015-12-13 11:12
BB有说不准直接这样倒序来，需要用到类似reverse函数，可是我单独监测reverse是对的，放在一起就报错·· ...

能给个Test Case吗。。。