最近刷了刷LeetCode的初级算法题目，大部分题目都很简单，有些题目却很有意思，值得总结一番。
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
这种题不难，但是第一次看到的时候比较难以把握住这道题到底什么意思。如果可以画图，就可以很好地辅助理解
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
进阶:
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
这道题我采用的方法是遍历大数组，对大数组中的每个元素，遍历小数组，若其中包含有该元素，则删除之并添加其到答案数组。
这种方法相比另一种循环方式来说更节省时间。可以通过数学方式来证明，倘若交集元素个数为k，平均来看，这k个元素出现应当是随机平均的。
那么可以将内层循环的数组元素个数与外层循环次数看做一次函数。在这种情况下，假设大数组大小为n，小数组大小为m，则两种循环方式分别会减少循环次数n(1+k)k/2、m(1+k)k/2。这样的算法时间复杂度实际为O(m * n)，不计输出空间复杂度为O(1)。
当然，也可以选择将某个数组放入一个表中，然后遍历另一个表寻找是否存在交集。这样最优是采用哈希表，时间复杂度为O(m + n)，空间复杂度为O(n)。这种情况下两个数组都只需循环一次，只是一次是插入，一次是查询。如果不能比较适合的选取哈希表参数，插入小数组可能会比较节省时间和空间。
对于进阶要求：
移动零 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
这道题也比较有意思，放在这里主要是因为我第一次从后向前遍历，交换非零元素与零元素导致数组不保序。其实很简单，只需要反复从头找到第一个零之后的非零元素与第一个零，将之交换即可。
旋转图像 给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
这道题有两种方法，一种是迭代地将所有元素按逆时针方向交换，这样每个元素都会被交换一次，所以总共会进行交换操作n*n次。
另一种需要用到线性代数的知识，只需先将矩阵转置，然后将列元素以中心为轴交换即可。
但是我觉得这里可能会存在更佳的方法，如果先将矩阵按照另一个方向转置，然后只需要交换行即可。这样的方法可能对于c/c++中用二维数组表示的矩阵没有什么区别，甚至可能因为转置过程需要多一步计算会更慢一些。但是如果矩阵不是用直接堆积的方式，而是用保存向量引用的方式进行储存，那么交换行会快很多。
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，qing返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42"
输出: 42
这道题比较烦，需要处理很多细节。 我是用一个64位来储存结果，将字符串先处理成一个整数，然后这个整数如果是负数则记录下来，然后将这个整数按十进制放入64位中，最后检测是否有溢出，如果有溢出，根据正负性返回适当的结果，但是这样做并不优雅，而且如果不是每次转换都检测是否有溢出，那么很可能他给你一个64位以上的数字，刚好在64位以内检测不到溢出。
比较优雅的解法应该是这样的，将字符串处理为一个整数，然后记录符号，对一个unsigned int型不断按十进制放入，每次放入后检测第32位按照正负性判断是否溢出，溢出返回对应值，最后返回正确值。但这样效率比较低，不过可以通过限制字符串位数来优化。
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
此题可以通过快慢指针来解决。
快慢指针是一种技术，让一个指针一次迭代沿链表走两步，另一个走一步，达到一个走到中间，一个走到末尾的结果。
这道题可以用这个技术将链表从中分为两半，然后将后半部分翻转，接着两个链表比较。
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
这道题也可以通过快慢指针来解决，只需让两个快慢指针对链表遍历，如果两个指针在过程中相等，则说明有环，否则无环。
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
这道题比较麻烦，但是属于BST的常识，以前不知道，所以在这里记录一下。
BST中，左子树中所有节点比当前节点小，右子树中所有节点大于当前节点，所以如果用中序遍历，那么就应该得到一个从小到大的序列。故而做递归检验即可。
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
这道题比较简单，和上一题相对应。用递归的方式比较好解决。
还是按照中序遍历的方法，取数组中位值作为当前节点，然后把左边作为左子树，右边作为右子树，递归调用算法即可。
给定一个整数，写一个函数来判断它是否是 3 的幂次方。
示例 1:
输入: 27
输出: true
示例 2:
输入: 0
输出: false
这道题比较简单，但是存在一个比较巧妙的方法。
通过迭代和递归的方法很简单，只需判断是否能一直被三整除到一为止即可。但是存在一个很巧妙的方法，只需要用输入的数字最大的三的幂次除以当前数，能整除就为三的倍数。
对于不定长的数也有方法，可以设定一些魔数，分别为n位下最大的三的倍数，2n位下最大的三的倍数等，对处于区间之中的数用上限去整除；对于更大的数，用最大数整除至小于其为止，然后重复上述过程。
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
这个算法实际上是在求汉明重量。
存在以下几种算法：