40天從 V:147 -> V:154

一亩三分地

 找回密码 注册账号

扫描二维码登录本站

最近看过此主题的会员


码农求职神器Triplebyte
不用海投
内推多家公司面试

Total Comp Calculator
输入offer信息
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code: 20%off 打八折

深入浅出AB Test
从入门到精通
coupon code: 20%off 打八折
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 2043|回复: 30
收起左侧

[高频题] 4.26Amazon视频面试:coin change的变种

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
BubbleFan 发表于 2019-4-27 11:05:23 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (39)
 
 
0% (0)    👎

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
本帖最后由 14417335 于 2019-4-27 18:28 编辑

4.26 Amazon 视频面试第一轮coding

游客,本帖隐藏的内容需要积分高于 150 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

评分

参与人数 5大米 +24 收起 理由
Ayukikiki_13 + 1 赞一个
RonHe + 1 很有用的信息!
剑随风飘 + 1 给你点个赞!
EdsgerW + 1 等我积分够了在看!
14417335 + 20

查看全部评分


上一篇:求问刷题使用的语言有限制嘛??
下一篇:为啥大家经常说Leetcode 400题?

本帖被以下淘专辑推荐:

  • · Amazon|主题: 31, 订阅: 4
我的人缘0
tinlittle 发表于 2019-4-29 08:09:42 | 显示全部楼层
本楼: 👍   60% (3)
 
 
40% (2)   👎
全局: 👍   98% (1748)
 
 
1% (31)    👎
这题在322的解之上再加一层每一枚coin的总数的循环就好了,因为coin数不是无限的,哪个针对amount的循环要倒过来。想不出是因为刷题没有精刷,不能举一反三。
游客,本帖隐藏的内容需要积分高于 150 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

评分

参与人数 3大米 +33 收起 理由
admin + 30
Neroldy + 1 很有用的信息!
ianianda + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0
tinlittle 发表于 2019-5-5 02:39:15 | 显示全部楼层
本楼: 👍   0% (0)
 
 
100% (2)   👎
全局: 👍   98% (1748)
 
 
1% (31)    👎
chenyijia055 发表于 2019-5-4 00:42
没看懂 你这里为什么是 dp = min(dp, num + dp) 而不是 dp = min(dp, j + dp)
还有这里是 for i in reve ...

没看懂你为什么认为我该按你的思路写代码。

你要是有测试样例证明我的代码有错,敬请分享。
你要是一眼看出什么逻辑错误,请指正。
你要是看出我的代码和你熟知的模版不同,想知道它们的异同,也得给出链接吧?

和那个声称greedy的一样(不认为有greedy解),要准备面试的话,不能光说不练,show me your code。
回复

使用道具 举报

我的人缘0
mc2 发表于 2019-5-23 09:49:56 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (128)
 
 
0% (0)    👎
请叫我热情老八 发表于 2019-5-22 13:18
非常感谢仁兄的分享!

1. 0 那里我猜想如果换成 sys.maximum 会更加 make sense, 当然,不换也是非常 ...

Dijkstra其实比较简单。老兄去tube查查很多讲解。在这个题目的关键就是用PriorityQueue,哪个amount更大就先处理哪个。虽然排序耗费时间但是确是一个时间和空间总体的良好折中方案。当然用Queue BFS也可以,不过空间耗费可能会大一些。
回复

使用道具 举报

我的人缘0
你的鱼跑了 发表于 2019-5-16 03:08:43 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   81% (304)
 
 
18% (70)    👎
chenyijia055 发表于 2019-5-5 14:45
你的代码漏洞百出,整个逻辑都是错误的。另外,你的test cases写得也是烂的不行,自己去拿这些test cases ...

看着回溯的dfs
好似夕阳下的奔跑
那是我逝去的青春
awsl
回复

使用道具 举报

我的人缘0
chenyijia055 发表于 2019-5-5 14:45:34 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
tinlittle 发表于 2019-5-5 02:39
没看懂你为什么认为我该按你的思路写代码。

你要是有测试样例证明我的代码有错,敬请分享。

你的代码漏洞百出,整个逻辑都是错误的。另外,你的test cases写得也是烂的不行,自己去拿这些test cases好好想想你为什么错,( [1, 6, 7], [5, 2, 1], 13),  ([1, 2, 5], [3, 3, 1], 12), ([1, 2, 5], [3, 3, 1], 13), ([1, 2, 5], [3, 3, 1], 1), 第一次没想直接给你指出来,你还来劲了。

下面是我的code.
class Solution:
    def coin_change(self, coins, nums, amount):
      self.res= float('inf')
      d  = {c:n for c, n in zip(coins, nums)}
      def dfs(curr, count):
        if curr == amount:
          self.res = min(self.res, count)
          return
        for nxt in d:
          if nxt +curr <= amount and d[nxt] >= 1:
            d[nxt] -= 1
            dfs(curr+nxt, count+1)
            d[nxt] += 1
      dfs(0, 0)
      return self.res if self.res != float('inf') else -1


补充内容 (2019-5-5 14:55):
[1, 6, 7], [5, 2, 1], 1 再多送你一个简单的,你就懂为什么这么问了。
回复

使用道具 举报

我的人缘0
孙行者 发表于 2019-4-29 05:19:42 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   91% (261)
 
 
8% (23)    👎
这题还是要backtrack方法+贪婪法。动态法可能有解,但是那玩意不是普遍使用。
回复

使用道具 举报

我的人缘0
EdsgerW 发表于 2019-4-28 23:54:03 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (68)
 
 
1% (1)    👎
感谢分享~同准备亚麻面试-
回复

使用道具 举报

我的人缘0
Vankhart 发表于 2019-4-29 00:53:46 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
积分不到看不到。。。但是我猜应该是求有多少种不同的方式?dp的题目?
回复

使用道具 举报

我的人缘0
flychicken 发表于 2019-4-29 00:56:14 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (10)
 
 
0% (0)    👎
看不到啊。难受。leetcode 上有类似的吗
回复

使用道具 举报

我的人缘0
 楼主| BubbleFan 发表于 2019-4-29 03:10:35 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (39)
 
 
0% (0)    👎
Vankhart 发表于 2019-4-29 00:53
积分不到看不到。。。但是我猜应该是求有多少种不同的方式?dp的题目?

我没有设置积分。。可能是管理员设置的吧?
LeetCode 322的变种,就是每种硬币有数量限制。
我谷歌了好些,感觉答案都太对。。
回复

使用道具 举报

我的人缘0
 楼主| BubbleFan 发表于 2019-4-29 03:11:51 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (39)
 
 
0% (0)    👎
flychicken 发表于 2019-4-29 00:56
看不到啊。难受。leetcode 上有类似的吗

LeetCode 322 coin change的变种,每种硬币有数量限制。
感觉这个题目还蛮有现实意义的,毕竟售货机得用类似的算法吧。。
我反正还想不出来咋做,所以问问大家!
回复

使用道具 举报

我的人缘0
Hypertin 发表于 2019-5-2 00:44:19 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   85% (6)
 
 
14% (1)    👎
同准备亚麻面试-
回复

使用道具 举报

我的人缘0
chenyijia055 发表于 2019-5-4 15:42:08 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
tinlittle 发表于 2019-4-29 08:09
这题在322的解之上再加一层每一枚coin的总数的循环就好了,因为coin数不是无限的,哪个针对amount的循环要 ...

没看懂 你这里为什么是 dp = min(dp, num + dp[i-c*j]) 而不是 dp = min(dp, j + dp[i-c*j])
还有这里是 for i in reversed(range(c*num, amount+1)):  而不是for i in reversed(range(c*j, amount+1)):
回复

使用道具 举报

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

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地

GMT+8, 2019-6-17 09:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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