一些可以让你装逼、让人眼前一亮的算法技巧总结
xsobi 2024-11-23 10:50 1 浏览
一些可以让你装逼、让人眼前一亮的算法技巧总结
今天和大家讲讲,在做算法题时常用的一些技巧。对于平时没用过这些技巧的人,或许你可以考虑试着去看看在实践中能否用的上这些技巧来优化问题的解,相信一定会让你有所收获,不然你看我。
1. 巧用数组下标
数组的下标是一个隐含的很有用的数组,特别是在统计一些数字,或者判断一些整型数是否出现过的时候。例如,给你一串字母,让你判断这些字母出现的次数时,我们就可以把这些字母作为下标,在遍历的时候,如果字母a遍历到,则arr[a]就可以加1了,即 arr[a]++;
通过这种巧用下标的方法,我们不需要逐个字母去判断。
我再举个例子:
问题:给你n个无序的int整型数组arr,并且这些整数的取值范围都在0-20之间,要你在 O(n) 的时间复杂度中把这 n 个数按照从小到大的顺序打印出来。
对于这道题,如果你是先把这 n 个数先排序,再打印,是不可能O(n)的时间打印出来的。但是数值范围在 0-20。我们就可以巧用数组下标了。把对应的数值作为数组下标,如果这个数出现过,则对应的数组加1。 代码如下:
public void f(int arr[]) { int[] temp = new int[21]; for (int i = 0; i < arr.length; i++) { temp[arr[i]]++; } //顺序打印 for (int i = 0; i < 21; i++) { for (int j = 0; j < temp[i]; j++) { System.out.println(i); } } } 复制代码
利用数组下标的应用还有很多,大家以后在遇到某些题的时候可以考虑是否可以巧用数组下标来优化。
2. 巧用取余
有时候我们在遍历数组的时候,会进行越界判断,如果下标差不多要越界了,我们就把它置为0重新遍历。特别是在一些环形的数组中,例如用数组实现的队列。往往会写出这样的代码:
for (int i = 0; i < N; i++) { if (pos < N) { //没有越界 // 使用数组arr[pos] else { pos = 0;//置为0再使用数组 //使用arr[pos] } pos++; } 复制代码
实际上我们可以通过取余的方法来简化代码
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。因此我们可以很容易写出递归的代码
public 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) 的递归,是有很多重复计算的。如
就有很多重复计算了。这个时候我们要考虑状态保存。例如用hashMap来进行保存,当然用一个数组也是可以的,这个时候就像我们上面说的巧用数组下标了。可以当arr[n] = 0时,表示n还没计算过,当arr[n] != 0时,表示f(n)已经计算过,这时就可以把计算过的值直接返回回去了。因此我们考虑用状态保存的做法代码如下:
//数组的大小根据具体情况来,由于int数组元素的的默认值是0 //因此我们不用初始化 int[] arr = new int[1000]; public int f(int n) { if (n <= 2) { return n; } else { if (arr[n] != 0) { return arr[n];//已经计算过,直接返回 } else { arr[n] = f(n-1) + f(n-2); return arr[n]; } } } 复制代码
这样,可以极大着提高算法的效率。也有人把这种状态保存称之为备忘录法。
(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)。因此,我们可以考虑使用自底向上的方法来做。
代码如下:
public int f(int n) { if(n <= 2) return n; int f1 = 1; int f2 = 2; int sum = 0; for (int i = 3; i <= n; i++) { sum = f1 + f2; f1 = f2; f2 = sum; } return sum; } 复制代码
我们也把这种自底向上的做法称之为递推。
总结一下
当你在使用递归解决问题的时候,要考虑以下两个问题
(1). 是否有状态重复计算的,可不可以使用备忘录法来优化。
(2). 是否可以采取递推的方法来自底向上做,减少一味递归的开销。
如果你觉得这篇内容对你挺有启发,那么你可以:
1、点赞,让更多的人也能看到这篇内容(收藏不点赞,都是耍流氓 -_-)
2、*关注我,让我们成为长期关系。
3、关注公众号「苦逼的码农」,里面已有100多篇原创文章,我也分享了很多视频、书籍的资源,以及开发工具,欢迎各位的参考文献:K码农-http://kmanong.top/kmn/qxw/form/home?top_cate=28
- 上一篇:位运算实现加减法
- 下一篇:杭州Java培训入门技术点:位移运算符
相关推荐
- js向对象中添加元素(对象,数组) js对象里面添加元素
-
一、添加一个元素对象名["属性名"]=值(值:可以是一个值,可以是一个对象,也可以是一个数组)这样添加进去的元素,就是一个值或对象或数组...
- JS小技巧,如何去重对象数组?(一)
-
大家好,关于数组对象去重的业务场景,想必大家都遇到过类似的需求吧,这对这样的需求你是怎么做的呢。下面我就先和大家分享下如果是基于对象的1个属性是怎么去重实现的。方法一:使用.filter()和....
- 「C/C++」之数组、vector对象和array对象的比较
-
数组学习过C语言的,对数组应该都不会陌生,于是这里就不再对数组进行展开介绍。模板类vector模板类vector类似于string,也是一种动态数组。能够在运行阶段设置vector对象的长度,可以在末...
- 如何用sessionStorage保存对象和数组
-
背景:在工作中,我将[{},{}]对象数组形式,存储到sessionStorage,然后ta变成了我看不懂的形式,然后我想取之用之,发现不可能了~记录这次深刻的教训。$clickCouponIndex...
- JavaScript Array 对象 javascript的array对象
-
Array对象Array对象用于在变量中存储多个值:varcars=["Saab","Volvo","BMW"];第一个数组元素的索引值为0,第二个索引值为1,以此类推。更多有...
- JavaScript中的数组Array(对象) js array数组
-
1:数组Array:-数组也是一个对象-数组也是用来存储数据的-和object不同,数组中可以存储一组有序的数据,-数组中存储的数据我们称其为元素(element)-数组中的每一个元素都有一...
- 数组和对象方法&数组去重 数组去重的5种方法前端
-
列举一下JavaScript数组和对象有哪些原生方法?数组:arr.concat(arr1,arr2,arrn);--合并两个或多个数组。此方法不会修改原有数组,而是返回一个新数组...
- C++ 类如何定义对象数组?初始化数组?linux C++第43讲
-
对象数组学过C语言的读者对数组的概念应该很熟悉了。数组的元素可以是int类型的变量,例如int...
- ElasticSearch第六篇:复合数据类型-数组,对象
-
在ElasticSearch中,使用JSON结构来存储数据,一个Key/Value对是JSON的一个字段,而Value可以是基础数据类型,也可以是数组,文档(也叫对象),或文档数组,因此,每个JSON...
- 第58条:区分数组对象和类数组对象
-
示例设想有两个不同类的API。第一个是位向量:有序的位集合varbits=newBitVector;bits.enable(4);bits.enable([1,3,8,17]);b...
- 八皇后问题解法(Common Lisp实现)
-
如何才能在一张国际象棋的棋盘上摆上八个皇后而不致使她们互相威胁呢?这个著名的问题可以方便地通过一种树搜索方法来解决。首先,我们需要写一个函数来判断棋盘上的两个皇后是否互相威协。在国际象棋中,皇后可以沿...
- visual lisp修改颜色的模板函数 怎么更改visual studio的配色
-
(defunBF-yansemokuai(tuyuanyanse/ss)...
- 用中望CAD加载LISP程序技巧 中望cad2015怎么加载燕秀
-
1、首先请加载lisp程序,加载方法如下:在菜单栏选择工具——加载应用程序——添加,选择lisp程序然后加载,然后选择添加到启动组。2、然后是添加自定义栏以及图标,方法如下(以...
- 图的深度优先搜索和广度优先搜索(Common Lisp实现)
-
为了便于描述,本文中的图指的是下图所示的无向图。搜索指:搜索从S到F的一条路径。若存在,则以表的形式返回路径;若不存在,则返回nil。...
- 两个有助于理解Common Lisp宏的例子
-
在Lisp中,函数和数据具有相同的形式。这是Lisp语言的一个重大特色。一个Lisp函数可以分析另一个Lisp函数;甚至可以和另一个Lisp函数组成一个整体,并加以利用。Lisp的宏,是实现上述特色的...
- 一周热门
- 最近发表
- 标签列表
-
- grid 设置 (58)
- 移位运算 (48)
- not specified (45)
- patch补丁 (31)
- strcat (25)
- 导航栏 (58)
- context xml (46)
- scroll (43)
- element style (30)
- dedecms模版 (53)
- vs打不开 (29)
- nmap (30)
- webgl开发 (24)
- parse (24)
- c 视频教程下载 (33)
- android 开发环境 (24)
- paddleocr (28)
- listview排序 (33)
- firebug 使用 (31)
- transactionmanager (30)
- characterencodingfilter (33)
- getmonth (34)
- commandtimeout (30)
- hibernate教程 (31)
- label换行 (33)