📣 VIP通行证夏日特惠 限时立减$68
楼主: flex
跳转到指定楼层
上一主题 下一主题
收起左侧

Bloomberg 新鲜面经

🔗
何打发123 2016-8-14 09:31:05 | 只看该作者
全局:
xihaokai1 发表于 2016-8-4 00:24
compute a[1...27] such that a is the list of numbers 100-999 whose digit sum equals i; concatenate e ...

大神 没太看懂 能仔细说说嘛?
回复

使用道具 举报

🔗
 楼主| flex 2016-8-14 22:29:23 | 只看该作者
全局:
何打发123 发表于 2016-8-14 09:31
大神 没太看懂 能仔细说说嘛?

思路是这样的:
遍历一遍100到999的数字,对每个数字分别求三位数的和,比如100的和就是1,101的和是2,999的和是27,将这些结果放入一个表里面:
1:100
2:101,110
3:111
...
26: 998, 989, 899
27: 999
然后遍历表的每一行,对每一行中的每一个元素进行组合,比如行26,就会有这样的组合998-989, 998-899, 989-899,把结果都放到一个vector里面最后return。
回复

使用道具 举报

🔗
何打发123 2016-8-14 23:39:21 | 只看该作者
全局:
flex 发表于 2016-8-14 22:29
思路是这样的:
遍历一遍100到999的数字,对每个数字分别求三位数的和,比如100的和就是1,101的和是2, ...

机智!!  如果有n位的话 9^n 个数字分类 然后再对前面的9^n配对 这里是o(1)? 然后整体复杂度就是9^n 这样分析对吗~
回复

使用道具 举报

🔗
 楼主| flex 2016-8-14 23:54:34 | 只看该作者
全局:
何打发123 发表于 2016-8-14 23:39
机智!!  如果有n位的话 9^n 个数字分类 然后再对前面的9^n配对 这里是o(1)? 然后整体复杂 ...

如果题目是n位的话,要求前n/2个数字和与后n/2个数字和相等,那么遍历一半的复杂度就是n/2 * 10^(n/2),然后总共有n/2 * 10个entry,假设每个entry最多会有m个元素(理论上m会很小),则整体复杂度为O(n / 2 * 10^(n/2) * n/2 * 10 * m ^2),当n = 6的case:3*1000*30*m^2,小于暴力解法 (999999-100000) * 6
这道题有一个tricky的地方就是组合的时候,前半部的数字不能以0开头。
回复

使用道具 举报

🔗
何打发123 2016-8-15 00:36:18 | 只看该作者
全局:
写了一个 求斧正~~~

  1. //把1 ~999分成27组
  2.         public void print3(){
  3.                 HashMap<Integer, ArrayList<String>> map = new HashMap<Integer, ArrayList<String>>();
  4.                 for(int i = 1; i <= 999; i++){
  5.                         int sum = getSum(i);
  6.                         ArrayList<String> arr = map.get(sum);
  7.                         if(arr == null){
  8.                                 arr = new ArrayList<String>();
  9.                                 map.put(sum, arr);
  10.                         }
  11.                        
  12.                         String cur = i + "";
  13.                         //统一往前加0 否则前后都加有重复
  14.                         while(cur.length() < 3){
  15.                                 cur = '0' + cur;
  16.                         }
  17.                         arr.add(cur);
  18.                 }
  19.                
  20.                 int m = 0;
  21.                 for(int i = 100; i <= 999; i++){
  22.                         int sum = getSum(i);
  23.                         ArrayList<String> list = map.get(sum);
  24.                         for(String str : list){
  25.                                 String temp = i + str;
  26.                                 m++;
  27.                                 System.out.println(m + "  " + temp);
  28.                                
  29.                         }
  30.                 }
  31.         }

  32. private int getSum(int k){
  33.                 int sum = 0;
  34.                 while(k > 0){
  35.                         sum = sum + k%10;
  36.                         k = k/10;
  37.                 }
  38.                 return sum;
  39.         }
复制代码
回复

使用道具 举报

🔗
 楼主| flex 2016-8-15 01:21:29 | 只看该作者
全局:
何打发123 发表于 2016-8-15 00:36
写了一个 求斧正~~~

第二段的逻辑会遍历100到999并重复计算getSum,遍历HashMap应该会更好些,因为总共27个Entry,每个Entry也就几个做全排列,复杂度会好一些。我写了一个版本,和暴力法的结果验证一致,供50412种情况:
  1. int getSum(int num) {
  2.     int sum = 0;
  3.     while (num != 0) {
  4.         sum += num % 10;
  5.         num = num / 10;
  6.     }
  7.     return sum;
  8. }

  9. vector<int> getNum() {
  10.     vector<int> result;
  11.     unordered_map<int, vector<int>> parts;
  12.     for (int i = 1 ; i <= 999; i++) {
  13.         int sum = getSum(i);
  14.         parts[sum].push_back(i);
  15.     }
  16.    
  17.     // 遍历Hash表
  18.     for (auto entry : parts) {
  19.         vector<int>& elements = entry.second;
  20.         // 得到Entry中一对元素的全排列
  21.         for (int i = 0; i < elements.size(); i++) {
  22.             for (int j = 0; j < elements.size(); j++) {
  23.                 int num = elements[i] * 1000 + elements[j];
  24.                
  25.                 // 去除0开头的数字
  26.                 if (num >= 100000) {
  27.                     result.push_back(num);
  28.                 }
  29.             }
  30.         }
  31.     }
  32.    
  33.     return result;
  34. }
复制代码
回复

使用道具 举报

🔗
cicean 2016-9-13 03:03:47 | 只看该作者
全局:
flex 发表于 2016-8-14 22:29
思路是这样的:
遍历一遍100到999的数字,对每个数字分别求三位数的和,比如100的和就是1,101的和是2, ...

感觉是不是可以bucket select 啊?
List<Integer>[]

这题好难啊。。。怎么这么难,45分钟写一道就差不多了。
回复

使用道具 举报

🔗
cicean 2016-9-13 03:58:19 | 只看该作者
全局:
flex 发表于 2016-8-14 22:29
思路是这样的:
遍历一遍100到999的数字,对每个数字分别求三位数的和,比如100的和就是1,101的和是2, ...

100010 这个种情况怎么办呢?
回复

使用道具 举报

🔗
 楼主| flex 2016-9-13 15:27:37 | 只看该作者
全局:
cicean 发表于 2016-9-13 03:58
100010 这个种情况怎么办呢?

恩,不好意思之前有笔误,应该遍历1到999的数字,具体实现请看我之前贴的程序。
没有想到这个最优解不用担心,我当时就是暴力解,也闯到Onsite拿到Offer了。毕竟电话面试还有其他的题目,这道题的最优解算是Bonus吧。
回复

使用道具 举报

🔗
freeaccount 2016-12-25 13:31:55 | 只看该作者
全局:
三位和最小是1,最大是27。

当三位和为1时,有三种情况100100 100010 100001

如果给出一个三位和为n的数,如果 n < 27,则可以生成9个三位和为n+1的数,就是把这个数加上: 100100 100010 100001 10100 10010 10001 1100 1010 1001

生成过程中会有重复,用set去重

目测是对的,没细想。。。但不知道这样会快么?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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