狗狗11/2店面

请告诉我 问这么容易的题是正常的……

1. 给一个数组，找到比左右邻居都大的element。比如[1,2,3,4,3,5,6,7]，返回4
看到这道题，内心无数黑人问号

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

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

补充内容 (2016-11-10 10:58):
刚收到二面通知，森森滴感觉被放水

希望也可以遇到到和LZ类似的题。估计这样的题就是考察细节和一定要bug free吧。
第一题我觉得最优不可能少于O(N)，因为数组中任何元素都各自独立并都有可能影响最终结果。第二题我用vector::iterator比较方便。

1. int firstLocalMax(vector<int>& a) { // O(N)
   
2.   int i = 0;
   
3.   while (i < a.size()-2) {
   
4.     if (a[i] < a[i+1]) {
   
5.       if (a[i+1] > a[i+2]) return a[i+1];
   
6.       else if (a[i+1] == a[i+2]) { i+=2; continue; }
   
7.     }
   
8.     i++;
   
9.   }
   
10.   return INT_MIN;
    
11. }
    
12. 
    
13. class NegativeItr {
    
14. private:
    
15.   vector<int>::iterator itr, end;
    
16. public:
    
17.   NegativeItr(vector<int>& a):itr(a.begin()),end(a.end()) { // worst O(N)
    
18.     while (itr != end && *itr >= 0) ++itr;  
    
19.   }
    
20.   
    
21.   bool hasNext() { return itr != end; } // O(1)
    
22.   int next() { // worst O(N)
    
23.     if (!hasNext()) return INT_MAX;
    
24.     int res = *itr++;
    
25.     while (itr != end && *itr >= 0) ++itr;
    
26.     return res;
    
27.   }
    
28. };

复制代码

zhan1612 发表于 2016-11-5 11:30
第一题是lc原题， 条件是无重复数， 然后两边无限小。
思路是：
if(mid < mid+1)

多谢！我说怎么能O(logN)时间解决呢，原来Leetcode 162原题里还有两个限制条件。。。


PS（纯娱乐）：我想了想为什么加上那两个条件就可以O(logN)时间解决（即使不是sorted），这其实就是一个微积分关于连续函数局部极大值证明题的离散版本啊！
根据离散条件，我可以对等的出这么一道题：（这个题就是用闭区间套定理证明的，相当于binary search）
给定一个定义在闭区间[a, b]上的连续函数f(x), 满足：
1. f(x) > f(a), f(x) > f(b), 对任意 x in (a, b);
2. 对任意 x in [a, b], 存在小邻域(x-d, x+d) 使得f(x)在(x-d, x]和[x, x+d)上分别严格单调 （若x=a or b的话只需满足一边）。
求建立一个[a, b]中的一个序列{x_n}使其收敛到一个严格局部极大值。

你给f(x)的假设条件太强了，因为可能它就不是可导的。而且为什么要求f(a)=f(b)呢？而且即使找到f'(x)=0的点也不能说明它就一定是严格局部极大值点。
这个关键是要把a[i]!=a[i+1]翻译成等价的连续形式。在离散系统中1就是最小的delta, 而在连续系统中就只能用存在邻域的形式表述了。而这个题是要构造找出严格极大值点，光证明存在性还是不够的。我在Leetcode 162的discussion 中写了证明离散（就是本题）和连续两个版本的证明。得用到实数域的比区间套定理。

第一题binary search3分钟写出来
第二题怎么做……参数的Iterator有没有peek()之类的东西？

Owenli20 发表于 2016-11-4 19:28
第一题binary search3分钟写出来
第二题怎么做……参数的Iterator有没有peek()之类的东西？

第一题我当时也想到binary search, 但他说不是sorted, 那怎么判断从mid往左走还是往右走？感觉都是O(n)

第二题在类里定义一个iterator存储input, 定义一个int存储下一个负数，hasNext()用来更新这个int

第一题是lc原题， 条件是无重复数， 然后两边无限小。
思路是：
if(mid < mid+1)
     left = mid+1;
else
     if(mid > mid+1)
         return  mid;
     else
         right = mid-1;

这两道貌似都是leetcode原题，第一道162，第二道341？

我也是大概这么容易的题 然后挂了

33847682 发表于 2016-11-4 21:59
我也是大概这么容易的题 然后挂了

那我也得做好心理准备了……你是几号面的？

jpeng7 发表于 2016-11-4 21:47
这两道貌似都是leetcode原题，第一道162，第二道341？

第二题跟284差不多，唉，就感觉做过，好久以前做的都忘了

zhan1612 发表于 2016-11-4 21:30
第一题是lc原题， 条件是无重复数， 然后两边无限小。
思路是：
if(mid < mid+1)

两边怎么处理我都没问，目测挂定了