LeetCode刷题笔记（200-299）

【202】快乐数

解题记录

做这题的时候感慨了一下，大一的时候求一个数的各位还专门背了个十百千的求法，但是现在已经可以用循环信手拈来了，想当初为什么就不会用循环呢？明明是很简单的问题。回到题目，这题的难度不在于取各位，难度在于何时终止循环，若给定数字是快乐数情况很简单，满足条件返回即可，但是不是快乐数的情况如何判断呢？不是快乐数的情况下程序会陷入无限循环，我们需要找到一个办法终止循环。最初我使用的方法是使用哈希表存储每一次计算出来的各位平方和，直到新的平方和已经在哈希表中存在为止。这个方法有个毛病，需要很多额外空间存储我们计算出来的平方和，尤其是在给定的数字比较复杂的情况下。而更好的方法是快慢指针，快指针每个循环计算两次平方和，慢指针计算一次，两个指针差距每次循环增大一次计算，这样的话如果平方和中存在循环，当慢指针计算到开始循环的地方，快指针已经在循环中计算了多次，两个指针一定会发生碰撞，所以当指针碰撞时，判断值是否为1即可得出结论。

【203】移除链表元素

解题记录

这题还是属于链表应用的基础题目，与第83题相似，第83题在LeetCode刷题笔记（二）中进行了描述。需要注意的就是对引用值的操作应当注意是否正确，以及如何处理第一个元素。

【204】计数素数

解题记录

这个题应该是目前我写过的简单题里坑最深的一个题了，表面上看起来，没什么难的，就是遍历所有更小的数判断是否为素数然后记下是素数的数的数目即可。以这个方法来写这个题，很容易超时，我第一次提交的时候就提示我执行超时，基于这个方法，改进了一下判断素数的条件，将循环终点从一半修改为平方根，时间上有了提高，在LeetCode中20个测试用例的执行时间是我前所未见的3000+毫秒。还有一些别的效率更高的判断一个数是否是素数的数学方法，例如Fermat小定理、Rabin-Miller测试等方法，感兴趣可以点击这里查看学习，这题的突破口并不在于如何快速的判定素数。

埃拉托斯特尼筛法（Sieve of Eratosthenes）

这是一种简称为埃式筛或素数筛的历史悠久而简单的筛法，用于找出给定范围内的所有素数，这个方法是列出小素数最有效的方法。其实这个算法的思路很简单且符合直觉，下面介绍算法的详细内容。

首先2是素数，基于这个前提，所有2的倍数均不是素数，同理，3是素数，所有3的倍数均不是素数，4由于是2的倍数，不是素数，5是，6是3的倍数不是······埃式筛的核心就是通过已知的素数，将不可能是素数的数排除，最后剩下的就是素数。下面开始根据思路设计算法：

我们先假定所有数字都是素数，将所有数字对应的数组下标位置标示置为素数，在Swift中创建数组时使用repeating构造方法即可实现这一步。接下来从2开始处理，标示每一个下标为2倍数的数组元素为非素数，直到倍数大于给定范围。然后继续重复开始处理3，首先判断3是否标示为素数，如果是重复以上操作，不是就直接进行下一次循环。通过用这个方法，可以把程序运行时间大幅缩短。但其实这个算法还是有优化的空间。我们可以很容易知道，除2以外的所有偶数都不是素数，所以我们初始化数组时循环一次，将所有偶数提前标示为非素数，同时在标示非素数时每次倍数从3开始增加偶数倍，以3为例，只需要标示3 * 3，3 * 5，3 * 7，3 * 9的数，并且下一次直接跳过4开始处理5，通过这两个手段，最终可以将程序的运行时间压缩到100毫秒附近。

为什么说这题坑，因为哈希表的标签，我一开始使用字典存储不是素数的数，动态的向字典中添加标示的非素数，除此以外与上面介绍的方法没有差异，但是使用字典的话，运行时间虽然相比试除法有提升，但是仅仅只从3000毫秒提升到2000毫秒，并且耗费的空间几乎翻了三番，消耗空间的剧增我可以理解，因为字典需要存储key和value两个值，但是我不理解为什么使用字典相比使用数组耗费的时间会相差那么大，这可能涉及语言的底层实现差异，只有等未来继续学习才可能明白了。

【205】同构字符串

解题记录

最初我遍历两个字符串，判断两个字符串相比自己的上一个字符是否变化，这个想法漏洞很大，它其实只能观察两个字符串连续与不连续的部分是否相同，但是没法判断是否是同构字符串。思考了许久，想到的办法是用两个字典，分别存储下每个字符串中每个字符出现的位置，以title与paper两个字符串为例，因为是同构字符串，所以在第一个字符串中t的位置与第二个字符串中p的位置是相同的，同理，其它字符也是一样的。我们可以用一个字符每次出现的位置之和代表一个字符的唯一标示码，对两个字符串进行遍历，每次将字典中对应key的value值增加当前字符的下标位，最后再遍历一遍字符串，查看两个字符串同一位置字符对应的唯一标示码是否相同，若不相同则返回false，结束判断。这个方法其实是没有错的，但是在LeetCode中显示执行超时，我个人认为时间复杂度是O(2n)，我本来以为碰到了与204题相似的坑，对代码进行修改使用数组重新测试，但依然执行超时。

正确的答案其实也是使用字典，但是只是用了一个字典，因为同构字符串其实就像简单的加密，将字符两两对应，形成匹配关系，使用对应的字符替换所有原字符，这样得到的就是同构字符串。所以对于同构字符串而言，一定存在key-value结构的两两对应关系，我们开始遍历两个字符串，只要第一个字符串的字符可以取到其对应的key-value关系，并且第二个字符串的字符不匹配该关系，就说明出现了一对多，不是同构字符串。如果第一个字符串取不到对应的key-value关系，并且第二个字符串的字符已经有对应的key-value关系，说明出现了第一个字符串中的字符多对一的情况，也说明不是同构字符串。这题令我困惑的地方在于使用数组反而超时了，与204题完全相反。

【206】反转链表

解题记录

很简单的链表操作题，使用了栈辅助存储链表数据，先遍历链表将每个元素压入栈，然后从栈顶弹出元素创建新的链表，但这题还有迭代法，更为巧妙一些。我们使用三个变量存储相邻的三个节点，以1->2->3这个链表为例，三个节点存储空、1、2，并且每次将中间节点的next修改为上一个节点，同时三个变量向后指一位，这样可以保证不会有节点丢失造成内存泄漏，同时一次遍历即可修改完成，空间复杂的为O(1)，时间复杂度为O(n)。

【217】存在重复元素

解题记录

用哈希表解这个题是最直接的思路，遍历数组，如果哈希表中已存在当前元素就返回true，这个做法时间复杂度和空间复杂度均为O(n)，但是提交后我发现只比50%的Swift题解快，这很不寻常，说明这题还有更快的方法。另一个方法其实就涉及我的知识盲区了，用了一个我没用过的集合类型，Set。集合（Set）用来存储相同类型并且没有确定顺序的值。当集合元素顺序不重要时或者希望确保每个元素只出现一次时可以使用集合而不是数组，这也就意味着，集合中所有元素只会出现一次，不会有重复的元素，我们利用数组对集合进行初始化，会自动的将重复元素删去，这时候比较集合的长度和数组的长度即可知道是否存在重复元素。

【219】存在重复元素II

解题记录

这题与它的第一题类似，依然采用哈希表的思路，用元素的值与数组中出现的位置作为key-value，当出现哈希表中已有的元素时检测当前元素与哈希表中元素的value值的差是否小于题目给定的数值，小于说明出现了重复元素，否则继续遍历并将该key对应的value重置为新的位置。

【225】用队列实现栈

解题记录

在Swift中这题可以直接用数组的基础操作函数实现，但如果在Java中，我会选择用双队列实现栈，因为队列先进先出的特性，使用第二个队列储存第一个队列除了最后一个元素的所有元素，这样就可以获取队列中的最后一个元素了，从而实现栈的各种操作。

【231】2的幂

解题记录

看到题我确实想到位运算了，但是对位运算的性质还不够熟悉，所以也不知道该怎么用位运算来解这个题。使用中规中矩的循环法，每次除2判断是否为2，时间复杂度为 O(log₂N)。如果使用位运算，注意到所有2的幂的二进制数除了第一位是1其余位均为0，这一点我也注意到了，再注意到2的幂-1的数每一位都是1并且比2的幂短一位，将两个数进行与运算，由于两个数每一位均与对方相反，与运算后结果一定为0，根据这条性质我们就能判断出这个数是否是2的幂。但令我好奇的是在LeetCode上提交的时候我使用中规中矩算法的耗时是比位运算的耗时短的，多次测试都是如此。

【234】回文链表

解题记录

这题有两个要求，不使用额外空间以及时间复杂度O(n)，如果没有这两个额外要求我会使用数组将链表中的所有元素存起来，双指针从数组两头开始遍历。但是由于不允许使用额外空间，相当于遍历一遍链表就需要得出答案，查看相关标签，双指针，和我想的没错，但是如何使用双指针对链表进行遍历？其实这题使用的是快慢指针，快指针每次多移动一个元素的位置，从而达到快指针抵达末尾时，慢指针刚好在链表中间的效果。为什么要这个效果呢？我们需要判断的是链表的前半部分与后半部分是否构成回文关系，我们在快慢指针遍历寻找链表中点的过程中，就需要利用慢指针将链表的前半部分倒转过来，也就是说先遍历半趟链表，完成倒置前半部分和寻找中点的任务，再遍历半趟，判断前后是否回文。这里需要注意的是如何在遍历前半部分的时候将前半部分倒置，我们需要用到两个临时变量，一个存储当前慢指针的元素，一个存储已经倒置完的部分，再将两部分拼接在一起，就是我们需要的倒置链表。

【242】有效的字母异位词

解题记录

哈希表是自然而然想到的解决这个题的方法，思路也很简单，将没有的字符添加到哈希表，已有的字符出现次数自增，最后检查两个哈希表同样的元素出现次数是否相同即可。这里需要注意的是，在Swift中，contain方法的时间复杂度为O(n)，如果使用这个方法，就会导致程序耗时大幅度增加，以至于超时。但使用下标直接取key值的话，时间复杂度为O(1)，正确的做法就是使用下标取，这算是Swift里的一个小技巧吧，需要记住。

【258】各位相加

解题记录

这题我的思路是将数字转换成字符串顺序读取，再将字符转换为数字相加，循环直到只剩一位。这是很容易想到的办法，这题还有一个挑战，使用O(1)的时间复杂度完成题目，也就是不循环直接计算。很显然，有一个公式可以得到答案。我没有短时间内直接推理出公式的能力，查看答案后发现公式为 (n - 1) % 9 + 1 ，n是要求的数，算式结果即为n各位相加之和。大概理解了一下公式，我们观察1～20的各位相加的答案，可以发现规律，各位之和是一个1～9循环的数列，那么按理说我们直接使用我们的数对9取余即可，为什么要先减1取余再加1呢？对于因为对9取余的结果只有0～8，以18为例，取余结果为0，但实际上答案为9，我们先减1取余再加1相当于一个补偿措施，避免9的倍数取余结果为0。在LeetCode中，使用循环解决这个题消耗的时间远比使用这个公式速度快，我猜测应该是LeetCode使用的测试样例不够大导致的。

【263】丑数

解题记录

最初想到的是动态规划，如果一个数是丑数，那么它的1/2或1/3或1/5一定有一个是丑数，进而想到了递归，但是考虑到递归的开销太大，又想到前两天的一个题，我想到了筛法，从1开始将自己的2、3、5倍的数标记为丑数，但是这个办法在处理极大的数据的时候会超时，并且占用极大的空间存储丑数的标记，在某个测试样例中跑出了1.2G内存占用的“好成绩”，这个办法虽然可行，但无论是时间复杂度还是空间复杂度都不可接受。但其实这题我陷入了一个误区，以 30 = 2 * 3 * 5 为例，它可以是2 * 3 * 5，也可以是3 * 5 * 2，还可以是5 * 2 * 3，换句话说，因数的乘积顺序不影响这个数是否是丑数。最开始我想到的方法都需要区分顺序，也就是30先除以2、3或5在我看来是不一样的，可能造成不同的结果，这是我踩的一个坑。没有坑的话就很简单了，每次除以2、3或5，不断循环，直到为1或者某次循环中2、3、5均不为因数即可返回答案。

【268】缺失数字

解题记录

这题直接想到了使用等差数列求和公式求出0～n的和，再减去数组中所有元素即为所求。时间复杂度O(n)，空间复杂度O(1)，还有一个方法是位运算，先将0～n进行异或运算，再将数组中所有元素与0～n的异或结果继续异或，最后剩下的就是缺失的数字，同样为时间复杂度O(n)，空间复杂度O(1)。

【283】移动零

解题记录

这题的要求是不使用额外空间+尽可能少的步数解决问题，我想到的是遍历数组，用快慢指针，慢指针指向数组起始位置，快指针每次循环向后挪动一位，当快指针指向的元素值不为0时，与慢指针指向的数组位置交换元素，遍历一趟解决问题，时间复杂度O(n)，空间复杂度O(1)，这也就是最优解。

【290】单词规律

解题记录

这题类似于【205】同构字符串，使用的也是哈希表进行映射判断是否具有一一对应的Key-Value关系，需要注意的是需要在循环内嵌套一层循环读取到字符串代表的单个单词，并且题目没有保证Str串与Pattern串具有数量上的相等关系，所以还需要注意两者长度不同的情况，例如 pattern = "abba", str = "dog cat cat dog cat" 或者 pattern = "abbaa", str = "dog cat cat dog" 。有一说一，Swift对字符串通过下标取字符的语法是真的窒息。

【292】Nim游戏

解题记录

4不可以胜利，同理，如果制造出8的局面也不可以胜利，无论拿几块石头，对手总能拿到只剩4块，同理，12、16都不可以胜利，所以除了4的整数倍，我们都可以胜利。

【299】猜数字游戏

解题记录

这个题目的重点在于如何计数重复出现的但是不在相同位置的B类数字，我们考虑使用哈希表，在遍历字符串的时候将每个数字出现的次数作为value值记录在哈希表中，与此同时将在一个位置重复出现的A类数字记录下来，完成A类数字的计算。然后对guess串进行遍历，若字符存在于哈希表的key中，相当于出现了B类数字，此时记录并将对应字符的出现次数自减。但这就面临一个问题，A类数字同样会被记录为B类数字，所以在之前记录A类数字的循环中我们需要对B类数字进行补偿，每次自减，最后就能获得A类数字和B类数字的数字。