谷苟面经题

最近翻地理的面经贴，看到一道高频题，但没想到好的做法，求大家指点一下
题目如下：

可乐饮料机，有一系列按钮，每个按钮按下去会得到一定体积范围的可乐。先给定一个目标体积范围，问不限制按按钮次数，能否确定一定能得到目标范围内的可乐？
举例：有三个按钮，按下去得到的范围是[100,

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这样做复杂度蛮高的，也没法memoize，求大家的见解谢谢



补充内容 (2018-10-30 09:56):
顺便求个米

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=449947&extra=&page=1
个人实现代码：

1. 
   
2. // 类似如下dfs（下面的code里pair不能作为memo的key，待改）
   
3. bool dfs(pair<int, int> temp, pair<int, int> range, vector<pair<int, int>>& buttons, unordered_map<pair<int, int>, bool>& memo) {
   
4.     if (memo.count(temp))
   
5.         return memo[temp];
   
6.     if (range.first <= temp.first && temp.second <= range.second)
   
7.         return true;
   
8.     if (range.second < temp.second)
   
9.         return false;
   
10.     for (auto button : buttons) {
    
11.         if (dfs({button.first + temp.first, button.second + temp.second}, range, buttons, memo)) {
    
12.             memo.insert();
    
13.             return true;
    
14.         }
    
15.     }
    
16.     memo[temp] = false;
    
17.     return false;
    
18. }
    
19. 
    
20. bool isInCocaMachineRange(pair<int, int> range, vector<pair<int, int>>& buttons) {
    
21.     unordered_map<pair<int, int>, bool> memo;
    
22.     return dfs({0,0}, range, buttons, memo);
    
23. }
    
24. 
    
25. int main() {
    
26.     vector<pair<int, int>> button1 = {{100, 120}, {200, 240}, {400, 410}};
    
27.     cout << (isInCocaMachineRange({100, 110}, button1) ? "In" : "Not in") << endl; // false
    
28.     cout << (isInCocaMachineRange({90, 120}, button1) ? "In" : "Not in") << endl; // true
    
29.     cout << (isInCocaMachineRange({300, 360}, button1) ? "In" : "Not in") << endl; // true
    
30.     cout << (isInCocaMachineRange({310, 360}, button1) ? "In" : "Not in") << endl; // false
    
31.     cout << (isInCocaMachineRange({1, 999999999}, button1) ? "In" : "Not in") << endl; // true
    
32.     return 0;   
    
33. }
    

复制代码

def colaMachine(buttons, r):
        memo = dict()
        return dfs([0, 0], buttons, r, memo)

def dfs(temp, buttons, r, memo):
        temp = tuple(temp)
        start, end = temp
        if temp in memo: return memo[temp]
        if start >= r[0] and end <= r[1]:
                return True
        if end > r[1]:
                return False
        for button in buttons:
                if dfs([start + button[0], end + button[1]], buttons, r, memo):
                        memo[temp] = True
                        return True
        memo[temp] = False
        return False

这样做memorize对吗，求各路大神指正

第一次见 哈哈 感觉是dp背包 回头想想

LoseYourself 发表于 2018-10-30 09:50
def colaMachine(buttons, r):
        memo = dict()
        return dfs([0, 0], buttons, r, memo)

我也是这个思路。但这样memo的话subproblem重合的几率感觉不大鸭。

感觉是这个思路哈

这里面有一个很trick的地方，注意上下差值，然后对齐下线就可以了。不用全部塞进去。你每次加一组新的差值都在扩大。这样可以剪枝。然后只要下线对齐，插值不超过目标范围就可以了。

foryousee 发表于 2018-10-30 14:39
这里面有一个很trick的地方，注意上下差值，然后对齐下线就可以了。不用全部塞进去。你每次加一组新的差值 ...

可以详细说一下么？请问对齐下线是指什么呢？

题目有问题吧，按照你的说法，
假设目标是[100, 110], 那答案是不能。因为按下一，可能得到120体积的可乐，不在目标范围里，我可以按两下button 1，不也是true吗

lunatic_luna 发表于 2018-10-31 00:07
可以详细说一下么？请问对齐下线是指什么呢？

我好像解释的有点问题，我一会儿试着写一下code po过来吧。

wjw779 发表于 2018-10-31 04:05
题目有问题吧，按照你的说法，
假设目标是[100, 110], 那答案是不能。因为按下一，可能得到120体积的可乐 ...

按两次也是不能呀