FB电面

FB电面，争取为下一轮攒人（大）品（米）。

面试官上来先是客套话问我今天过得怎么样，我说不错啊，你呢？面试官：“我车窗被砸了，所以早上心情不太好。。。” 我：“您节哀。。。”

之后就直接进入答题环节了：
如果有一些长短不一（但是长度都是整数）的木头，和一个正整数X，那么能截

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

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

-10 11:39):
之前没见过这道题，面试时试了几个思路才选定对切分后的长度做binary search. 面试之后也没有想到更好的解法。

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]

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的版本

should be this one

Given an int array wood representing the length of n pieces of wood and an int k. It is required to cut these pieces of wood such that more or equal to k pieces of the same length len are cut. What is the longest len you can get?

楼主能不能举个例子。。没看太懂这道题

没看太懂这道题，楼主举几个例子，或者可以说的更详细一些吗？感谢

楼主能给点细节和例子吗，谢谢

请问楼主可以给下解题思路吗

请问楼主可以是面的什么岗位或者组呢？

比如五根木头长度分别为1,2,3,4,5，
要切出5段，最大长度是2
要切7段，最大长度是1
要切16段，切不了

binary search

这题叫wood cut

二分法 这题是二分法经典入门题