FB新鲜跪经。。

zhangyat 发表于 2017-10-7 07:59
对的是wood cut才看到，还是刷题不够啊

不着急了，慢慢刷题吧，题太多了

zhangyat 发表于 2017-10-7 07:58
对的，brute force了，先找到了max L然后递减枚举。。完全没想到binary search

然后面试官有没有给个hint？让你优化，感觉brute force写完了，不一定会挂，后面followup咋样

可一切的长度从[min(L[i]), max(L[i])] 然后二分查找？

感觉这道题可以用quick select诶，其实find the kth smallest element in an array?

同意楼上 应该等同于找第t小的元素吧

补充内容 (2017-10-7 12:22):
不对 不对 第t大。 但是如果一根木头如果正好是2k 切完算2根么

补充内容 (2017-10-7 12:29):
理解错题意了 好尴尬 还不能删帖

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

复制代码

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

感觉题意是只能切一刀呢。。

这只能等T吗，是不是应该大于等于呢

感觉用map也可以解决吧