📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2130| 回复: 2
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

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

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

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

上一篇:关于28. Implement strStr()的while条件
下一篇:LeetCode 332. Reconstruct Itinerary 有人能看懂这个DFS解法吗?
🔗
红A 2020-9-25 05:20:17 | 只看该作者
全局:
知乎的挺好的,也就3种模板吧
left <= right
left < right
left + 1 < right

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

评分

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

查看全部评分

回复

使用道具 举报

🔗
kamm 2020-9-26 06:19:54 | 只看该作者
全局:
我觉得最好的办法是不要自己写,用自带的库函数,算cheating吗?
https://www.1point3acres.com/bbs/thread-670713-1-1.html

昨天刷的题
LC 1011
  1. import java.util.AbstractList

  2. class Solution {


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


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

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

  10.         }

  11.         val index = list.binarySearch{

  12.             var current = 0
  13.             var count = 1
  14.             for(i in weights){

  15.                 if((current + i) <= it) {
  16.                     current += i
  17.                 } else {
  18.                     current = i
  19.                     count += 1
  20.                     if(count > D || current > it){
  21.                         println("$it is not valid")
  22.                         return@binarySearch -1
  23.                     }
  24.                 }
  25.             }
  26.             println("$it is valid")
  27.             1

  28.         }

  29.         return -index

  30.     }
  31. }
复制代码

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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