首页 > 其他分享 >代码随想录day 01 二分法与快慢指针

代码随想录day 01 二分法与快慢指针

时间:2023-12-27 11:55:52浏览次数:39  
标签:快慢 slow 随想录 fast 二分法 01 数组 指针

二分法题目:

实现代码如下:

值得注意的是实现的方法是利用左闭右开区间还是左闭右闭区间
根据选择的不同,判断条件不同
将迭代的值带入到条件看符不符合区间要求就不会混淆二者

快慢指针题目:

本题实际上可以通过二重for循环暴力求解,复杂度是O(n^2)
但是测试过程中发现超时遂放弃

利用快慢指针在数组进行原地操作可以实现O(n)的时间复杂度

代码如下:

重点在于理解fast指向的是新数组所需的元素,slow指向的是新数组的下标
因而实际上fast只需要遍历一遍数组 然后slow在非目标值停顿一次
这样slow在遍历完成之后正好就是新数组的长度

实现过程漏掉了slow在fast赋值之后需要+1的操作 需要小心

标签:快慢,slow,随想录,fast,二分法,01,数组,指针
From: https://www.cnblogs.com/mingtiao/p/17930258.html

相关文章

  • [WC2018] 通道题解
    先考虑只有两颗树要咋做,柿子先变成\(dep_x+dep_y-2\timesdep_{lca}+dist_2(x,y)\)我们可以新建节点\(x'\rightarrowx\),边权为\(dep_x\),这样上面的式子可以看作枚举\(lca\)后,选出一个端点在不同子树中的直径,可以直接\(DP\)合并直径再考虑多了一颗树,我们可以进行边分治,枚......
  • P5513 [CEOI2013] Board 题解
    P5513容易发现,每次等价于对一个二进制数进行操作。但是这个二进制数长为\(n\),即需要高精。但是这样支持加一和减一是复杂度会退化为\(\mathcal{O}(n^2)\),有一个很正常的做法就压位,仿照bitset的做法进行操作,复杂度\(\mathcal{O}(\frac{n^2}{w})\)。这样已经可以通过了,但发......
  • 【数据结构】P4338 [ZJOI2018] 历史 题解
    P4338先考虑怎么安排崛起的先后顺序最优。但是发现好像没有一个很好的顺序去进行崛起,并且由于\(a_i\)的值域会很大,所以即使知道顺序应该也会难以进行维护。转换一下方向,正难则反。考虑每个点的贡献,但是颜色不同时只会算一次,所以要钦定是哪一个点造成的贡献。令当前考虑的点为......
  • 代码随想录算法训练营第十四天 | 二叉树理论基础,递归遍历,分别迭代遍历, 统一迭代遍历
    一、二叉树理论基础学习:1.从二叉树是否包含数值进行分类:无数值:完全二叉树和满二叉树有数值的:二叉搜索树和平衡二叉搜索树(AVL,Adelson-VelskyandLandis)。其中二叉搜索树指数值按照从小到大的顺序是左子树<根结点<右子树,平衡指的是左右子树高度差不超过12.二叉树存......
  • [NOI2015] 寿司晚宴
    P2150[NOI2015]寿司晚宴翻译一下,题目其实就是给你\(2-n\)这些数,从其中选出两个集合(可以为空),求使两个集合中的数两两互质的方案数。那么就相当于说两个集合中的数的质因数的集合不能有重合。先看前\(\%30\)的数据,\(n<=30\),里面的质因数不多,考虑状压\(DP\)。我们不妨设\(DP[i]......
  • [CTSC2018]暴力写挂题解
    我们先将柿子变成\(\frac{1}{2}(dis_{x,y}+dep_{x}+dep_{y})-dep'_{lca'}\)考虑边分治,枚举断边,我们将一个点在第二棵树上的点权看成是\(v_x=d_x+dep_x\),答案就为\(v_x+v_y+dep'_{lca'}\)对于每次边分治将分治联通块内所有点在第二棵树上的建出虚树,同时将分治联通块以分治中心......
  • 01-redis的安装和基本配置
    一、redis简介1、Redis是一款开源的,ANSIC语言编写的,高级键值(key-value)缓存和支持永久存储NoSQL数据库产品。2、Redis采用内存(In-Memory)数据集(DataSet)。3、支持多种数据类型。4、运行于大多数POSIX系统,如Linux、*BSD、OSX等。redis软件获取和帮助Redis.ioDownload......
  • P5333 [JSOI2019] 神经网络
    题面传送门本来以为\(m\)这么小是\(m\sumk_i\logk\)的NTT的,写完发现一点不用(首先我们发现,这样的图上面的一个哈密顿回路可以表示成原森林若干条链,每个点都在其中一条链上,且相邻两条链不在同一棵树上。先跑一个DP把\(f_{i,j}\)表示用\(j\)条链覆盖\(i\)的方案数......
  • [SNOI2019] 网络 题解
    [SNOI2019]网络题解最喜欢这道题。简要题意给一颗\(n\)个节点的树和一个参数\(d\),定义两个节点\(x,y\)之间的距离为\(x\)到\(y\)的简单路径上的边数。定义一个树上连通块的权值为连通块中任意两点的距离之和。定义一个树上连通块的直径为连通块中任意两点距离的最......
  • java接口自动化系列(01):自动化测试框架设计(入门版)
     前言想必很多测试小伙伴自动化都是用的python吧?从当前测试招聘要求可以看到,测试开发就是全栈要求,要想在职场有竞争力,就得多个技术方向逐个提升;而和自动化、测开、性能、白盒等都相关的语言就是java,当然,这是基于很多公司项目是java来说的,毕竟Java已经发展了近20年,丰富的周边框架打......