LeetCode刷题笔记（100-199）

【100】相同的树

解题记录

最近正好在学树的遍历，这题自然而然想到通过递归实现，若当前两棵树对应的元素值不同则直接返回false，否则一直遍历直到两棵树都为空，若有一棵树提前为空则也返回false。

【101】对称二叉树

解题记录

这题与100题相似，还是考察树的基本使用，依旧是使用递归，对两棵子树的对称节点进行比较，相同返回true，否则返回false。

【104】二叉树的最大深度

解题记录

还是树的基础知识，依然使用递归解决。第一次提交LeetCode提示超出时间限制，精简了代码之后才通过了判题。

【118】杨辉三角

解题记录

双层for循环嵌套，外层循环每循环一次相当于放好一排杨辉三角，内层循环每循环一次计算好一排杨辉三角。每一行杨辉三角的结果都依赖于上一行杨辉三角的值，所以当杨辉三角层数大于等于1，先令第一层为1，之后的每一层的第n位都等于上一层的第n位与第n-1位之和，并使用三目运算符判断是否n与n-1是否越界进行赋值，若不越界则直接取上一层的对应值，越界则赋值为0。

由于这题对空间复杂度提出了要求，如果直接用118题普通杨辉三角的方法求出所有杨辉三角，自然也能得出答案，但是空间复杂度大大提升。我们需要寻求一种只需要一个数组的方法。我们令一个数组为我们需要返回的答案，由于第n位杨辉三角值都等于上一列的第n位与第n-1位，我一开始想到的是循环数组，令每个数组值等于自身与前一位之和，但是这么做会带来一个问题，第n+1位需要用到第n位与第n+1位的值，但是在循环到n+1位之前，第n位的值已经被改变了。为了解决这个问题，可以从后往前循环，这样的话被修改的数组值就是再也不会被用到的值，这样就完成了通过一个数组完成输出第k行杨辉三角的任务，空间复杂度为O(k)。

【121】买卖股票的最佳时机

解题记录

一开始看到这个题冒出的第一想法其实还是动态规划，第n天以前的最大利润肯定大于等于第n-1天以前的最大利润。但是在思考的过程中遇到了一定的困难，不知道该如何把问题转换成动态规划的问题。用暴力法解这个题很容易，但是时间复杂度很高，是最差的算法。我们可以观察问题，每一个点的最大利润一定产生在当前点与当前点之前的最低谷之间，那么我们只需要一直记录最低谷，并用每个点减去最低谷，得到的利润与最大利润比较，如果更大，则将最大利润重置为当前利润，否则的话继续循环。一次循环就能解决问题，时间复杂度为O(n)。

【122】买卖股票的最佳时机II

解题记录

我们可以观察到，在每个股票价格由极小值走向极大值（非最小值最大值）的过程中买入就是最大的利润，所以我们需要想办法求出极小值与极大值。遍历股票价格数组，并设置两个变量代表极小值与极大值，当当前变量小于极小值或者小于极大值时，这意味着当前变量可能是极小值，将其重置为极小值，由于我们要求的极大值必定在极小值之后，所以我们需要将极大值也重置为0。如果当前变量大于极大值，将当前变量重置为极大值，如果当前变量大于极小值，则利润就为当前变量与极小值的差。最终将每一段的利润加起来就是我们要求的最大利润。但实际上这个题有更简单的思路，由于我们要实现最大利润，所以其实我们要求出整个股价曲线最终上升的总和，

【125】验证回文串

解题记录

我使用的方法是先对字符串进行遍历，删除所有字母数字以外的元素，然后将所有字符转换为小写字母，最后比较字符串与反转字符串是否相同。

【136】只出现一次的数字

解题记录

这题有两个要求，不使用额外空间，时间复杂度线性。如果没有这两个要求，我可能会遍历一遍数组，创建额外空间存储可能只出现了一次的数，只要有重复的就从额外空间中删除这个可能的数，最后剩下的即为所求。但是加上那两个要求后，我就没什么好的思路，我一开始想到的是将第一个元素作为只出现一次的数字，往后遍历数组，如果发现重复的数，将只出现一次的数重置为发现重复数后的第一个数。但是这么做有很大的问题，在如果真正只出现了一次的数在两个重复数之间，那么就无法得到答案。苦苦思考没有头绪，我查看了一下这题的相关标签，位运算是我听说过但从没有仔细学习过的知识，哈希表我虽然使用过，但确实不熟练。所以只能补充基础知识再做这个题了。

位运算

常见的位运算有四种，与、或、异或、取反。

与AND运算的符号是 & ，当二进制位相同时不变，不相同时为0，例如 1&1=2，1&0=0

或OR运算的符号是 | ，当二进制位存在1时为1，否则为0，例如 1|1=1，1|0=1，0|0=0

异或XOR运算的符号是 ^ ，当两个二进制位有且只有一个1时为1，其余时候为0，例如 1^1=0，1^0=1

取反NOT运算的符号是 ~ ，对每一个二进制位取反，例如 ~1=0，~0=1

位运算的常用性质：

～x = -x - 1：从以上0与-1的按位关系可以看到，两者的二进制位正好取反；此规律能推广到1与-2，2与-3……等等。因此，该性质是NOT操作中最常使用的性质。
(~x)&x = 0：任意数与它的取反数的AND操作结果为0。
(~x)|x = -1：任意数与它的取反数的OR操作结果为-1。
(~x)^x = -1：任意数与它的取反数的XOR操作结果为-1。
x|0 = x：任意数与0的OR操作结果为自己。
x^0 = x：任意数与0的XOR操作结果为自己。
x^y^y = x：任意数x与任意数y进行两次XOR操作结果为x自己。

二进制与位运算实用操作汇总

哈希表

数据结构简介——哈希表

了解完了基础知识以后回到这个题，由于题目强调了除了只出现了一次的那个数，其余的每个数都出现了两次，那么我们可以使用异或XOR运算，由于相同的数进行XOR运算结果为0，而任何数与0进行XOR运算结果为自身，这题每个重复的数都只出现了两次，使用XOR运算可以将所有重复的数抵消为0，最后剩下的只剩0和只出现了一次的数，进行XOR即为所求，时间复杂度线性，没有使用额外空间。如果这题使用哈希表，需要使用与数组长度相同的额外空间，每遍历到一个数，如果哈希表中没有这个元素，则将这个元素作为key，出现的次数1作为value存入哈希表，如果哈希表中有这个元素，将出现的次数自增存入哈希表，最终对哈希表进行遍历，找到value为1的key即为所求。但是用哈希表存在一个不确定性，如果数组很长，存入哈希表后存在哈希碰撞的可能性，那么寻找哈希表中是否存在这个值的时间复杂度就不再是O(n)

【167】两数之和II-输入有序数组

解题记录

由于是有序数组，所以我第一时间就想到了双指针或者二分查找，如果使用二分查找，需要先找到目标值的中位值，然后从这个位置开始使用双指针进行查找，但实际上在使用二分法的过程中，消耗了一定的查找时间，可以直接用双指针进行求解。由于是有序数组，我们将一个指针指向第一个元素也就是最小值，一个指针指向最后一个元素也就是最大值，如果两个数加起来大于目标值，则后一个指针前移，如果小于，则前一个指针后移。一开始的时候我犯了一个错误，我将第二个指针指向了第一个元素，当两个元素加起来小于目标值的时候第二个指针向后移，当大于的时候，第二个指针往前移的同时第一个指针往后移。但是这么做有一个问题，每次如果和大于目标值，会导致两个指针同时移动，结果就是第一个指针很可能错误的越过我们需要的值，一旦越过，就无法得出正确答案。

【168】Excel表列名称

解题记录

一开始没看懂题意，走了一些弯路，后面发现这其实是一个十进制转二十六进制的问题，明白了这个本质后问题就简单了，将其转换为26进制后作为 ASCII 码制获取对应的字符，就能得到答案。但是需要注意的是字符顺序是以A开始的，但是表列标号是从1开始的，所以我们每次循环都需要将表列标号自减1。

【169】求众数

解题记录

最开始我想到的方法是先对数组进行排序，然后遍历数组找到出现次数最多的元素，这个方法的耗时只打败了个位数的人，估计也就仅仅只是比两层 for 循环嵌套暴力求解快。其实如果首先对数组进行排序，没必要再遍历数组找到出现次数最多的值，由于题目对众数的定义是出现次数大于数组长度的一半，这意味着当数组排好序后位于中间的数就是我们要的众数，直接返回值即可。但这么做其实提升并不大，在排序的过程中耗费了太多时间，最终其实只比排序+遍历少了一个循环。还想到用哈希表，key 值表示数字，value 值表示数字出现的次数，遍历一遍数组，添加到哈希表后如果有一样的 key 值，就自增 value 值，最后返回最大的 value 值对应的 key，而这也不是最好的办法，虽然时间复杂度降到了 O(n)，但是同时也使用了 O(n) 的额外空间。而最好的解法，是使用 Boyer-Moore 多数投票算法。

Boyer-Moore 多数投票算法

Boyer-Moore 多数投票算法适用于解决寻找一个集合中出现次数最大且大于一半的元素的值的问题，由于集合中只有两种元素，等于目标元素的元素和不等于的元素，我们可以模拟投票，令等于目标元素的元素持有一个值+1，不等于的元素持有一个值-1，由于我们要求的元素在集合中占比超过一半，所以最终所有元素持有的值加起来一定大于0。它的思路是这样的，先假定第一个元素就是我们要求的元素，遍历集合，如果与我们要求的元素相等，则投票值+1，就像投票时投了一票赞成票一样，如果不相同，则-1。当投票值为0时，意味着当前赞成票与反对票相同，也就是说我们在一开始假定第一个元素为目标值可能并不是正确的答案，那么我们假定下一个元素为目标值，继续进行投票，最终剩下的元素就是我们要求的元素。

这题还提到可以使用位运算，我也看到了有用位运算的题解，但是很难理解，用位运算解题一般都是奇技淫巧，学不来。

【172】阶乘后的0

解题记录

一开始我先自己用计算器计算了一些简单的阶乘观察规律，我发现每逢5或10就会新增一个0，这题要求用 O(log n) 的时间复杂度解决问题，并且题目测试用例给了一些极大的阶乘，肯定无法使用直接运算的方式得出。我通过不断的测试寻找到规律，n的阶乘后0的个数m可以通过一个等比数列进行计算，公式为：

1	`m = n/5 + n/25 + n/125 +...+ n/k，k < n`

虽然推导出了公式，但其实我不明白公式的原理，有机会再请数学大佬为我解答吧。

【189】旋转数组

解题记录

最初我陷入了一个误区，直接将数据与n位以后的数据交换，这么做有一个很大的陷阱，以 [1,2,3,4,5,6,7] 和 k = 3 为例，将1与4交换后，1确实被放到了正确的位置，但是4被放到了错误的位置，而这反而打乱了数组的顺序，使得后续要对错误位置的数字进行位置调整更加困难。有一个方法叫三次反转法，我们观察 [1,2,3,4,5,6,7] 和它旋转后的 [5,6,7,1,2,3,4] 可以发现一个规律，我们先将 [1,2,3,4,5,6,7] 反转，得到 [7,6,5,4,3,2,1] ，对比反转一次后的数组与旋转结果，从数组的第三个元素与第四个元素为界，两侧分别进行反转就能得到我们需要的结果。发现这个规律后就可以开始写代码了，但是有一个小细节需要注意，我们需要将向后挪动的位数取数组长度的余，以刚才的例子为例，如果将 k 修改为10，得到的结果也是一样的，但如果不做这个处理，就会数组越界。

【198】打家劫舍

解题记录

分析题目可以知道这是一个动态规划的题目，每到一户所能抢劫到的最高金额，取决于它的前两户，当到的新一户与前两户最高金额的和大于前一户的最高金额，那么当前这户能抢劫到的最高金额就等于与前两户最高金额之和，否则的话与前一户的最高金额相同，这是动态规划的状态方程的描述，想明白后这题很容易，一个动态规划的入门题。时间复杂度 O(n)。