FB电面

wood cut

oml 发表于 2019-9-9 21:01
should be this one

Given an int array wood representing the length of n pieces of wood and an int ...

是的！字数字数

binary search, trial and error, 类似于koko eating bananas

1.     public static int woodcut(int[] woods, int target) {
   
2.         if (woods == null || woods.length == 0) return -1;
   
3.         int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE, sum = 0;
   
4.         for (int i = 0; i < woods.length; ++i) {
   
5.             min = Math.min(min,woods[i]);
   
6.             max = Math.max(max,woods[i]);
   
7.             sum += woods[i];
   
8.         }
   
9.         if (target > sum || min <= 0 ) return -1;
   
10.         int l = min, r = max;
    
11.         while (l < r) {
    
12.             int m = (l+r)/2 + 1;
    
13.             int count = countWood(woods,m);
    
14.             if (count < target) {
    
15.                 r = m - 1;
    
16.             } else {
    
17.                 l = m;
    
18.             }
    
19.         }
    
20.         return countWood(woods,l) >= target ? l : -1;
    
21. 
    
22.     }
    
23. 
    
24.     private static int countWood(int[] woods, int cutLen) {
    
25.         int count = 0;
    
26.         for (int wood : woods) {
    
27.             count += wood/cutLen;
    
28.         }
    
29.         return count;
    
30.     }

复制代码

[/i][/i][/i]

梅亮 发表于 2019-9-10 12:35
binary search, trial and error, 类似于koko eating bananas

[mw_shl_code=java,true]    public stati ...

代码有点问题。左边要从1开始，而不是从数组中的最小数字开始。

是，左边应该从 1 开。

minggo 发表于 2019-9-10 17:28
是，左边应该从 1 开。

确实，已经改过来了

leetcode 875蕾丝

1. class Solution {
   
2.     public int cutWood(int[] wood, int k){
   
3.         if(wood.length == 0 || k == 0) return 0;
   
4.         int left = 1, right = Integer.MAX_VALUE;
   
5.         int res = 0;
   
6.         if(!canCut(wood, left, k)) return 0;
   
7.         while(left <= right){
   
8.             int mid = left + (right - left) / 2;
   
9.             boolean valid = canCut(wood, mid, k);
   
10.             if(valid){
    
11.                 left = mid + 1;
    
12.                 res = mid;
    
13.             }
    
14.             else right = mid - 1;
    
15.         }
    
16.         return res;
    
17.     }
    
18.    
    
19.     private boolean canCut(int[] woods, int n, int k){
    
20.         int count = 0;
    
21.         for(int wood: woods) count += wood;
    
22.         return count / n >= k;
    
23.     }
    
24. }

复制代码

这边写了个稍微concise的版本