查看: 484|回复: 9
收起左侧

[二分/排序/搜索] 请教一道lintcode上的题:wood cut

|只看干货 |刷题, columbia
pxuu | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (3)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
Description
Given n pieces of wood with length L (integer array). Cut them into small pieces to guarantee you could have equal or more than k pieces with the same length. What is the longest length you can get from the n pieces of wood? Given L & k, return the maximum length of the small pieces.

The unit of length is centimeter.The length of the woods are all positive integers,you couldn't cut wood into float length.If you couldn't get >= k pieces, return 0.

Example 1
Input:
L = [232, 124, 456]
k = 7
Output: 114
Explanation: We can cut it into 7 pieces if any piece is 114cm long, however we can't cut it into 7 pieces if any piece is 115cm long.

LC上有很多类似的题,对于这道题,思路也是类似的,用二分法来trial and error。
主要问题是这个二分搜索的结束条件 while (lo + 1 < hi) { // why lo+1 < hi?
通过跑例子,我能知道应该用这个条件,否则无法exit loop。
但是一开始想的时候怎么想到呢?请大神们赐教~

[Java] 纯文本查看 复制代码
public class Solution {
    /**
     * @param L: Given n pieces of wood with length L[i]
     * @param k: An integer
     * @return: The maximum length of the small pieces
     */
    public int woodCut(int[] L, int k) {
        // write your code here
        int lo = 1, hi = 0;
        for (int l : L) {
            hi = Math.max(l, hi);
        }
        while (lo + 1 < hi) {   // why lo+1 < hi?
            int mid = lo + (hi-lo)/2;
            int numPieces = getNumPieces(L, mid);
            if (numPieces >= k) {
                lo = mid;  // lo is a possible candidate, so lo = mid (not mid+1)
            } else {
                hi = mid - 1;
            }
        }
        if (getNumPieces(L, hi) >= k) return hi;
        if (getNumPieces(L, lo) >= k) return lo;
        return 0;
    }

    private int getNumPieces(int[] L, int len) {
        int ans = 0;
        for (int l : L) {
            ans += l / len;
        }
        return ans;
    }
}



评分

参与人数 1大米 +2 收起 理由
14417335 + 2

查看全部评分


上一篇:力扣T shirt
下一篇:binarysearch.com开房间同场竞技
cnxhk 2021-4-23 03:35:48 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
主要是经验,注意二分的形式:

如果是 lo = mid, hi = mid - 1显然是没法跳出循环的,需要特殊判断差为1的情况
如果是 lo = mid + 1, hi = mid 是没问题的

但前者推荐你这么写:int mid = lo + ((hi-lo+1)>>1);
这样如果是差1会被assign成hi,就不存在这个问题了

评分

参与人数 1大米 +1 收起 理由
pxuu + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (550)
 
 
0% (1)    👎
二分其实应用了单调性,也就是说如果一个长度可以切出那么多来,那比他小的长度一定都可以。如果一个长度切不出来,那么比他大的也一定切不出来。这样的话就可以求两个的边界点,也就是可以用二分。类似first bad ver sion
回复

使用道具 举报

wisdompeak2 2021-4-23 11:15:49 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (508)
 
 
1% (8)    👎
换做我会这么写:
```
public class Solution {
    /**
     * @param L: Given n pieces of wood with length L[i]
     * @param k: An integer
     * @return: The maximum length of the small pieces
     */
    public int woodCut(int[] L, int k) {
        // write your code here
        int lo = 1, hi = 0;
        for (int l : L) {
            hi = Math.max(l, hi);
        }
        while (lo < hi) {  
            int mid = hi - (hi-lo)/2;
            int numPieces = getNumPieces(L, mid);
            if (numPieces >= k) {
                lo = mid;  // lo is a possible candidate, so lo = mid (not mid+1)
            } else {
                hi = mid - 1;
            }
        }
        return hi;
    }
}
```
注意两点:
1. 模板永远用while (lo<hi),这样退出循环的时候一定是lo==hi. 因为本题一定有合理解,所以收敛解就是最终的最优解,不需要额外check答案。
2. 根据hi/lo来算mid这一行会需要根据你后面的代码做变动。本题中 ```... lo=mid; ... hi = mid - 1... ```为了避免死循环,所以你就需要写成mid = hi-(hi-lo)/2。 如果在其他题目里是 ```... lo = mid+1; ... hi = mid...``` 那么你就要写成mid = lo+(hi-lo)/2. 这个不需要死记硬背,你想想lo=0,hi=1,那么下一轮为了防止继续lo=0,hi=1,你该怎么写。

评分

参与人数 2大米 +4 收起 理由
14417335 + 3
pxuu + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

 楼主| pxuu 2021-4-24 07:47:26 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (3)
 
 
0% (0)    👎
cnxhk 发表于 2021-4-23 03:35
主要是经验,注意二分的形式:

如果是 lo = mid, hi = mid - 1显然是没法跳出循环的,需要特殊判断差为1 ...

多谢指点!
想给大佬加米,但是积分不够,加不成。。

补充内容 (2021-04-25 00:22 +8:00):
我的积分到100了,可以给各位加米了
回复

使用道具 举报

hjldtc 2021-4-24 07:55:09 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (300)
 
 
5% (18)    👎
直接写成l+1<r
l=mid
r=mid
最后出来l和r再判断一下
这样就不用纠结会不会死循环了
这种二分对新手友好
九章算法学来的哈哈
回复

使用道具 举报

 楼主| pxuu 2021-4-24 08:00:52 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (3)
 
 
0% (0)    👎
wisdompeak2 发表于 2021-4-23 11:15
换做我会这么写:
```
public class Solution {

多谢大佬指点!有些特别tricky的test case,我加了一个判断if (sum < k) return 0; 这样就可以把binary search之后的那些判断删去了。

[Java] 纯文本查看 复制代码
    public int woodCut(int[] L, int k) {
        if (L == null || L.length == 0)
            return 0;
        // System.out.println("L length = " + L.length + ", k = " + k);
        // write your code here
        int lo = 1, hi = 0;
        long sum = 0;
        for (int l : L) {
            hi = Math.max(l, hi);
            sum += l;
        }
        if (sum < k) return 0;
        while (lo < hi) {  
            // int mid = lo + (hi-lo+1)/2;
            int mid = hi - (hi-lo)/2;
            int numPieces = getNumPieces(L, mid);
            if (numPieces >= k) {
                lo = mid;  // lo is a possible candidate, so lo = mid (not mid+1)
            } else {
                hi = mid - 1;
            }
        }
        // if (getNumPieces(L,hi) >= k) return hi;
        // if (getNumPieces(L,lo) >= k) return lo;
        return lo;
    }
回复

使用道具 举报

Falldawn 2021-4-24 08:46:06 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (62)
 
 
8% (6)    👎
具体请看我的帖子https://www.1point3acres.com/bbs/thread-747061-1-1.html
我觉得非常清楚了

评分

参与人数 2大米 +2 收起 理由
14417335 + 1
pxuu + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

Falldawn 2021-4-24 08:47:31 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (62)
 
 
8% (6)    👎
pxuu 发表于 2021-4-24 08:00
多谢大佬指点!有些特别tricky的test case,我加了一个判断if (sum < k) return 0; 这样就可以把binary s ...

具体请看我的帖子https://www.1point3acres.com/bbs/thread-747061-1-1.html
我觉得非常清楚了,请仔细阅读,多谢

在这里我要指出来,你最好写成一个返回boolean的函数,为什么?因为可以提前退出。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

>
快速回复 返回顶部 返回列表