一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
指尖新闻
Offer多多
Salarytics
Learn
Who's Hiring?
疫情动态
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
12
返回列表 发新帖
楼主: 匿名
收起左侧

微软苏州4面挂经

[复制链接] |试试Instant~ |中国面试经验, 中国面经, 码农类general
我的人缘0
donnice 2020-6-2 11:00:23 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   92% (2871)
 
 
7% (223)    👎
mazrim-- 发表于 2020-6-2 09:32
关键是有负数,怎么背包?

知道最小的负数是多少就行,假设最小负数是x,则

[Java] 纯文本查看 复制代码
for(int i = 0; i < arr.length; i++)
    for(int j = x; j <= sum; j++) 
回复 微信

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (207)
 
 
4% (9)    👎
子轩不语 发表于 2020/06/01 20:21:53
combination sum ii? (答案里也有用dfs的)
是原题,但是combination sum ii求方案,这个问的只是可行性

补充内容 (2020-6-1 20:46):
啊,仔细一想就是combination sum ii啊,只写出来DFS也不至于是个挂点啊,不懂面试官是到了最后一轮应付一下还是有意刁难楼主,还是国内面试官默认candidates是刷过题见过原题的?
回复

使用道具 举报

我的人缘0
amgfan 2020-6-2 14:06:05 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (630)
 
 
5% (34)    👎
把所有数字和 target 加上 min(nums) 变成>=0

然后用 dp ?

dp[i][s]   代表 前 i 个数字 组成和为 s 的组合数量

dp[i][s]  = dp[i-1][s] + dp[i][s-n[i]]

感觉这样时空复杂度也不一定比 dfs 小吧
回复

使用道具 举报

我的人缘0
mazrim-- 2020-6-2 22:12:21 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
本帖最后由 mazrim-- 于 2020-6-2 22:24 编辑
matthew_z 发表于 2020-6-2 14:06
把所有数字和 target 加上 min(nums) 变成>=0

然后用 dp ?

你这是多重背包问题解法吧,如果只能使用一次不知解法对不对
public static int sum(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {. From 1point 3acres bbs
            for (int j = dp.length - 1; j >= nums; j--) {
                dp[j] += dp[j - nums];
            }
        }
        return dp[target];
    }

回复

使用道具 举报

我的人缘0
amgfan 2020-6-2 23:03:45 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (630)
 
 
5% (34)    👎
本帖最后由 matthew_z 于 2020-6-2 23:10 编辑
mazrim-- 发表于 2020-6-2 22:12
你这是多重背包问题解法吧,如果只能使用一次不知解法对不对
public static int sum(int[] nums, int ta ...

嗯是的  我递推式写错了 应该
[Python] 纯文本查看 复制代码
dp[i][s]  = dp[i-1][s] + dp[i-1][s-n]  
所以不用 i 的

回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (3)
 
 
0% (0)    👎
请问面的哪个组,有英文面试吗
回复

使用道具 举报

我的人缘0
limingli1991 2020-6-3 02:19:00 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (19)
 
 
0% (0)    👎
请问你人是在国内吗?
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
baihou 发表于 2020/06/03 00:29:15
请问面的哪个组,有英文面试吗
有自我介绍,和简单问答
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-7-12 15:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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