一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
Visa Tracker
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 312|回复: 2
收起左侧

[二分/排序/搜索] 请教下Binary Search模版

[复制链接] |只看干货 |刷题, 二分/排序/搜索
我的人缘0

升级   2.86%


分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   90% (347)
 
 
9% (38)    👎

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

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

x
Binary Search相关的题一般来说大体思路比较清楚,但是个人觉得有时候边界条件比较容易犯错。想问下大家有没有好的模版啊之类处理Binary Search相关题型。
我个人看到的几个相关网页和视频:
花花
https://www.youtube.com/watch?v=v57lNF2mb_s
https://www.youtube.com/watch?v=J-IQxfYRTto

The Matrix
https://www.youtube.com/watch?v=25086D5uZmY
他视频里提到的first yes和last no的模版个人觉得还不错,不过感觉有些题套用不上去。

知乎上一个总结:
https://zhuanlan.zhihu.com/p/101188615

评分

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

查看全部评分


上一篇:关于28. Implement strStr()的while条件
下一篇:LeetCode 332. Reconstruct Itinerary 有人能看懂这个DFS解法吗?
我的人缘2
红A 2020-9-25 05:20:17 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   84% (2276)
 
 
15% (427)    👎
知乎的挺好的,也就3种模板吧
left <= right
left < right
left + 1 < right

考虑一下截止条件就比较清楚了。所有题目三种模板都应该是可以的,只是有的需要处理边界,我个人用的是第一种,必要的时候加一个
res来保存最后一次valid的情况。

评分

参与人数 1大米 +1 收起 理由
mjnchen2014 + 1 赞一个

查看全部评分

回复

使用道具 举报

我的人缘0

升级   67%

kamm 2020-9-26 06:19:54 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (48)
 
 
0% (0)    👎
我觉得最好的办法是不要自己写,用自带的库函数,算cheating吗?
https://www.1point3acres.com/bbs/thread-670713-1-1.html

昨天刷的题
LC 1011
[Java] 纯文本查看 复制代码
import java.util.AbstractList

class Solution {


    fun shipWithinDays(weights: IntArray, D: Int): Int {


        val list = object : AbstractList<Int> () {
            override fun get(index: Int): Int {
                return index + 1
            }

            override val size: Int
                get() = weights.sum() 

        }

        val index = list.binarySearch{

            var current = 0
            var count = 1
            for(i in weights){

                if((current + i) <= it) {
                    current += i
                } else {
                    current = i
                    count += 1
                    if(count > D || current > it){
                        println("$it is not valid")
                        return@binarySearch -1
                    }
                }
            }
            println("$it is valid")
            1

        }

        return -index 

    }
}

回复

使用道具 举报

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

本版积分规则

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

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

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