10.11狗家昂赛

10.11 狗家昂赛
10点开始第一轮，白人小哥给一个string，和一个suffix array， array里面存储的是按字典序排序后的suffix tree的起始位置的index。例："banana" array[] = [5,3,1,0,4,2];
write a function to search a  substring.
第二轮，国人小姐姐。 给一块长条状巧克力，巧克力每一小

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

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

quot;am","ama","amadog"]，在"m"，第二个"a"和"g"处都会call signal()

第一轮麻烦楼主能给个例子什么的吗，不太好理解...，谢谢了;
第二轮LC410变种，不过原题的binary search是不能用的，因为这里的最大最小不等于原题的最小最大，只能用O(N^2 * K)的DP；
第五轮LC1032

补充内容 (2019-10-20 01:08):
抱歉，第二轮也可以用二分，我之前没想好切分的方法。https://leetcode.com/discuss/int ... Chocolate-Sweetness

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

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

1. int numOfPieces(vector<int> v, int sweetness) {
   
2.         int piece = 1;
   
3.         int curSweetness = 0;
   
4.         for (int i : v) {
   
5.                 if (i + curSweetness > sweetness) {
   
6.                         ++piece;
   
7.                         curSweetness = 0;
   
8.                 }
   
9.                 curSweetness += i;
   
10.         }
    
11.         return piece;
    
12. }
    
13. 
    
14. int getMin(vector<int> v, int capacity) {
    
15.         int ret = INT_MAX;
    
16.         int sum = 0;
    
17.         for (int i : v) {
    
18.                 if (sum + i > capacity) {
    
19.                         ret = min(ret, sum);
    
20.                         sum = 0;
    
21.                 }
    
22.                 sum += i;
    
23.         }
    
24.         return min(ret, sum);
    
25. }
    
26. 
    
27. int findSweetness(vector<int> v, int k) {
    
28.         int l = *max_element(v.begin(), v.end());
    
29.         int h = accumulate(v.begin(), v.end(), 0);
    
30.         int res = *min_element(v.begin(), v.end());
    
31.         while (l < h) {
    
32.                 int mid = (l + h) / 2;
    
33.                 int p = numOfPieces(v, mid);
    
34.                 if (p <= k) {
    
35.                         if (p == k) {
    
36.                                 res = max(res, getMin(v, mid));
    
37.                         }
    
38.                         h = mid;
    
39.                 }
    
40.                 else {
    
41.                         l = mid + 1;
    
42.                 }
    
43.         }
    
44.         return res;
    
45. }

复制代码

写了下sweetness的code，就是lc上的类似题，但是稍微复杂一点。楼主能帮忙看看对错吗，自己试了几个case都是对的。

spotti 发表于 2019-10-19 02:52
[mw_shl_code=cpp,true]int numOfPieces(vector v, int sweetness) {
        int piece = 1;
        int curSweetness ...

请问和什么题类似呢？

KisekiABC 发表于 2019-10-19 03:38
请问和什么题类似呢？

蠡口逸灵异逸

spotti 发表于 2019-10-19 04:02
蠡口逸灵异逸

感恩的心 zszs

努力的黑子 发表于 2019-10-19 10:09
请问为什么不可以呀？如果每次假设一个最小值待入数组，看看可以分成几份，如果份数>=K，那么就是可分， ...

貌似是可以的，我修改下我的答案。

请问第一题可以举个例子么？没太看懂谢谢了

lthdqq 发表于 2019-10-19 04:58
第一轮麻烦楼主能给个例子什么的吗，不太好理解...，谢谢了;
第二轮LC410变种，不过原题的binary search是 ...

第二轮是 伊尔散佚