店面面试题，cents change 分享，同时求好的解答 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

店面面试题，cents change 分享，同时求好的解答

店面面试题，cents change 分享，同时求好的解答# JobHunting - 待字闺中

d*l2015-04-20 07:04

1 楼

you have 2 quarters, 4 dimes, 5 nickles, and 7 pennies. write a function to
output all the ways that you can use those coins to make 61 cents in change.
我以前写过类似的cents change，但quarter dime nickel and penny 是无限制的用。

l*82015-04-20 07:04

2 楼

dfs would work

to
change.

【在 d******l 的大作中提到】

: you have 2 quarters, 4 dimes, 5 nickles, and 7 pennies. write a function to
: output all the ways that you can use those coins to make 61 cents in change.
: 我以前写过类似的cents change，但quarter dime nickel and penny 是无限制的用。

d*l2015-04-20 07:04

3 楼

能具体点吗？sorry，我没反应过来

dfs would work

【在 l*****8 的大作中提到】

: dfs would work
:
: to
: change.

H*n2015-04-20 07:04

4 楼

可能说的是backtracking，就是一个个试，试不通就回溯。

【在 d******l 的大作中提到】

: 能具体点吗？sorry，我没反应过来
:
: dfs would work

e*x2015-04-20 07:04

5 楼

就是backtracking，然后用一个list来记录剩余硬币的数量
不过我没想到如何在过程中去重，直接用set了，OJ妥妥会超时……
def centsChange(cents):
# pennies, nickles, dimes, quarters
quantity = [7,5,4,2]
value = [1,5,10,25]
path = [0,0,0,0]
result = []
dfs(cents, cents, path, result, quantity, value)
return list(set(result))
def dfs(remaining, cents, path, result, quantity, value):
if remaining < 0: return
if centsSum(path, value) == cents:
result.append(tuple(path))
for i,v in enumerate(quantity):
if v > 0:
path[i] += 1
quantity[i] -= 1
dfs(cents-value[i], cents, path, result, quantity, value)
quantity[i] += 1
path[i] -= 1
def centsSum(coins, value):
result = 0
for i,v in enumerate(coins):
result += v*value[i]
return result
print centsChange(61)

【在 d******l 的大作中提到】

: 能具体点吗？sorry，我没反应过来
:
: dfs would work

a*r2015-04-20 07:04

6 楼

http://www.lintcode.com/en/problem/combination-sum-ii/

d*l2015-04-20 07:04

7 楼

谢谢

就是backtracking，然后用一个list来记录剩余硬币的数量不过我没想到如何在过程中
去重，直接用set了，OJ妥妥会超时……def centsChange(cents)........

【在 e****x 的大作中提到】

: 就是backtracking，然后用一个list来记录剩余硬币的数量
: 不过我没想到如何在过程中去重，直接用set了，OJ妥妥会超时……
: def centsChange(cents):
: # pennies, nickles, dimes, quarters
: quantity = [7,5,4,2]
: value = [1,5,10,25]
: path = [0,0,0,0]
: result = []
: dfs(cents, cents, path, result, quantity, value)
: return list(set(result))

d*l2015-04-20 07:04

8 楼

Leetcode vs. Lintcode, 双兔傍地走啊
第一次看到lintcode, 哈哈

http://www.lintcode.com/en/problem/combination-sum-ii/" x-apple-data-detectors=........

【在 a****r 的大作中提到】

: http://www.lintcode.com/en/problem/combination-sum-ii/