menu combo
国人小哥+一个shadow abc
老哥人很nice!
// Input:
Menu:
"Fruit": 2.15,
"Fries": 2.75,
"Salad": 3.35,
"Wings": 3.55,
"Mozzarella": 4.20,
"Plate": 5.80,
target = 4.3
output:
[["fruit", "fruit"]]
假设给你一份菜单 找出所有combo最终的价格的等于target price.
很显然backtracking题目,秒了 最后聊了聊corner case.
这题有个follow up,不给target price,给一个getPrice(“Mozzarella”, “Wings”)各种组合的API,menu combo会被call很多次,要你设计一个数据结构怎么存。。。
Xavier
(Xavier)
3
组合是指 m 个 “Mozzarella” + n 个 “Wings”
吗?
不是,原题有点记不清了,好像是存任意若干个组合(不是n个同一种),call最终的价格
Xavier
(Xavier)
8
应该可以把组合map成一个数字,这样也就是存储若干数字,如果是连续区间的数字可以存成interval
另外就是存储小于一定值(比如100)的price对应的combo,相当于cache,更大的price可以在这个cache的基础上计算出来,相当于省去计算price在前100的dp过程