巧克力甜度

我觉得binary search的解有点太tricky了
想不到一个思路来跟面试官从无到有讨论出这样的想法
有人有idea吗

我目前的考量是, 假如我在面试遇到这题
我可能会先提到DP, 从recursion到bottom-up
然后space从O(NM)到O(N)
中途看看面试官会不会不满意而给我binary search的hint
没有的话就不回答这个做法了
不然有点太明显写过这道题目

Lunluen 发表于 2019-3-28 02:22
我觉得binary search的解有点太tricky了
想不到一个思路来跟面试官从无到有讨论出这样的想法
有人有idea ...

如果我要面到这题，我设定的剧本是就先带个例子，手算expected answer，过程就试一下不同的分割方法，说这样分太大了，这样分又太小了，所以 这样分好像是最大了不可能再更大了......这样带两个例子，最后说其实答案好像可以用于得，根据猜的结果把边往往或往下调，就可以相对而言比较自然地衔接到怎么想到二分法了

最多能分 int(sum // n), 最少1 。 用二分。

二分内部目标如果是mid,逻辑是至少有mid:
遍历数组，一旦到达mid就中断切开，切完N- 1刀剩下的大于mid说明可行： l = mid; 小于说明不可行: r = mid - 1。

我还以为楼主有推荐的好吃的巧克力

贡献一个dp解法吧，复杂度肯定不如二分。但之前看到加油站那个题（好像是，记不太清了）面试管强行要求dp解，准备份dp的以防万一

1. 
   
2. def chocolate(nums, k):
   
3.         # time: O(n^2 * k) space: O(nk)
   
4.         if not nums or len(nums) < k:
   
5.             return 0
   
6.         
   
7.         pre_sum = [0] * (len(nums) + 1)
   
8.         for i in xrange(len(nums)):
   
9.             pre_sum[i + 1] = pre_sum[i] + nums[i]
   
10.         
    
11.         dp = [[0] * (len(nums) + 1) for _ in xrange(k + 1)]
    
12.         for i in xrange(1, len(nums) + 1):
    
13.             dp[1][i] = pre_sum[i]
    
14.         
    
15.         for i in xrange(2, k + 1):
    
16.             for j in xrange(i, len(nums) + 1):
    
17.                 for m in xrange(1, j):
    
18.                     dp[i][j] = max(dp[i][j], min(dp[i - 1][m], pre_sum[j] - pre_sum[m]))
    
19.         
    
20.         return dp[k][len(nums)]

复制代码

肆意领 原题 minimize最大的sum 不就是maximize最小的sum
因为切大了都被别人拿走了只剩下最小的留给自己,所以给别人少点就相当于给自己多一点

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

****  ...

Good work! Although small problem at initialization: you set l = min(nums). What would happen if the length of array (# of chocolates) is less than the # of people? Your solution will return min(nums) rather than the correct solution which is 0.

bradFCB 发表于 2019/04/16 12:35:25


Good work! Although small problem at initialization: you set l = min(nums). What would happen if t...

是的，所以通常面试第一件事情就是把k的范围讲清楚，这样面试官就不会挑了

        给你点个赞！

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

****  ...

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