来自《漫画算法》一书，记录下有用东西供自己查阅。
1.如何判断单链表有环
设置两个指针，初始时都在链表开头，一个指针每次移动一个位置，另一个每次移动两个位置，如果链表有环，那么这两个指针会在某个位置指向同一个节点。这与追击相遇问题很类似，一个环形跑道上，一个人跑的快一个人跑的慢，两个人出发总会相遇。
这种求是否有环的时间复杂度为O(n)，空间复杂度为O(1)。
如何求环长
https://blog.csdn.net/ying_an/article/details/106176348
以上是一个解决思路。
也就是如果按照前面的判断单链表有环了，那么接着让两个指针前进，直到下一次相遇，中间走过的步数就是环长。
求入环节点
还是如果有环，那么将一个指针移到链表开头位置，两者都每次移动一个节点，下一次相遇的位置就是入环位置。
2.最小栈的实现
实现个栈，该栈有入栈(push)、出栈(pop)、取最小元素(getMin)3个方法。要保证这三个方法的时间复杂度都是O(1)。
https://blog.csdn.net/weixin_41951281/article/details/102483971
解决思路创建栈的同时创建一个最小栈，每次栈入栈后元素都与最小栈栈顶元素进行比较，如果比最小栈栈顶元素小，那么这个元素也进入最小栈，每次弹出后都将弹出元素与最小栈栈顶元素比较，如果相同，那么最小栈栈顶元素也弹出。getMin每次返回最小栈栈顶元素。
3.求最大公约数
辗转相除法
算法基于的原理：两个正整数a和b（a>b），他们的最大公约数等于a除以b的余数c和b之间的最大公约数。
更相减损术
两个正整数a和b（a>b），他们的最大公约数等于a-b的差值c和较小数b的最大公约数。
但是这两个算法性能都不算优秀，要结合两者的优点。
https://blog.csdn.net/qq_44344649/article/details/88322678
里面一个算法是结合两者优点。
求a和b的最大公约数
如果a和b都为偶数，a和b的最大公约数等于2乘以a/2和b/2的最大公约数
如果a和b有一个为奇数，那么a和b的最大公约数等于a和b中偶数除以2后与另一个数的最大公约数
如果a和b都为奇数，先用更相减损术运算一次，若为0则表示已找到最大公约数，否则a和b的最大公约数等于a-b的差值(这必然是一个偶数)与a和b中较小数的最大公约数
按照这个步骤就可以很快找到最大公约数。为什么是2因为除以2可以使用移位运算效率高。
4.如何判断一个数是否为2的整数次幂
2的整数次幂表现为二进制是1开头后面都是0，减1之后都变为1，利用这个特点，假如一个数n与n-1按位“与”之后是0，那么这个是数n就是2的整数倍。
5.无序数组的最大相邻差
一种最简单的思路是先排序然后求最大相邻差，这样做即使选择时间复杂度为O(nlogn)的算法也不够最快。且这样的思路就是错的，这道题不是排序问题。
解法1：借助计数排序的思想，将数值计数排序后，取0值出现最多的次数两端的数组下标相减即可得到最大相邻差，但是当元素差值大的时候创建数组的长度过大。
计数排序参考：https://www.cnblogs.com/kyoner/p/10604781.html
解法2：借助桶排序的思想，但是不需要得到每个桶内的顺序，只需知道每个桶内的最大最小值即可，相邻两个桶的最大值和最小值的差值最大的哪一个即所求的差值。时间复杂度稳定在O(n)。
桶排序参考：https://www.cnblogs.com/bqwzx/p/11029264.html
6.用栈实现队列
使用两个栈A和B，元素先压入A栈，出栈的时候将元素按顺序弹出A栈并压入B栈，然后从B栈的栈顶依次弹出。
7.寻找全排列的下一个数
从前到后查看逆序区域，找到逆序区域的前一位
让逆序区域的前一位和逆序区域中大于它的最小的数字交换位置
把原来逆序区域转换为顺序状态
注意最后两位如果是顺序的那么直接交换就好。
还有如果逆序区域等于数的长度，那么就没有下一个数了。
参考：https://www.cnblogs.com/smilepup-hhr/p/11302198.html
8.删去k个数字后的最小值
给出一个整数，从该整数中去掉k个数字，要求剩下的数字形成的新整数尽可能的小。
基本思路：
从左向右遍历整数，如果有一个数字大于其右侧数字，那么去掉这个数字，去掉k个这样的数字就可以了。
实现这个思路的时候可以使用一个栈，从左向右遍历整个数组的时候，将遍历的数与栈顶数进行比较，小于栈顶的数就将栈顶弹出，将这个数压入，弹出k次后就不再弹出剩下的数全部压入，这时新的数就在堆栈中了。
9.大整数加法
大整数加法的实现思路，使用数组拆分大整数，逐段相加，注意中间的进位即可。
10.金矿问题
参考：https://www.cnblogs.com/fengranqingyu/p/8452888.html
这个是所谓的动态规划问题，要解释清楚还真的很费力，所以就不写参考链接里面的讲解。
11.寻找缺失的整数
一个无序数组有99个不重复的整数，范围1~100，缺少一个，设计算法找到这个整数。
最佳解法：算出1到100的和，减去数组元素，剩下的就是要找的那个缺失的整数。时间复杂度O(n)，空间复杂度O(1)。
扩展：一个无序数组有若干正整数，范围1~100，其中99个整数出现了偶数次，只有一个整数出现了奇数次，找到它。
使用异或运算，将所有数组元素运算一遍，最终得到的就是要的数字。
扩展：一个无序数组有若干正整数，范围1~100，有98个出现奇数次，其他整数出现偶数次，找到这两个整数。
采用分治，将两个数分到不同的两组采用上一个类似的方法，关键是是如何份到两组，先将所有数组元素异或运算一遍，得到的是两个计数的异或运算结果，取其中不为0的任意一位，因为两个奇数次出现的整数在这一位必定不同，所以按照这一位为0和1将数组分为两组分别进行异或运算，即可得出想要结果。
以上均来自《漫画算法：小灰的算法之旅》和其他的网上查找，不过这本书看起来很易懂，从来不知道原来算法是这么用的，对于我这样一个初学者来说收获很大。算法的好坏重要的是思想。
