近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3988|回复: 35
收起左侧

Yahoo电面

[复制链接] |试试Instant~ |关注本帖
hkc593 发表于 2016-7-2 11:55:53 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 博士 全职@Yahoo - Other - HR筛选 |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
给一个array,都是正整数,没有重复,问是否存在一个subsequence其和等于target.例如:{1,2,5,6,10,12,17}, target=15. 应该返回true, 因为有{1,2,12}或{5,10}. 应该是跪了,实在没想出什么好的解
-google 1point3acres

评分

1

查看全部评分

本帖被以下淘专辑推荐:

frozencookie 发表于 2016-7-5 14:07:32 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
不是背包么...背包的大小是target,物品价值和重量相等,复杂度n*m
回复 支持 1 反对 0

使用道具 举报

lookbackinanger 发表于 2016-7-4 04:42:58 | 显示全部楼层
关注一亩三分地微博:
Warald
感觉是backpack问题啊
回复 支持 1 反对 0

使用道具 举报

waikai 发表于 2016-7-2 12:26:42 | 显示全部楼层
谢谢lz的面经。lz怎么做的啊,复杂度O(n^2)么?我也想不着好方法
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2016-7-2 13:09:00 | 显示全部楼层
这不是combination sum么?还是对复杂度有要求?
回复 支持 反对

使用道具 举报

glory007 发表于 2016-7-2 13:25:03 | 显示全部楼层
多谢分享啊!
回复 支持 反对

使用道具 举报

gxiverson_1 发表于 2016-7-2 13:50:20 | 显示全部楼层
waikai 发表于 2016-7-2 12:26
谢谢lz的面经。lz怎么做的啊,复杂度O(n^2)么?我也想不着好方法

O(n^2)显然搞不定吧,subset sum是NP-Complete的吧
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-7-2 14:04:11 | 显示全部楼层
难道不是连续的subarray么。。。。。
回复 支持 反对

使用道具 举报

gxiverson_1 发表于 2016-7-2 14:07:26 | 显示全部楼层
blackrose 发表于 2016-7-2 14:04
难道不是连续的subarray么。。。。。

楼主例子里的就不连续啊,连续的就简单了。。。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-7-2 14:11:44 | 显示全部楼层
gxiverson_1 发表于 2016-7-2 14:07
楼主例子里的就不连续啊,连续的就简单了。。。

不连续就是combination sum了。或者就是pick coins 的变形
回复 支持 反对

使用道具 举报

八和九生 发表于 2016-7-2 14:13:21 | 显示全部楼层
如果只是返回有没有,boolean的话。那么可以用recursive 吧,感觉类似google 的面试题:coins change
先排个序,然后判断-google 1point3acres
{1,2,5,6,10,12,17}, 有没有15
等同于{2,5,6,10,12,17}, 有没有14
{5,6,10,12,17}, 有没有12
{6,10,12,17}, 有没有7
返回上一层的false
{5,10,12,17}, 有没有6
返回上上一层的false
{5,6,10,12,17}, 有没有12.
返回true。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
backtracking
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

补充内容 (2016-7-2 14:38):
public static boolean hasTarget(ArrayList<Integer> list, int target){
                if(list.contains(target))
                        return true;
. from: 1point3acres.com/bbs
                for(int i=0; i<list.size();...
回复 支持 反对

使用道具 举报

waikai 发表于 2016-7-2 14:25:22 | 显示全部楼层
gxiverson_1 发表于 2016-7-2 13:50
O(n^2)显然搞不定吧,subset sum是NP-Complete的吧
. Waral 鍗氬鏈夋洿澶氭枃绔,
啊,我考虑错了。想说的是 0(m^2)   target = m
回复 支持 反对

使用道具 举报

八和九生 发表于 2016-7-2 14:36:47 | 显示全部楼层
写了段代码,拿eclipse跑了一下,感觉没问题。
.1point3acres缃
  1. public static boolean hasTarget(ArrayList<Integer> list, int target){
  2.                 if(list.contains(target))
  3.                         return true;
  4.                
  5.                         System.out.println(list.size() + " " + target);
  6.                 for(int i=0; i<list.size(); i++){
  7.                         if(list.indexOf(i) < target){. 1point3acres.com/bbs
  8.                                 int temp = list.get(i);
  9.                                 list.remove(i);
  10.                                 if(hasTarget(list, target - temp))
  11.                                         return true;
  12.                                 else
  13.                                 list.add(i, temp);
  14.                         }. visit 1point3acres.com for more.
  15.                 }
  16.                 return false;
  17.         }
复制代码

补充内容 (2016-7-2 14:37):
test的部分也粘贴进去了= = 不好意思
回复 支持 反对

使用道具 举报

waikai 发表于 2016-7-2 14:43:59 | 显示全部楼层
八和九生 发表于 2016-7-2 14:36
写了段代码,拿eclipse跑了一下,感觉没问题。

这样和dfs区别不大吧,还是2^m时间复杂度 m = target?不知道理解对了没
回复 支持 反对

使用道具 举报

八和九生 发表于 2016-7-2 14:46:37 | 显示全部楼层
waikai 发表于 2016-7-2 14:43
这样和dfs区别不大吧,还是2^m时间复杂度 m = target?不知道理解对了没

我认为应该是2^n 的时间复杂度。 n是数组的长度
回复 支持 反对

使用道具 举报

waikai 发表于 2016-7-2 14:48:19 | 显示全部楼层
八和九生 发表于 2016-7-2 14:46
我认为应该是2^n 的时间复杂度。 n是数组的长度

不用呀。比如【1,2,4,33,44,543,..., 23432】 求target 是 6,数组里大于6的就不用考虑了,所以说target^2

补充内容 (2016-7-2 15:18):
错了错了。我想说我写的应该是target^2
回复 支持 反对

使用道具 举报

八和九生 发表于 2016-7-2 14:51:46 | 显示全部楼层
waikai 发表于 2016-7-2 14:48
不用呀。比如【1,2,4,33,44,543,..., 23432】 求target 是 6,数组里大于6的就不用考虑了,所以说ta ...

你要是那么考虑的话,还有一种[1,2,3,4,5,6...100.] taget = 12345……
应该是C^n 的时间复杂度(我们假设N是小于target的所有数值吧= = )

N^2 或者 target^2肯定到不了啊…… 如果是N^2那是挺快的。backtracking是C^N, C的N次方
回复 支持 反对

使用道具 举报

waikai 发表于 2016-7-2 14:54:04 | 显示全部楼层
八和九生 发表于 2016-7-2 14:51
你要是那么考虑的话,还有一种[1,2,3,4,5,6...100.] taget = 12345…… . from: 1point3acres.com/bbs
应该是C^n 的时间复杂度(我们假 ...

好像有办法 target^2啊。你等我写下贴上讨论下
回复 支持 反对

使用道具 举报

八和九生 发表于 2016-7-2 14:56:50 | 显示全部楼层
waikai 发表于 2016-7-2 14:54
好像有办法 target^2啊。你等我写下贴上讨论下
. From 1point 3acres bbs
好的啊,你写好了私信我地址,我还不着急睡呢
回复 支持 反对

使用道具 举报

waikai 发表于 2016-7-2 15:02:57 | 显示全部楼层
八和九生 发表于 2016-7-2 14:56
好的啊,你写好了私信我地址,我还不着急睡呢
  1. import java.util.*;
  2. . 1point 3acres 璁哄潧
  3. class Test {. 1point3acres.com/bbs
  4.         public static void main(String[] args) {
  5.                 int[] num = {1,2,5,6,10,17};. from: 1point3acres.com/bbs
  6.                 int t = 4;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  7.                 Sooo r = new Sooo();
  8.                
  9.                 System.out.println(r.find(num, t));
  10.         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  11. }
  12. class Sooo {
    . visit 1point3acres.com for more.
  13.         public boolean find(int[] nums, int m) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  14.                 ArrayList<Integer> rec = new ArrayList<Integer>();
  15.                 Arrays.sort(nums);. 鍥磋鎴戜滑@1point 3 acres
  16.                 if (m == 0) return false; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  17.                 rec.add(0);
  18.                 for (int e : nums) {
  19.                         if (e > m) break; //O(m)
  20.                        
  21.                         ArrayList<Integer> tmp = new ArrayList<>();
  22.                         for (Integer prvRes : rec) {
  23.                                 int newRes = prvRes + e;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  24.                                 if (newRes > m || tmp.size() + rec.size() > m+1) break; //O(m+1). from: 1point3acres.com/bbs
  25.                                 if (!tmp.contains(newRes) && !rec.contains(newRes)) tmp.add(newRes); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  26.                         }
  27.                        
  28.                         //merge
  29.                         ArrayList<Integer> newList = new ArrayList<>();
  30.                         int a = 0; int b = 0;
  31.                         while (a < tmp.size() || b < rec.size()) {
  32.                                 int l1 = a < tmp.size() ? tmp.get(a): Integer.MAX_VALUE;
  33.                                 int l2 = b < rec.size() ? rec.get(b) : Integer.MAX_VALUE;
  34.                                 if (l1 < l2) {
  35.                                         newList.add(l1);
  36.                                         a++;. 1point 3acres 璁哄潧
  37.                                 }else {
  38.                                         newList.add(l2); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  39.                                         b++;
  40.                                 }
  41.                         } //O(m). visit 1point3acres.com for more.
  42.                         rec = newList;
  43.                 }
  44.                 return rec.contains(m);
  45.         }
  46. }
复制代码
回复 支持 反对

使用道具 举报

waikai 发表于 2016-7-2 15:10:02 | 显示全部楼层
八和九生 发表于 2016-7-2 14:56
好的啊,你写好了私信我地址,我还不着急睡呢

写完才发现,用booolean[m+1]会好很多。应该明白我的意思。就是不停的更新一个boolean[m+1]的数组,一直更新到nums里面的数 i > m为止,也就是更新最多m次。就是O(m(m+1))

补充内容 (2016-7-2 15:21):
更新最多 x = min(N, target) 次。。时间复杂度是就是O(x(m+1))。。。我这不考虑边界的习惯估计是好不了了。。。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-28 17:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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