谷苟面经题

嗯？？我怎么感觉这是一个标准的SegTree 的题目。。。

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. }
    

复制代码

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

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