s*****n
发帖数: 994 | 1 你有很多coins, like 1,2,5..,100,or more cents
You need to pay n cents by given n. What is the minimum number of coins you
need?
要求O(1)解法
(hint: based on O(n) to per-calculate certain constant number) | l*n
发帖数: 529 | 2 这种每个硬币都能被更小硬币取代的组合直接greedy就行了。
但是例如3,5,7这种大的不能被小的组合的情况是没法O(1)的。
you
【在 s*****n 的大作中提到】
: 你有很多coins, like 1,2,5..,100,or more cents
: You need to pay n cents by given n. What is the minimum number of coins you
: need?
: 要求O(1)解法
: (hint: based on O(n) to per-calculate certain constant number)
| z****e
发帖数: 54598 | 3 我的想法
先找到最大面值那个coin
然后根据最大面值切割区间
然后制作一个区间的最小coin数量
然后apply到每一个区间里面去
一般而言，面值越大，间距越大
比如1-2-5-10-20-50-100
所以这种方法还是可行的
因为100以上的数值，肯定需要一张100的钞票酱紫
但是如果是1-2-5-...-50-98-99-100
那就需要额外优化处理 |
|
