一亩三分地论坛

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

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

早上的脸书店面

[复制链接] |试试Instant~ |关注本帖
weii 发表于 2016-11-12 06:44:33 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 硕士 全职@Facebook - 内推 -  |Otherfresh grad应届毕业生

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

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

x
题目是给一些input 一个target,所有input加起来为target的去重combination个数
如[2, 3], 目标是5,可能的组合只有(2,3) 返回1

经验就是别紧张,想叉了就返回去想,我一开始说用backtracking 然后可以优化为dp 面试官说要去重 然后就卡住了……在面试官提示下才改为backtracking …最后写完没时间了TAT 面试官说没时间问第二题了,你来问问题吧

面试官是美国人,很 nice的,从头到尾一直说cool cool,感觉他也很紧张,讲话也会说一半卡住…最后没时间了我说不好意思太紧张了一开始卡住了 他说没事没事一题就够了,做出来以后也没问复杂度啊优化之类的问题(其实还可以memorized一下)希望不是安慰我……TAT

补充内容 (2016-11-12 09:17):
补充一下,这题和LC 40 combination II的差别的是,LC40里array数字是可以重复的,然而每个数字可以只能用一次;我这里array的数字是没有重复的,在结果里可以用多次……求大米求bless~. Waral 鍗氬鏈夋洿澶氭枃绔,

补充内容 (2016-11-13 04:06):.鐣欏璁哄潧-涓浜-涓夊垎鍦
在大家提醒下发现,其实是combination 4的去重版啦

评分

3

查看全部评分

Roisterer 发表于 2016-11-14 09:04:02 | 显示全部楼层

out put 7
回复 支持 1 反对 0

使用道具 举报

Roisterer 发表于 2016-11-13 01:00:53 | 显示全部楼层

那感觉像是个背包问题, 这样不知道对不对.

public static int combination(int[] nums, int T) {
        if (nums == null || nums.length == 0)
            return 0;
        int[] dp = new int[T + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = nums; j <= T; j++) {
                dp[j] += dp[j - nums];. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            }
        }
        return dp[T];
    }

补充内容 (2016-11-13 01:02):. 1point 3acres 璁哄潧
手残..
for (int j = nums; j <= T; j++) {.1point3acres缃
                dp[j] += dp[j - nums];
            }
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-11-12 06:59:29 | 显示全部楼层
如果要求不去重的话(1,2,3)和(3,2,1)都算,应该就是LC上的combination sum IV了
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-12 06:59:38 | 显示全部楼层
是不是就是combination sum呀? LC39 LC40?

补充内容 (2016-11-12 07:05):
错了..比较像combination sum IV... 但如果要去重貌似不能memoization? 是不是要用类似subsets II 的方法做去重?
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-12 07:02:37 | 显示全部楼层
话说input array里的数字能被重复使用吗?
回复 支持 反对

使用道具 举报

 楼主| weii 发表于 2016-11-12 07:10:51 | 显示全部楼层
wtcupup 发表于 2016-11-12 07:02
话说input array里的数字能被重复使用吗?
. visit 1point3acres.com for more.
可以 也就是弄个backtraking 有一个start index
回复 支持 反对

使用道具 举报

 楼主| weii 发表于 2016-11-12 07:11:43 | 显示全部楼层
catinclay 发表于 2016-11-12 06:59
是不是就是combination sum呀? LC39 LC40?

补充内容 (2016-11-12 07:05):

喔 对的 你说的有道理 因为和组合里开始的数大小有关
回复 支持 反对

使用道具 举报

 楼主| weii 发表于 2016-11-12 07:12:23 | 显示全部楼层
wtcupup 发表于 2016-11-12 06:59
如果要求不去重的话(1,2,3)和(3,2,1)都算,应该就是LC上的combination sum IV了
.鏈枃鍘熷垱鑷1point3acres璁哄潧
只算一个
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-12 07:16:30 | 显示全部楼层

恩,那应该就是combination sum I 加一个global counter 计数一下有几个组合就行
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-12 08:15:21 | 显示全部楼层
weii 发表于 2016-11-12 07:11
喔 对的 你说的有道理 因为和组合里开始的数大小有关

好像就是combination sum II ? 除了返回的是數量而不是組合
回复 支持 反对

使用道具 举报

Onedayw 发表于 2016-11-12 08:24:35 | 显示全部楼层
请问楼主什么时候推的啊
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-12 08:39:05 | 显示全部楼层
每一个input可以重复使用么?
回复 支持 反对

使用道具 举报

 楼主| weii 发表于 2016-11-12 08:52:03 | 显示全部楼层
catinclay 发表于 2016-11-12 08:15
好像就是combination sum II ? 除了返回的是數量而不是組合

对的!哎我真是脑子糊住了这么简单的来回折腾
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-12 08:53:42 | 显示全部楼层
weii 发表于 2016-11-12 08:52
对的!哎我真是脑子糊住了这么简单的来回折腾
. From 1point 3acres bbs
combination sum ii 是原数字只能用1次,你的题也是么?
回复 支持 反对

使用道具 举报

 楼主| weii 发表于 2016-11-12 09:16:11 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-11-12 08:53
combination sum ii 是原数字只能用1次,你的题也是么?

不是的 差的点是,combination sum ii里的数字是可以重复的,结果是数字只能用一次;我的这个是array里数字是不重复的,但是可以用多次 我等等补充一下
回复 支持 反对

使用道具 举报

Roisterer 发表于 2016-11-12 09:28:32 | 显示全部楼层
请问下楼主 数组里的数字会有重复嘛? 比如[1,2,2,3] 这种的
回复 支持 反对

使用道具 举报

 楼主| weii 发表于 2016-11-12 09:58:21 | 显示全部楼层
Roisterer 发表于 2016-11-12 09:28
请问下楼主 数组里的数字会有重复嘛? 比如[1,2,2,3] 这种的

没有重复的~
回复 支持 反对

使用道具 举报

jiangyntz 发表于 2016-11-12 17:44:42 | 显示全部楼层

看了下,好像就是combination sum I的DP解法?只要注意下内外重循环的顺序就可以去重了
回复 支持 反对

使用道具 举报

hello2pig 发表于 2016-11-12 22:45:41 | 显示全部楼层
楼主能说说和Combination Sum IV有什么区别么?
回复 支持 反对

使用道具 举报

hello2pig 发表于 2016-11-13 01:51:40 | 显示全部楼层
Roisterer 发表于 2016-11-13 01:00
那感觉像是个背包问题, 这样不知道对不对.. from: 1point3acres.com/bbs

public static int combination(int[] nums, int T) {

这不就是Combination Sum IV?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 22:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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