FB新鲜跪经。。

一个国人小哥，听起来很耐心。上来先自我介绍，然后叫我自我介绍，5分钟后开始做题。
不知道是不是我刷

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

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

T。

运气也是背到头。。目测是跪了，哎，move on了。

真的略不懂 国人为啥要出非lc的题难为国人。真的感觉猪队友。三哥之间真的好很多。还记得某个培训机构的老师，很得意地说，自己就喜欢出非lc的题...

似乎是这题？http://www.lintcode.com/en/problem/wood-cut/

1.     int woodCut(vector<int> &L, int k) {
   
2.         // write your code here
   
3.         if(L.empty()) return 0;
   
4.         int maxlen = *max_element(L.begin(), L.end());
   
5.         if(k == 0) return maxlen;
   
6.         int start = max(1, maxlen/k), end = maxlen;
   
7.         while(start < end) {
   
8.             int mid = start + (end - start) / 2;
   
9.             int cnt = 0;
   
10.             for(int len : L) {
    
11.                 cnt += len/(mid+1);
    
12.             }
    
13.             if(cnt >= k) start = mid + 1;
    
14.             else end = mid;
    
15.         }
    
16.         int cnt = 0;
    
17.         for(int len : L) cnt += len/start;
    
18.         return cnt >= k ? start : 0;
    
19.     }
    

复制代码

一个木头可以切几下？

楼主当时有没有先想一个brute force idea，然后再想办法优化下

jiongjiongyoush 发表于 2017-10-7 07:28
一个木头可以切几下？

可以切到不能切为止

这个题好像是在lintcode上有，用二分去解。

这类似wood cut，最优解应该是用binary search，枚举可能能切的长度，长度范围是从1到最长的木头；楼主可以看下这题http://www.lintcode.com/en/problem/wood-cut/

二分法？二分切的木段长度

stone-18 发表于 2017-10-7 07:30
楼主当时有没有先想一个brute force idea，然后再想办法优化下

对的，brute force了，先找到了max L然后递减枚举。。完全没想到binary search

mchzh 发表于 2017-10-7 07:38
这个题好像是在lintcode上有，用二分去解。

对的是wood cut才看到，还是刷题不够啊