巧克力甜度

hoort 发表于 2019/05/12 07:19:50


为什么这个total >= target 以后不把 total = num 而是 set 成0
这样算total 不就少了一个值了么？

这就看你要问什么了，410那题要求的是每一段都不能超过target，所以>target时把total设为num，这个num要算到下一段的total才不会使当前的total超过target；这题要求的是每一段都至少达到target，一但>=target这一段total就达标了，total设为0因为当前的num是达标target的一部分，不属于下一个片段

仿照lc410，binary search + greedy:

def split_array(nums, p):
  min_sweet = min(nums)
  max_sweet = sum(nums)
  l, r = min_sweet, max_sweet
  res = min_sweet # want more
  while l <= r:
    mid = l + int((r-l) / 2)
    sub_sum = 0 # want to find less
    count = 1
    for i in nums:
      if sub_sum >= mid:
        count += 1
        sub_sum = i
      else:
        sub_sum += i
    if sub_sum >= mid and count >= p: # mid value is good, but want to find a bigger one
      l = mid + 1
      res = max(res, mid)
    else: # mid value is not good, need to narrow it down
      r = mid - 1
  return res

补充内容 (2019-5-15 05:27):
抱歉，有些corner case没有考虑进去。代码有问题。

抱歉之前发的代码测试不全，这次又参考了了大家的test case完善了一些。方法就是参考lc410的binary search + greedy。本人新手，如有不对请指正。

1. def chocolate_array(nums, p):
   
2.   min_sweet = min(nums)
   
3.   max_sweet = sum(nums)
   
4.   l, r = min_sweet, max_sweet
   
5.   res = min_sweet
   
6.   while l <= r:
   
7.     mid = l + int((r-l) / 2)
   
8.     sub_sum = 0
   
9.     count = 1
   
10.     for i in nums:
    
11.       if sub_sum >= mid:
    
12.         count += 1
    
13.         sub_sum = i
    
14.       else:
    
15.         sub_sum += i
    
16.     if (sub_sum >= mid and count >= p) or (sub_sum < mid and count >= p + 1): # mid value is good, but want to find a bigger one
    
17.       l = mid + 1
    
18.       res = max(res, mid)
    
19.     else: # mid value is not good, need to narrow it down
    
20.       r = mid - 1
    
21.   return res

复制代码

kaipeng21 发表于 2019-3-18 22:55
原题是猜一个数使每一片段都 =这个数，这少可以分成n片（或是找最小的一个数，让他无法分成n片）

****  ...

所以这个代码是LC原题的，不是这道题的呀

朋友面谷歌的时候被问到了经典的巧克力甜度的Follow-up问题，我们讨论了一会也没有明确的解法，求教下论坛大神。原题就是高频那题，给一个巧克力bar甜度是一个Array,可以切K-1刀分成K块，自己只能拿总甜度最低的那块，问自己能拿到的总甜度最高是多少。用Binary Search做完后，复杂度是O(NlgN) 。还剩一些时间，面试官就问了他一个Follow-up。假设这是一个巧克力环,要切K刀分成K份如何解。比如说 [7,6,3,3,5,2,1,1] 其实是首尾相连的，所以可以切成[3,5,2],[1,1,7],[6,3]答案就是9。当时朋友没有好的idea，就说是直接暴力解啦，对每一个可能的arr做Binary search 复杂度是(N^2lgN)。然后面试官就问他有没有什么其他的idea,胡扯了2-3分钟时间也到了。所以这个Follow-up到底怎么做？

要点只是看能不能分成k-1份 区别就是辅助函数里面怎么check吧

原来从起点开始往一个方向切
现在可以先从0开始 然后-1 然后-2 直到往后也超过限制为止

任意一个起点true就可以返回

pandami 发表于 2019-6-8 08:07
要点只是看能不能分成k-1份 区别就是辅助函数里面怎么check吧

原来从起点开始往一个方向切

哦哦。懂你的意思了，这样的话平均情况下会小于O(N*N*logN)，很可能每一次甜度Check前几个起点就True了。不过在最坏的情况下应该也是O(N*N*logN)， 比如每次二分猜都是False，或者True情况是在最后几个起点？

juventusland 发表于 2019/06/08 08:48:37


哦哦。懂你的意思了，这样的话平均情况下会小于O(N*N*logN)，很可能每一次甜度Check前几个起点就True了。不过在最坏的情况下应该也是O(N*N*logN)， 比如每次二分猜都是Fals...

可以固定一个起点比如0

往前时候是0到i第一块
往后是-i到0第一块

可以说起点是包涵0的那块

这样感觉可以简单一点不需要每个点都当起点

补充内容 (2019-6-8 09:51):
就是说check时候第一块必须有0

补充内容 (2019-6-8 10:04):
所以可以选最大的一块做为起点

块也好圈也好， 你总有一块一定是满足你的最后需求的。

这一块不论是块还是圈都是不分开的，他就变成了你新的块的起点。

贡献一个follow up: 面试官问如果有负数怎么办 (之前没看dp解法 不知道dp可以解负数)  我说二分应该不能解 但是用dp应该可以解, 因为如果我们想把这个问题变成可以用二分解的, 那确定好负数该怎么分配的时候也就相当于确定好了全局该怎么分配. 没有写码