一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1175|回复: 18
收起左侧

[算法题] 请教这道Bloomberg的高频题怎么做

[复制链接] |试试Instant~ |关注本帖
阿色 发表于 2015-12-13 03:09:22 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
数字游戏 给一个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);
    }

我这么做总是生成相同的结果,不知道错在哪里。请大神指教!
 楼主| 阿色 发表于 2015-12-13 03:52:19 | 显示全部楼层
刚发出来就解决了……

    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));
        }
    }
回复 支持 反对

使用道具 举报

ryb 发表于 2015-12-13 04:08:42 | 显示全部楼层
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);
        }
    }
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-12-13 09:36:37 | 显示全部楼层
占楼问问···楼主最近也是要面BB吗?BB还有一道高频提是reverse double,楼主会做吗
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2015-12-13 09:51:34 | 显示全部楼层
JamesJi 发表于 2015-12-13 09:36
占楼问问···楼主最近也是要面BB吗?BB还有一道高频提是reverse double,楼主会做吗

楼主能描述一下Reverse Double是啥吗?完全没概念。
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-12-13 10:32:29 | 显示全部楼层
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. }
复制代码
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2015-12-13 10:47:23 | 显示全部楼层
为什么不是直接
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;
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-12-13 11:12:55 | 显示全部楼层
yucheyang2 发表于 2015-12-12 21:47
为什么不是直接
boolean isNegative = num < 0.0 : true ? false;

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

使用道具 举报

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

能给个Test Case吗。。。
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-12-13 11:22:28 | 显示全部楼层
yucheyang2 发表于 2015-12-12 22:16
能给个Test Case吗。。。

input 23.345  output  543.32
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2015-12-13 11:30:57 | 显示全部楼层
JamesJi 发表于 2015-12-13 11:22
input 23.345  output  543.32

放IDE之后,我瞬间秒懂了。。。split是输入正则表达式。。。一个.在正则表达式里代表任何字符。。。改成                String[] res = s.split("\\.");
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-12-13 11:39:36 | 显示全部楼层
yucheyang2 发表于 2015-12-12 22:30
放IDE之后,我瞬间秒懂了。。。split是输入正则表达式。。。一个.在正则表达式里代表任何字符。。。改成         ...

你一说我也秒懂了可是我完全没意识到这个···唉··好像lc有个题也是这样子要加转义符····完全没这意识
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-12-13 11:41:51 | 显示全部楼层
yucheyang2 发表于 2015-12-12 22:30
放IDE之后,我瞬间秒懂了。。。split是输入正则表达式。。。一个.在正则表达式里代表任何字符。。。改成         ...

估计BB要你用reverse函数做也是想考察这方面知识吧··
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2015-12-13 11:42:17 | 显示全部楼层
JamesJi 发表于 2015-12-13 11:39
你一说我也秒懂了可是我完全没意识到这个···唉··好像lc有个题也是这样子要加转义符··· ...

哈哈,正常的,我也经常忘记这个。
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2015-12-13 11:43:32 | 显示全部楼层
JamesJi 发表于 2015-12-13 11:41
估计BB要你用reverse函数做也是想考察这方面知识吧··

那就危险了。。。。。。你几号Onsite?翻了一下最近面经都要绝望了。。。Intern的直接没Opening了。。。
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-12-13 11:44:28 | 显示全部楼层
yucheyang2 发表于 2015-12-12 22:43
那就危险了。。。。。。你几号Onsite?翻了一下最近面经都要绝望了。。。Intern的直接 ...

我还没onsite··下周电面而已哈哈···还有这个可以不需要split,可以Math.floor()取整数部分
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2015-12-13 11:52:39 | 显示全部楼层
JamesJi 发表于 2015-12-13 11:44
我还没onsite··下周电面而已哈哈···还有这个可以不需要split,可以Math.floor()取整数部分

Soga。。。楼主加油
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-12-13 12:04:57 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
  1. import java.util.ArrayList;
  2. import java.util.HashSet;

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 19:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表