感谢微信公众号“算法爱好者”,以及该漫画系列的出处“程序员小灰”

这里会长期小灰每一期的学习感悟总结。



* 算法系列 <https://blog.csdn.net/nakiri_arisu/article/details/79341527#算法系列>
* 最小栈实现 <https://blog.csdn.net/nakiri_arisu/article/details/79341527#最小栈实现>
* 判断2的乘方 <https://blog.csdn.net/nakiri_arisu/article/details/79341527#判断2的乘方>
* 找出缺失的整数
<https://blog.csdn.net/nakiri_arisu/article/details/79341527#找出缺失的整数>
* 辗转相除法是什么鬼
<https://blog.csdn.net/nakiri_arisu/article/details/79341527#辗转相除法是什么鬼>
* Bitmap 算法
<https://blog.csdn.net/nakiri_arisu/article/details/79341527#bitmap-算法>


算法系列

漫画算法:什么是动态规划?(整合版)
漫画算法:什么是跳跃表?
漫画算法:什么是 B 树?
漫画算法:什么是 B+ 树?
漫画算法:什么是一致性哈希?
漫画算法:无序数组排序后的最大相邻差值
漫画算法:什么是布隆算法?
漫画算法:什么是 A* 寻路算法?
漫画算法:什么是 Base64 算法?
漫画算法:什么是 MD5 算法?
漫画算法:如何破解 MD5 算法?
漫画算法:什么是 SHA 系列算法?
漫画算法:什么是 AES 算法?
漫画算法:AES 算法的底层原理
漫画算法:什么是红黑树?

最小栈实现

题目: 实现一个栈,带有出栈(pop),入栈(push),取最小元素(getMin)三个方法。要保证这三个方法的时间复杂度都是O(1)。

原链接: https://mp.weixin.qq.com/s/n2QA0q_NGDcnrg6a50fy9Q
<https://mp.weixin.qq.com/s/n2QA0q_NGDcnrg6a50fy9Q>

方法一: 设置两个Stack,一个Stack正常出栈入栈。另一个Stack用来辅助存储最小元素stackMin。
stackMin第一个元素正常入栈,之后入栈的元素和stackMin栈顶的元素相比,若小于等于
(等于这个条件非常关键,想想为什么)则入stackMin。getMin直接返回stackMin栈顶元素(peek)。pop的时候如果Stack栈顶的值等于最小值,则双Stack同步pop。

这个方法也是该文章中的思想(虽然文章中辅助栈存的是下标,毕竟用数组实现的)

方法二: 与方法一略有不同,区别在于每次入栈的时候stackMin都会判断入栈元素是否小于
等于(这里的等于就可有可无)栈顶元素,如果符合入栈,不符合的话将stackMin栈顶已有的元素重复入自身栈顶。
这样做的好处在于,出栈的时候非常方便,直接同步双栈pop就行了。除了非空,不需要做任何多余的判断。

这里为了省事,就用Stack来实现了。
要看数组实现栈的话,单独另写
数组实现栈的基本操作 <https://blog.csdn.net/nakiri_arisu/article/details/79341527>

方法一: 入栈方便,出栈复杂
public class StackPro{ private Stack<Integer> storeData; private
Stack<Integer> storeMin;public StackPro(){ storeData = new Stack<Integer>();
storeMin =new Stack<Integer>(); } public void push(Integer item){ if
(storeMin.isEmpty()){ storeMin.push(item); }else if(item<=storeMin.peek()){
storeMin.push(item); } storeData.push(item); }public Integer pop(){ if
(storeData.isEmpty())throw new RuntimeException("Your stack is Empty!"); if
(storeData.peek()==getMin()){//minStack的判断在getMin()里进行 storeMin.pop(); } return
storeData.pop(); }public Integer getMin(){ if(storeMin.isEmpty()) throw new
RuntimeException("Your stack is Empty"); return storeMin.peek(); } }
方法二: 入栈复杂,出栈方便。需要的空间较大
/** 只需要相应改写push和pop方法就行了,其他的省略 **/ public void push(Integer item){ if
(storeMin.isEmpty()){ storeMin.push(item); }else{ if(item<storeMin.peek()){
storeMin.push(item); }else{ storeMin.push(storeMin.peek()); } }
storeData.push(item); }public Integer pop(){ if(storeData.isEmpty()) throw new
RuntimeException("Your stack is Empty!"); storeMin.pop(); return
storeData.pop(); }
这道题的启发就是: 巧妙利用辅助空间完成功能。

判断2的乘方

题目:实现一个方法,判断一个正整数是否是2的乘方(比如16是2的4次方,返回True;18不是2的乘方,返回False)。要求性能尽可能高。

最容易想到的就是设置一个中间量,然后让该值从1开始不断乘以2和target进行比较,如果小于就继续乘以2,如果==返回true。如果大于则直接返回false。
public boolean is2Fang(int target){ int tmp = 1; while(tmp<=target){ if
(tmp==target)return true; else tmp<<=1; } return false; }
虽然这样的方法的时间复杂度也能够达到O(lgn)级别,但仍然不是最快的。

改进: 利用2的整数次幂数的特性,以及位运算。
public boolean is2FangPro(int target){ return 0==(target&target-1);
//由于运算符优先级关系,target-1不需要括号 }
推导过程略,因为太简单了..

找出缺失的整数

题目: 一个无序数组里有99个不重复正整数,范围从1到100,唯独缺少一个整数。如何找出这个缺失的整数?

这道题目的解法真的是非常非常多啊。。。
先说一个不咋样的是我条件反射想到的。
方法零:

利用bitMap的思想,建立一个100长度的数组初始为0,如果来一个95就将下标为94的格子涂黑(赋值1)..
public int getLackNum(int [] arr){ int [] bitMap = new int[100]; //100个0 for(
int j=0;j<arr.length;j++){ bitMap[arr[j]-1]=1; //存在100则把下标为99的格子染黑 } for(int x=0
;x<100;x++){ if(1!=bitMap[x]) return x+1; } return -1; //找不到返回-1 }
再谈谈文章中的方法。
方法一:

创建一个HashMap,以1到100为键,值都是0 。然后遍历整个数组,每读到一个整数,就找到HashMap当中对应的键,让其值加一。
由于数组中缺少一个整数,最终一定有99个键对应的值等于1, 剩下一个键对应的值等于0。遍历修改后的HashMap,找到这个值为0的键。

我个人不是很青睐这种方法,设置hashMap还行,最后遍历hashMap太蠢了。。 不过我还是代码实现以下…
public int getLackNum(int [] arr){ Map<Integer,Integer> map = new
HashMap<Integer,Integer>();for(int i=1;i<=100;i++){ map.put(i, 0); } //初始化map
for(int x : arr){ //涂黑 map.put(x,1); } Iterator<Entry<Integer,Integer>> it =
map.entrySet().iterator();while(it.hasNext()){ Map.Entry<Integer, Integer>
entry = it.next(); Integer key = entry.getKey(); Integer value =
entry.getValue();if(value==0) return key; } return -1; }
方法二:

将无序数组排序,然后看相邻元素是否连续,找到首个不连续的位置返回坐标 (依赖于题目的100个数只差一个)
public int getLackNum(int [] arr){ Arrays.sort(arr); for(int i=1
;i<arr.length;i++){if((arr[i]-arr[i-1])!=1) return arr[i-1]+1; } return -1; }
方法三: 也是该问题的最优解

将无序数组相加减去1-100的和… 大道至简

有些无聊… 就不讨论了
public int getLackNum(int [] arr){ int sum = 5050; for(int i=0
;i<arr.length;i++){ sum-=arr[i]; }return sum; }
题目扩展1:


一个无序数组里有若干个正整数,范围从1到100,其中99个整数都出现了偶数次,只有一个整数出现了奇数次(比如1,1,2,2,3,3,4,5,5),如何找到这个出现奇数次的整数?

思路:
我条件反射的想到的是利用bitMap,出现的涂黑,再出现涂白。这样最后奇数次的就是黑的。。

不过有更高端更省事的方法。

依次对数组中所有的数进行亦或
public int getLackNum(int [] arr){ int result = 0; //根据亦或的规律 for(int i=0
;i<arr.length;i++) result = result^arr[i];return result; }
题目扩展2:


一个无序数组里有若干个正整数,范围从1到100,其中98个整数都出现了偶数次,只有两个整数出现了奇数次(比如1,1,2,2,3,4,5,5),如何找到这个出现奇数次的整数?

思路:

这里用bitMap相对更简单一些,反而是文章中的分治法我觉得较为麻烦
public int[] getLackNum(int[] arr) { int [] result = new int[2]; //结果集 int []
bitMap =new int[100]; //无序数组全量表长度 for (int n : arr) { bitMap[n - 1] = bitMap[n -
1] == 1 ? 0 : 1; } int index = 0; for(int i=0;i<bitMap.length;i++){ if
(bitMap[i]==1) result[index++] = i+1; if(index == 2) return result; } return
result; }
辗转相除法是什么鬼?

这条算法基于一个定理:两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。

如何求两个数的最大公约数

辗转相除法很经典,毕竟欧几里得算法。需记忆,相反我倒是觉得暴力枚举很需要动脑子(捂脸)

辗转相除法:
public int gcb(int a, int b) { if(a==b) return a; if(a<b) return gcd(b,a);
return gcd(b,a%b); }
辗转相除法的好处在于,如果出现1001和1000这样的,只需两次就能发现这俩的公约数为1。 第一次1001%1000 = 1, 1000%1 = 0。
return 1。 于是1001和1000的最大公约数为1。

更相减损术:
思路: 当两个整形数较大的时候,取模效率较低。

更相减损术, 出自于中国古代的《九章算术》,也是一种求最大公约数的算法。

他的原理更加简单:
两个正整数a和b(a>b),它们的最大公约数等于a-b的差值c和较小数b的最大公约数。比如10和25,25减去10的差是15,那么10和25的最大公约数,等同于10和15的最大公约数。
public static int gcb(int a,int b){ if(a==b) return a; if(a<b) return gcd(b,a);
return gcd(b,a-b); }
但这种算法不适用于类似 (10000,1)这样差距很大的组合。明显公约数是1,但却需要递减999次。

众所周知,移位运算的性能非常快。对于给定的正整数a和b,不难得到如下的结论。其中gcb(a,b)的意思是a,b的最大公约数函数:
当a和b均为偶数,gcb(a,b) = 2*gcb(a/2, b/2) = 2*gcb(a>>1, b>>1)
当a为偶数,b为奇数,gcb(a,b) = gcb(a/2, b) = gcb(a>>1, b)
当a为奇数,b为偶数,gcb(a,b) = gcb(a, b/2) = gcb(a, b>>1)
当a和b均为奇数,利用更相减损术运算一次,gcb(a,b) = gcb(b, a-b), 此时a-b必然是偶数,又可以继续进行移位运算。

利用上面的规律,对更相减损术进行优化。

更相减损术优化:
/** 同时利用 &1运算来判断奇数偶数。 */ public static int gcd(int a, int b) { if(a==b) return
b;if(a<b){ return gcd(b,a); }else{ if((a&1)==0&&(b&1)==0) return gcd(a>>1,b>>1
)<<1; //关键点 不然结果会小2的N次幂 else if((a&1)==0&&(b&1)==1) return gcd(a>>1,b); else if
((a&1)==1&&(b&1)==0) return gcd(a,b>>1); else return gcd(b,a-b); } }
结论:
1. 暴力枚举法:时间复杂度是O(min(a, b)))
2. 辗转相除法:时间复杂度不太好计算,可以近似为O(log(max(a, b))),但是取模运算性能较差。
3. 更相减损术:避免了取模运算,但是算法性能不稳定,最坏时间复杂度为O(max(a, b)))
4. 更相减损术与移位结合:不但避免了取模运算,而且算法性能稳定,时间复杂度O(log(max(a, b)))

Bitmap 算法

公众号里关于这个讲了不少。我个人觉得bitMap不是一个具体的算法,而是一种思想,一个模型。


你可以理解为有一个长度为N的数组,数组里的每一个值只有两种情况0或1,或者是true和false。为了简化,我们这里就假设这个数组只有0或1的情况,初始都是0。然后我们根据情况将对应的位置染黑。
这就是bitMap,每一个位置大小都是一个bit.

应用这个思想可以解决很多问题,比如著名的布隆过滤器。

EWAHCompressedBitmap


https://mp.weixin.qq.com/s?__biz=MzI1MTIzMzI2MA==&mid=2650561333&idx=1&sn=654c214c204c708e7a9d559cec12c69e&chksm=f1feedb6c68964a0add2fa32ce209c59e344aa93fc6fd3682875e42f215e13eac83f4ff08682&scene=21#wechat_redirect

<https://mp.weixin.qq.com/s?__biz=MzI1MTIzMzI2MA==&mid=2650561333&idx=1&sn=654c214c204c708e7a9d559cec12c69e&chksm=f1feedb6c68964a0add2fa32ce209c59e344aa93fc6fd3682875e42f215e13eac83f4ff08682&scene=21#wechat_redirect>