LeetCode刷题笔记（400-499）
LeetCode刷题笔记（400-499）
【401】二进制手表
解题记录
遍历0小时0分到11小时59分的所有时间，检查这些时间用二进制表示时位为1的位数，如果1位数之和为给定的LED灯亮着的数量，将这个时间添加到结果数组中。这题的知识点在于如何求一个二进制数的1的位数，一开始我使用的方法是将二进制数转换为字符串，统计字符串中1出现的次数，其实这个问题就是【191】位1的个数，但是由于那题没有提供Swift的提交选项，当时被我直接跳过了。其实统计二进制位1的个数可以使用位运算，假设x为一个二进制数，x & (x - 1)每次得到的结果可以消除x存在的一个1，重复进行与运算，直到为0，进行与运算的次数就是x位1的个数。
相关标签
位运算、回溯算法
【404】左叶子之和
解题记录
这类题目一般都会自然而然的想到使用递归解决，如果一个节点是左节点且该节点的左右节点均为空，那么这个节点就是左叶子，需要返回他的值，这题最好构造一个辅助函数，传入一个Bool变量表示是否为左节点再进行递归，否则很难从根节点直接判断左节点是否为左叶子。
相关标签
树
【405】数字转换为十六进制数
解题记录
每次将数除以16，得到的商作为下一次除以16的被除数，得到的余就是所求十六进制的一位。以4567为例，其十六进制数为11d7，求解方法如下：
4567 / 16，商285，余7
285 / 16，商17，余13（十六进制下的d）
17 / 16，商1，余1
1 / 16，商0，余0
最后将所有余数组合在一起即为所求。如果需要转换的数字小于0，需要先求该数的补码，由于题目给定的数是32位以内，所以将1左移32位得到最大值+1的数，再加上需要转换的负数就得到了负数的补码，得到补码后按照正常的求解方法即可。
相关标签
位运算
【409】最长回文串
解题记录
用哈希表记录下每个字符的出现次数，再将所有偶数的出现次数相加，奇数的出现次数减去1后相加，因为偶数可以直接组成回文串，但不考虑中间的字符的前提下奇数无法组成回文串，必须舍掉一个字符。最后如果出现过奇数的出现次数就将结果加1返回，如果没出现过就直接返回结果，因为如果出现过奇数的出现次数，说明可以有一个字符位于回文串中间，故要再加1。在Swift中哈希表的效率并不如数组高，又因为字母的ASCII码是连续的，所以使用数组提高查找效率。
相关标签
哈希表
【412】Fizz Buzz
解题记录
过于简单，三个条件判断决定添加到数组中的字符串为什么样即可。
相关标签
无
【414】第三大的数
解题记录
使用三个变量记录最大的三个数，遍历数组，对三个变量进行更新，最后返回三个数中代表最大数的那个。但是需要注意如果三个变量中已经有与需要对比的数相等的数，需要直接跳过循环。
相关标签
数组
【415】字符串相加
解题记录
这题的思路就是模拟传统手工进位加法，用双指针从两个字符串末尾开始遍历，再设置一个变量记录是否进位，每次相加双指针所指的数与进位作为当前位的结果。
相关标签
字符串
【434】字符串中的单词数
解题记录
一开始忽略了可能连续出现的多个空格，直接将空格数+1作为结果，正确的方法是记录下上一个字符是空格，当前字符不是空格的字符数即为所求，
相关标签
字符串
【441】排列硬币
解题记录
最初用的是最常规的循环解决思路，很简单，但是耗时也很不理想，观察答案规律可以观察到其实给定的硬币数目是一个等差数列的和，首项为1，公差也为1，所以题目变成1+2+3…+a <= n，已知n，求a最大为多少。根据等差数列的求和公式，带入首项和公差可以得到a^2+a = 2n，再使用二次函数的求根公式可以得到这个根，再对求到的结果向下取整即为所求。
相关标签
数学、二分查找
【443】压缩字符串
解题记录
最初我想到了使用数组记录下每个字符的出现次数，然后最后将出现次数和对应字符拼接形成所需的答案。这里对题意的理解有一定的歧义，题意的压缩字符串指的是可以根据压缩后的字符串完整的还原成原来的字符串，但是如果只记录字符串的出现次数，就丢失了对应字符的出现顺序的信息。我想到的第二个方法是使用双指针，后一个指针找到最后一个与前一个指针连续相同的字符，两个指针之差即为当前第一个指针所指向的字符在这一段中连续出现的次数，将次数信息与对应字符记录下来，前一个指针直接挪动到后一个指针的位置，继续向后查找下一个字符，完成题目。
相关标签
字符串
【447】回旋镖的数量
解题记录
最暴力的方法就是三层循环，首先将第一个点与第二个点固定，算出距离，然后在所有剩下的点中遍历，若第三个点与第一个点距离相等，则结果数+1。这个方法虽然很容易想到，但是时间复杂度高，并不能通过提交。注意题意要求，我们只需要返回有多少对点满足回旋镖条件即可，并不需要返回具体是哪几对点满足，所以考虑优化之前的循环，将三层循环改为两层，固定第一个点，从所有剩下的点中与第一个点一一计算距离，如果当前点与第一个点的距离计算后发现已经出现过，说明有至少一个点与第一个点的距离与当前点与第一个点的距离相等，那么就可以达成回旋镖的条件。此时我们还需要记录下与第一个点满足同样距离条件的第二个点出现的次数，每出现一个新的同样距离的第二个点，都可以与前面的N个点两两配对形成2N种回旋镖。我们以一个例子来说明这个算法。观察 [[0,0],[1,0],[0,1],[-1,0],[0,-1]] 这个点集，首先将 [0,0] 设为第一个点，遍历其余的点，第二个点首先是 [1,0] ，与第一个点距离为1，此时与第一个点距离为1的点为1个。然后第二个点变为 [0,1] ，与第一个点的距离依然为1，此时与第一个点距离为1的点变为2个，可以组成两对回旋镖，然后第二个点变为 [-1,0] ，与第一个点距离为1，此时与第一个点距离为1的点变为3个，点 [-1,0] 与之前的两个点两两匹配可以新组成四对回旋镖，最后第二个点为 [0,-1] ，与第一个点距离为1，此时与第一个点距离为1的点变为4个，点 [0,-1] 与之前的三个点两两匹配可以新组成六对回旋镖，最终以为第一个点可以组成6+4+2对回旋镖，将第一个点设为 [1,0] ，继续进行下一个点的分析，将所有点分析完后即可得到回旋镖的数量。
相关标签
哈希表
【448】找到所有数组中消失的数字
解题记录
这题初看与【268】缺失数字很相似，区别在于这题可能缺失不止一个数字，并且缺失的数字位置会被重复的其他数字替代。如果使用268题的思路用和去减或者异或运算，是无法得到我们所需的结果的。这题最难的点在于不使用一丁点额外空间，常规能想到的诸如哈希表之类的方法都需要一个与原数组等长的数组。这题如果要做到不使用额外空间就需要借助数组自身来进行辅助。正确的方法我没想到，我是看了参考答案以后才明白的，题目给定了数组中数的范围是1～N，N为数组长度，所以遍历数组时将每个数对应的下标的数设置为相反数也就是负数，当遍历结束时数组中剩下的不是负数的数对应的下标即为我们要找的消失的数。这个方法利用了数组本身的下标作为一个信息。
相关标签
数组
【453】最小移动次数使数组元素相等
解题记录
这题有两个方法比较好，动态规划和数学法。观察 1,5,6,8,9 这个数组，由于每次只可以加4个元素，要想另5个数组元素相等，那么最后一步一定是 n-1,n-1,n-1,n-1,n ，要令前4个元素相等，最后一步一定是 n-1,n-1,n-1,n,x 以此类推。所以只需要遍历数组，令当前元素加上已经操作的次数，再求当前元素与第一个元素的差，将差分别加到第一个元素与操作次数上即可。优化流程后可以一次循环完成操作。在进行动态规划的时候可以观察到每次操作次数相加的值就是第一个元素与那个元素的差值，也就是数组中最小的元素与每个元素的差之和即为所求。因为将n-1个元素都加1相当于将最大的元素-1，我们只关心元素之间的差值而不关心他们的绝对值，所以将每个元素减到与最小元素相等所用的次数即为所求。
相关标签
数组
【455】分发饼干
解题记录
对两个数组进行从小到大排序，然后双指针分别指向两个数组从后往前遍历，如果当前指向的饼干大于小孩的胃口，说明这个饼干可以满足小孩，结果+1，两个指针同时往前移动，否则只移动指向小孩的指针。最后当某个指针回到开头时结束循环。最初我以为这个题有什么办法可以在不排序的前提下完成，实在想不到就用需要排序的方法做了一遍提交只超过了很少的用户，开始怀疑人生，看了参考答案发现我这个办法已经是最优解了，LeetCode坑爹。
相关标签
贪心算法
【459】重复的子字符串
解题记录
首先使用一个循环找到字符串的公约数，对于每个找到的公约数，取字符串的前公约数位作为参考子字符串，再将N个参考子字符串拼接成字符串的长度，与字符串对比即可知道当前参考子字符串是否是重复的子字符串，如果不是继续匹配下一个公约数，直到所有公约数匹配完成。以 abcdefabcdef 字符串为例，第一次寻找到的公约数是1，参考子字符串是a，拼接得到 aaaaaaaaaaaa，不匹配，寻找下一个公约数2，拼接得到 abababababab，不匹配，直到寻找到公约数6，拼接得到 abcdefabcdef，匹配，此时可以返回结果。
相关标签
字符串
【461】汉明距离
解题记录
LeetCode对于汉明距离的定义有歧义，建议自行查找汉明距离的定义，要计算汉明距离其实就是求出两个数二进制位有哪几位不相同。这里可以借助异或运算的性质，两个数异或后所有不相同的位为1，再利用401题中使用过的计算位1的个数，借助于运算计算出位1的个数，即为所需求的汉明距离
相关标签
位运算
【463】岛屿的周长
解题记录
从左到右从上到下扫描整个数组，当扫描到岛屿时周长加4，但是如果扫描到的岛屿左侧也有岛屿，就需要加4后减2，这很好理解，因为两块岛屿相邻的地方需要扣除各自方块1的周长，合计减2。同理，如果扫描到的岛屿上侧有岛屿，也需要减2，最后得到的就是岛屿的周长。我们可以使用数组存储之前岛屿的出现情况，只需要存储上一行的当前列到当前行的上一列的数据即可，所以数组的大小只需要列数那么多。
相关标签
哈希表
【475】供暖器
解题记录
首先将房屋的位置和供暖器的位置进行排序，然后每次使用二分查找寻找距离每个房屋最近的供暖器，记录下此时的加热半径，供暖器的最小加热半径就是所有记录下来的加热半径中最大的那一个。这题的难点在于二分查找，不使用二分查找的话这题是无法在时限内完成的，而二分查找时需要注意的是供暖器与房屋几乎不会位置重合，所以需要找出房屋左侧的第一个供暖器和右侧的第一个供暖器取最小绝对值差为加热半径。
相关标签
二分查找
【476】数字的补数
解题记录
我们利用一个性质，一个数与其自身的补数之和一定是一个所有位均为1的二进制数，且这个二进制数的位数与这个数本身相同，而一个二进制位均为1的数+1为一个第一位为1，其余为为0的二进制数，所以我们只需要找到最小的大于所求数的整二进制数（第一位为1，其余位为0的数），将这个数减去1再减去所求数本身就是所求数的补数。
相关标签
位运算
【482】密钥格式化
解题记录
这题只需要逆序读取字符串进行处理就能比较简单的完成，需要注意的是我一开始使用字符数组存储转换后的字符串，最后将字符数组再转换为字符串，这么做会导致未知的时间耗费，改为直接操作字符串耗时会大大缩短。
相关标签
字符串
【485】最大连续1的个数
解题记录
顺序读取数组，遇到1记录数量，遇到0将记录的数量与最大连续1的个数对比，取最大值为最大连续1的个数，然后清空数量。
相关标签
数组
【492】构造矩形
解题记录
一开始我寻找所有面积的公因数，然后在公因数中寻找差值最小的一对，但这个方法在数字较大时耗时很大，寻找公因数就需要很长时间。这题找的是差最小的一对公因数，而如果一对公因数差为0意味着这个公因数就是这个面积的开方，所以我们直接从面积数的开方处开始查找是否为面积的公因数，此时找到的第一对公因数即为所求。
相关标签
数学
【496】下一个更大元素I
解题记录
遍历第一个数组，寻找第二个数组中对应位置之后是否有更大的元素，如果有存入哈希表，当两个数组遍历到末尾时意味着此时找不到更大元素，所以将-1存入哈希表中对应的元素。遍历完第一个数组后再次遍历第一个数组，将值替换为哈希表中对应的值，此时第一个数组即为所求。
相关标签
栈