LeetCode刷题笔记（500-599）
LeetCode刷题笔记（500-599）
【500】键盘行
解题记录
首先准备三个数组存储键盘上每一行出现的字符，然后顺序遍历数组中的单词，首先确认单词的第一个字母属于哪一行，确认后遍历单词后面的字符，如果出现不属于第一个字母所属行的字母则将当前遍历的单词从数组中移除，最后返回单词数组。
相关标签
哈希表
【501】二叉搜索树中的众数
解题记录
对二叉树使用递归遍历，使用哈希表记下每个数出现的次数，然后遍历哈希表，找到出现次数最大的数加入结果数组即为所求。
相关标签
树
【504】七进制数
解题记录
这题类似于 【405】数字转换为十六进制数，区别在于这题会出现负数，将所有的负数转换为正数进行处理最后加上符号即可，进制转换的方法与转换为十六进制数是相同的。
相关标签
数学
【506】相对名次
解题记录
首先对运动员的分数进行从高到低排序，然后遍历运动员的分数，假设目前5个运动员分数分别为5、4、3、2、1，那么分数为5的运动员排名第1，所以创建一个记录排名的数组，数组的第5个元素即为1，遍历完分数后，排名数组有如下对应关系，得分“下标”分的运动员排名为下标对应的数组元素，得到这个数组后遍历未排序的运动员分数数组即可得到与之对应的运动员名次数组。
相关标签
数组
【507】完美数
解题记录
这题的超时条件比较苛刻，所以如果遍历寻找所有的因数会超时，所以我们只能寻找一半的因数，另一半的因数靠寻找到的这一半的因数计算获得，所以遍历的终点为所求数开方取整的数，所有因数相加后最后判断一下所求数开方取整再平方是否为原来的数，检测一下所求数是否能被开方为整数，是的话加上这个特殊的因数，判断因数之和是否等于这个数即可。
相关标签
数学
【509】斐波那契数
解题记录
最直观的做法就是使用递归，但是递归耗时耗空间，在这题给出的极端条件下会超时，所以只能使用非递归的方法求解。有两个思路，使用数组和不使用数组，使用数组的话首先将数组的第一个元素和第二个元素置为0和1，之后插入元素，插入的元素为数组最后两个元素之和，这个方法的好处是可以完整的保存整个斐波那契数列，另一个办法不使用数组，只使用两个变量保存最后的两个数，每次循环将第二个变量的值赋给第一个变量，两个变量值之和赋给第二个变量，这个方法节省空间，对于本题的要求，使用第二个方法明显是更好的。
相关标签
数组
【520】检测大写字母
解题记录
一开始我写了非常复杂的条件判断语句去判断是否合规，但其实仔细思考题目可以发现一个规律，对于合规的单词来说，大写字母要么只有一个且是第一个字符，要么和单词的长度相同，要么一个也没有，所以遍历单词，记录下大写字母的数量，最后根据寻找到的规律使用三个条件判断进行或运算即可。
相关标签
字符串
【521】最长特殊序列I
解题记录
这题诈骗性质比较明显，乍一看感觉这题很难，应该会用到模式匹配和切割字符串，想了半天没想到很好的解法，一看题解发现这题是一行流。两个字符串的匹配有三种可能，完全相等，长度相等，长度不同。对于完全相等的字符串来说，互相不存在特殊序列，返回-1，对于长度相等的字符串来说，互相为对方的最长特殊序列，对于长度不同的字符串来说，长的字符串是短的字符串的最长特殊序列，一行return语句解决问题。
相关标签
字符串
【530】二叉搜索树的最小绝对差
解题记录
注意二叉搜索树的性质，当中序遍历的时候获得的序列自然呈从小到大排列，所以对二叉搜索树进行中序遍历就能得到一个有序数组，在有序数组中遍历计算两两相邻元素之差即可得到最小绝对差。
相关标签
树
【532】数组中的K-diff数对
解题记录
遍历数组，将元素出现的次数存储到哈希表中，然后遍历哈希表，寻找±K的元素是否出现过，如果出现过说明可以构成一个K-diff数对，然后将遍历过的哈希表键值对置为空。
相关标签
数组，双指针
【538】把二叉搜索树转换为累加树
解题记录
还是利用二叉搜索树的性质，但是这一次进行逆中序遍历，从最大的元素遍历到最小的元素，由于每个元素需要加上比他大的所有元素的值，所以从最大的元素开始累加然后赋值即为所求。
相关标签
树
【541】反转字符串II
解题记录
这题涉及到大量的切割字符串，只要输入字符串的剩余长度大于2K，就按正常流程操作，首先切割输入字符串的前2K个字符，然后将切割下来的子字符串的前K个字符进行反转拼接到后K个字符上，最后将输入的字符串前2K个字符删除。如果剩余长度大于K小于2K，将剩余字符串前K的字符进行反转，如果小于K，直接将剩余字符串拼接到结果上即可。
相关标签
字符串
【543】二叉树的直径
解题记录
关于二叉树的题目大部分时候都是使用递归进行求解，这题也不例外。我们思考一下，直径有两种可能，一种路过根节点，一种并不路过根节点，而不路过根节点的直径也一定路过根节点的某个子节点。如果是路过根节点的直径，长度就为根节点左右子树深度和+2，所以对二叉树进行递归，将二叉树的左右子树深度之和+2与最大直径进行比较，将较大者赋给最大直径，如果最大直径大说明存在不路过根节点的直径为最大直径，如果左右子树深度和+2大说明路过根节点的直径为最大直径。
相关标签
二叉树
【551】学生出勤记录I
解题记录
这题有两个思路，一个思路是直接遍历字符串检查是否符合条件，另一个思路就是正则表达式。
相关标签
字符串
【557】反转字符串中的单词III
解题记录
主要就是以空格为分界，由于题目标注了不会有额外空格，所以并不复杂。有个减少耗时的小技巧，每次处理单个单词的时候我一开始先取到单个单词，然后对单个单词进行反转拼接到答案中，但是其实更好的办法是在取单个单词的时候直接将读取到的字母不断插入到单词的头部，直接就可以得到反转的单词而不需要再调用字符串方法。
相关标签
字符串
【561】数组拆分I
解题记录
这个又是一个看起来很难实际上有规律的题，其实本质就是问你一个排好序的数组的奇数位之和，凭直觉找到了这个规律，但其实数学证明还是挺复杂的，在LeetCode评论区里有人给出了完整的数学证明。
相关标签
数组
【563】二叉树的坡度
解题记录
这题有一点绕，一颗二叉树的坡度等于其所有节点的坡度之和，而节点的坡度等于该节点左侧所有元素之和与右侧所有元素之和的差的绝对值。一开始有点绕进去想到的方法是两层递归嵌套，一层递归用来算某节点下的元素之和，另一层递归用来将节点的坡度相加。但其实一层递归就可以解决这个题目，在递归的过程中求某个a节点左侧的元素之和其实是求了该a节点左孩子的左侧元素之和和右侧元素之和，再把这两个和相加再加上a节点左孩子自己的值返回给a节点，那么在这个过程中其实就已经得到了a节点左孩子的坡度，不需要再进行第二次递归。
相关标签
树
【566】重塑矩阵
解题记录
遍历原始数组，存储到新的数组中，使用辅助变量记录已经存储的列数，达到新的限制就换行存储，在遍历原始数组之前需要先判断原始数组和重塑后的数组元素数是否一致，否则的话直接返回原始数组。
相关标签
数组
【572】另一个树的子树
解题记录
这题有两个思路，一个思路是对S树递归的比较是否是T树的子树，比较两棵树是否相等也需要使用递归，递归每个节点是否相等，所以如果使用递归的话相当于两层递归嵌套，效率比较低。另一个方法是对两棵树进行遍历，获取遍历的顺序，将遍历的顺序以字符串的形式存储下来，如果S树中有与T树相同的子树，那么在T树的遍历字符串一定是S树的遍历字符串的子串。所以问题变成如何生成遍历字符串，对二叉树进行遍历为了直观起见，一般都选用递归的方式。但是要考虑一个问题，如果一个节点为1，一个节点为2，遍历得到12，与一个为12的节点是相通的，所以我们需要为每一个数进行标示。还需要考虑不完整的二叉树的遍历顺序可能会相同，所以在遍历时还需要将空节点进行标记加入到遍历字符串中。
相关标签
树
【575】分糖果
解题记录
这题看起来还是比较复杂的，但是仔细分析其实只有两种情况，第一种，糖果的种数大于每个人应该发放的糖果数量，那么直接返回每个人应该发放的糖果数量即可，此时妹妹分到的糖果是各不一样的，弟弟拿走剩余的糖果。第二种，糖果的种数小于每个人应该发放的糖果数量，这时候应该返回糖果的种数，妹妹拿每种糖果各一颗，再补齐需要拿的总数，剩余的由弟弟拿走。所以建立哈希表，遍历数组获得糖果的种数就可以直接判断返回。
相关标签
哈希表
【581】最短无序连续子数组
解题记录
这题最直观的方法就是对数组进行排序，然后双指针对原数组和新数组同时遍历，找到不同的位置就可以得到长度。但是这题其实是可以一次遍历得到答案的，把问题分成两部分，一部分是找到左侧无序子数组的末端，我们对数组进行遍历，假设数组是完全逆序的，取第一个元素（除非完全逆序，否则第一个元素一般是最小的元素）为最大的元素，遍历的时候如果遇到更大的元素就更新最大值，如果遇到更小的元素说明数组在此处是无序的，记下当前的下标，继续向后遍历，如果当前下标后没有更小的元素，说明当前下标以后的数组是有序的，这样就得到的无序子数组的末端。同理，从数组末端向前遍历，取最末尾元素为最小的元素，遇到更小的元素更新最小值，遇到更大的元素说明数组在此处无序，记录下标，直到遍历到开头，这样就能得知无序子数组的开头。得到了开头和结尾就能知道最短无序连续子数组的长度了。以一个数组进行举例，观察[1,2,3,7,9,5,6,4,8,10]，从1-9一直都是有序的，此时最大值为9，一直到10都没有更大的元素，都比9小，说明只有10是有序的后缀。从后往前遍历时，10-4都是有序的，此时最小值为4，一直到3都没有更小的元素，都比4大，说明1-3是有序的前缀，将前缀和后缀减去剩下的部分就是最短无序连续子数组。这个方法优化后可以一次遍历同时找到有序前缀和有序后缀，且不需要额外空间。
相关标签
数组
【594】最长和谐子序列
解题记录
哈希表遍历数组拿到每个数字出现的次数，遍历哈希表键值找到相差为1的两个数出现次数，找到最大的那对即为所求。
相关标签
哈希表
【598】范围求和II
解题记录
求最大整数的范围就是求最多的重叠范围，重叠的区域越大则这个区域的数也就越大，要求最大的重叠区域就是求所有操作中最小的长和最小的宽，这个长和宽组成的区域就是最多的重叠范围，每次操作过后总能覆盖到这个区域。
相关标签
数学
【599】两个列表的最小索引总和
解题记录
首先遍历其中一个列表存入哈希表，将列表元素作为key，下标作为value，然后遍历另一个列表，如果遍历的元素在哈希表中并且两次出现的下标之和最小就把当前元素作为待返回的结果之一。与哈希表有关的简单题目我觉得我基本上已经掌握了，一般都能比较快的得出正确的思路。
相关标签
哈希表