老大爷

老大爷

好好滴写代码,不要想那么多,钱钱会有的

标签: 算法 (2)

小灰算法(二): 可能是小学老师没教你的最大公约数算法


  最大公约数是我们在小学都学过的,是最基本的数学知识,基本的我们都没有怀疑过它是否有更好的方法去计算。因为笔者当年的老师教我们从最小的数一直往上试,看看能不能同时被这俩整数整除,一直循环下去就能计算出最大公约数了。比如求10和25的最大公约数,大家或许会先试2,发现不是。然后试3,然后4…,一直到5。10/5=2,25/5=5. 2和5已经没有共同可分解的因数了。所以最大公约数是5. 如果用代码来写,可能会稍微有些不同,但是基本思路也是用一个循环去试出来最大的公约数。时间复杂度为O(N).

小灰算法(一): 快慢指针求解链表是否有环

单向有环链表

如图是一个有环的单向链表,那么我们如何判断一个单向链表有环?会被大家常想到的方法是穷举遍历或者借助一个hashSet来判断。
穷举的时间复杂度是O(N*N),借助hashSet的时间复杂度是O(N),空间复杂度是O(N)。

所以我们今天来介绍一种稍微更优的算法来求解单向链表是否有环。首先我们使用两个指针p1和p2指向链表头结点。
然后让p1以速度1向后移动,p2以速度2向后移动。如果两个指针会相遇,则表示此链表有环。