一些可以装逼的算法技巧总结!值得拥有简单实用算法思想
xsobi 2024-11-23 10:51 18 浏览
今天和大家讲讲,在做算法题时常用的一些技巧。对于平时没用过这些技巧的人,或许你可以考虑试着去看看在实践中能否用的上这些技巧来优化问题的解。
1. 巧用数组下标 数组的下标是一个隐含的很有用的数组,特别是在统计一些数字,或者判断一些整型数是否出现过的时候。例如,给你一串字母,让你判断这些字母出现的次数时,我们就可以把这些字母作为下标,在遍历的时候,如果字母a遍历到,则arr[a]就可以加1了,即 arr[a]++; 通过这种巧用下标的方法,我们不需要逐个字母去判断。
我再举个例子: 问题:给你n个无序的int整型数组arr,并且这些整数的取值范围都在0-20之间,要你在 O(n) 的时间复杂度中把这 n 个数按照从小到大的顺序打印出来。 对于这道题,如果你是先把这 n 个数先排序,再打印,是不可能O(n)的时间打印出来的。但是数值范围在 0-20。我们就可以巧用数组下标了。把对应的数值作为数组下标,如果这个数出现过,则对应的数组加1。 代码如下:
编辑切换为居中
添加图片注释,不超过 140 字(可选)
利用数组下标的应用还有很多,大家以后在遇到某些题的时候可以考虑是否可以巧用数组下标来优化.
2. 巧用取余 有时候我们在遍历数组的时候,会进行越界判断,如果下标差不多要越界了,我们就把它置为0重新遍历。特别是在一些环形的数组中,例如用数组实现的队列。往往会写出这样的代码:
?
编辑切换为居中
添加图片注释,不超过 140 字(可选)
实际上我们可以通过取余的方法来简化代码 for (int i = 0; i < N; i++) { //使用数组arr[pos] (我们假设刚开始的时候pos < N) pos = (pos + 1) % N; }
3. 巧用双指针 对于双指针,在做关于单链表的题是特别有用,比如“判断单链表是否有环”、“如何一次遍历就找到链表中间位置节点”、“单链表中倒数第 k 个节点”等问题。对于这种问题,我们就可以使用双指针了,会方便很多。我顺便说下这三个问题怎么用双指针解决吧。
例如对于第一个问题 我们就可以设置一个慢指针和一个快指针来遍历这个链表。慢指针一次移动一个节点,而快指针一次移动两个节点,如果该链表没有环,则快指针会先遍历完这个表,如果有环,则快指针会在第二次遍历时和慢指针相遇。
对于第二个问题 一样是设置一个快指针和慢指针。慢的一次移动一个节点,而快的两个。在遍历链表的时候,当快指针遍历完成时,慢指针刚好达到中点。
对于第三个问题 设置两个指针,其中一个指针先移动k个节点。之后两个指针以相同速度移动。当那个先移动的指针遍历完成的时候,第二个指针正好处于倒数第k个节点。 你看,采用双指针方便多了吧。所以以后在处理与链表相关的一些问题的时候,可以考虑双指针哦。
4. 巧用移位运算 有时候我们在进行除数或乘数运算的时候,例如n / 2,n / 4, n / 8这些运算的时候,我们就可以用移位的方法来运算了,这样会快很多。 例如: n / 2 等价于 n >> 1 n / 4 等价于 n >> 2 n / 8 等价于 n >> 3。 这样通过移位的运算在执行速度上是会比较快的,也可以显的你很厉害的样子,哈哈。 还有一些 &(与)、|(或)的运算,也可以加快运算的速度。例如判断一个数是否是奇数,你可能会这样做 if(n % 2 == 1){ dosomething(); } 不过我们用与或运算的话会快很多。例如判断是否是奇数,我们就可以把n和1相与了,如果结果为1,则是奇数,否则就不会。即if(n & 1 == 1){ dosomething(); ) 具体的一些运算技巧,还得需要你们多在实践中尝试着去使用,这样用久后就会比较熟练了。
5. 设置哨兵位 在链表的相关问题中,我们经常会设置一个头指针,而且这个头指针是不存任何有效数据的,只是为了操作方便,这个头指针我们就可以称之为哨兵位了。 例如我们要删除头第一个节点是时候,如果没有设置一个哨兵位,那么在操作上,它会与删除第二个节点的操作有所不同。但是我们设置了哨兵,那么删除第一个节点和删除第二个节点那么在操作上就一样了,不用做额外的判断。当然,插入节点的时候也一样。 有时候我们在操作数组的时候,也是可以设置一个哨兵的,把arr[0]作为哨兵。例如,要判断两个相邻的元素是否相等时,设置了哨兵就不怕越界等问题了,可以直接arr[i] == arr[i-1]?了。不用怕i = 0时出现越界。 当然我这只是举一个例子,具体的应用还有很多,例如插入排序,环形链表等。
6. 与递归有关的一些优化 (1).对于可以递归的问题考虑状态保存 当我们使用递归来解决一个问题的时候,容易产生重复去算同一个子问题,这个时候我们要考虑状态保存以防止重复计算。例如我随便举一个之前举过的问题
问题:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法? 这个问题用递归很好解决。假设 f(n) 表示n级台阶的总跳数法,则有 f(n) = f(n-1) + f(n - 2)。 递归的结束条件是当0 <= n <= 2时, f(n) = n。因此我们可以很容易写出递归的代码 int f(int n) { if (n <= 2) { return n; } else { return f(n - 1) + f(n - 2); } } 不过对于可以使用递归解决的问题,我们一定要考虑是否有很多重复计算。显然对于 f(n) = f(n-1) + f(n-2) 的递归,是有很多重复计算的。如
?
编辑切换为居中
添加图片注释,不超过 140 字(可选)
就有很多重复计算了。这个时候我们要考虑状态保存。例如用hashMap来进行保存,当然用一个数组也是可以的,这个时候就像我们上面说的巧用数组下标了。可以当arr[n] = 0时,表示n还没计算过,当arr[n] != 0时,表示f(n)已经计算过,这时就可以把计算过的值直接返回回去了。因此我们考虑用状态保存的做法代码如下:
?
编辑切换为居中
添加图片注释,不超过 140 字(可选)
这样,可以极大着提高算法的效率。也有人把这种状态保存称之为备忘录法。 (2).考虑自底向上 对于递归的问题,我们一般都是从上往下递归的,直到递归到最底,再一层一层着把值返回。 不过,有时候当n比较大的时候,例如当 n = 10000时,那么必须要往下递归10000层直到 n <=2 才将结果慢慢返回,如果n太大的话,可能栈空间会不够用。 对于这种情况,其实我们是可以考虑自底向上的做法的。例如我知道 f(1) = 1; f(2) = 2; 那么我们就可以推出 f(3) = f(2) + f(1) = 3。从而可以推出f(4),f(5)等直到f(n)。因此,我们可以考虑使用自底向上的方法来做。 代码如下:
?
编辑切换为居中
添加图片注释,不超过 140 字(可选)
我们也把这种自底向上的做法称之为递推。
总结一下
当你在使用递归解决问题的时候,要考虑以下两个问题
是否有状态重复计算的,可不可以使用备忘录法来优化。
是否可以采取递推的方法来自底向上做,减少一味递归的开销。
我的C/C++编程学习基地:点击正在跳转即可加入,欢迎大家一起来学习交流嗷~
- 上一篇:C语言中的位运算符
- 下一篇:算法 | 位运算实现乘除
相关推荐
- 大模型技术:详解LangGraph,从基础到高级
-
图片来自DALL-E3LangChain是构建由Lardge语言模型提供支持的应用程序的领先框架之一。借助LangChain表达语言(LCEL),定义和执行分步操作序列(也称为链)变得更加简...
- SQL知识大全三):SQL中的字符串处理和条件查询
-
点击上方蓝字关注我们今天是SQL系列的第三讲,我们会讲解条件查询,文本处理,百分比,行数限制,格式化以及子查询。条件查询IF条件查询#if的语法IF(expr1,expr2,expr3)#示例S...
- 聊聊Spring AI Alibaba的PdfTablesParser
-
序本文主要研究一下SpringAIAlibaba的PdfTablesParserPdfTablesParsercommunity/document-parsers/spring-ai-alibab...
- SpringBoot数据库管理 - 用Liquibase对数据库管理和迁移?
-
Liquibase是一个用于用于跟踪、管理和应用数据库变化的开源工具,通过日志文件(changelog)的形式记录数据库的变更(changeset),然后执行日志文件中的修改,将数据库更新或回滚(ro...
- MySQL合集-单机容器化
-
MySQL单机容器化mkdir-p/opt/mysql/{data,etc}cpmy.cnf/opt/mysql/etc#dockersearchmysqldockerpullm...
- 差异基因分析不会做?最简单的火山图做法,一秒学会
-
最近很多刚了解生信的同学问喵学姐:看了一些文献,文献里的各种图怎么看呀,完全看不懂。今天喵学姐就来给大家讲一讲我们平时做的最基础的差异分析——火山图火山图(Volcanoplot)是散点图的一种,它...
- 每分钟写入6亿条数据,携程监控系统Dashboard存储升级实践
-
一、背景概述框架Dashboard是一款携程内部历史悠久的自研监控产品,其定位是企业级Metrics监控场景,主要提供用户自定义Metrics接入,并基于此提供实时数据分析和视图展现的面板服务,提供...
- 高效开发库:C++ POCO库开发者使用指南
-
目录POCO库简介POCO库的特点POCO库的模块分类POCO库的应用场景各模块功能详解与代码示例1.POCO库简介POCO(PortableComponents)是一个开源的C++类库,旨在为开...
- Oracle中JDBC处理PreparedStatement处理Char问题浅析
-
最近碰到一个奇怪的问题,同样的Java代码,在不同的数据库执行,结果集却不同?代码片段如下:表的定义:SAMPLE_TABLE(IDINTEGER,NAMECH...
- mp4封装格式各box类型讲解及IBP帧计算
-
mp4封装格式各box类型讲解及IBP帧计算目录;总结送学习大纲零基础到实战boxftypboxmoovboxmvhdbox(MovieHeaderBox)trakbox(Track...
- 「猪译馆」ASFV在不同基质中的存活时间(一)
-
作者Author欧洲食品安全署EuropeanFoodSafetyAuthority(EFSA),AndreaGervelmeyer欧盟委员会委托欧洲食品安全署对非洲猪瘟病毒在不同基质中...
- 视频封装格式:MP4格式详解
-
1.MP4格式概述1.1简介MP4或称MPEG-4第14部分(MPEG-4Part14)是一种标准的数字多媒体容器格式。扩展名为.mp4。虽然被官方标准定义的唯一扩展名是.mp4,但第三方通...
- 音视频八股文(10)-- mp4结构
-
介绍mp4文件格式又被称为MPEG-4Part14,出自MPEG-4标准第14部分。它是一种多媒体格式容器,广泛用于包装视频和音频数据流、海报、字幕和元数据等。(顺便一提,目前流行的视频编码格式...
- 大数据ClickHouse进阶(九):ClickHouse的From和Sample子句
-
#头条创作挑战赛#ClickHouse的From和Sample子句一、From子句From子句表示从何处读取数据,支持2种形式,由于From比较简单,这里不再举例,2种使用方式如下:SELECTcl...
- 一文读懂MP4封装格式
-
简介MP4或称MPEG-4第14部分(MPEG-4Part14)是一种标准的数字多媒体容器格式。扩展名为.mp4。虽然被官方标准定义的唯一扩展名是.mp4,但第三方通常会使用各种扩展名来指示文件的...
- 一周热门
- 最近发表
- 标签列表
-
- grid 设置 (58)
- 移位运算 (48)
- not specified (45)
- 导航栏 (58)
- context xml (46)
- scroll (43)
- dedecms模版 (53)
- c 视频教程下载 (33)
- listview排序 (33)
- characterencodingfilter (33)
- getmonth (34)
- label换行 (33)
- android studio 3 0 (34)
- html转js (35)
- 索引的作用 (33)
- checkedlistbox (34)
- xmlhttp (35)
- mysql更改密码 (34)
- 权限777 (33)
- htmlposition (33)
- 学校网站模板 (34)
- textarea换行 (34)
- 轮播 (34)
- asp net三层架构 (38)
- bash (34)