LeetCode刷题笔记（1-99）

【2】两数相加

解题记录

简单的链表合并，只是合并的话其实不难，遍历两个链表，将相加的结果存入新的链表，同时设置进位标记符检查是否发生进位。这里讲讲怎么利用Swift的语法可以把这题的代码写的更短小精悍。一般我们在合并两个链表的时候，合并完以后需要检查两个链表有哪一个还没有到尾，再将没有到末尾的链表单独处理。在Swift中利用可选类型可以将这段代码写的更优雅。

其他语言中，常规的写法一般是这样的：

while linkNode1 != nil && linkNode2 != nil {
		// do something
		linkNode1 = linkNode1?.next
  	linkNode2 = linkNode2?.next
}
if linkNode1 != nil {
  	// do something
  	linkNode1 = linkNode1?.next
}
if linkNode2 != nil {
  	// do something
  	linkNode2 = linkNode2?.next
}

利用可选类型，可以写成这样：

while linkNode1 != nil || linkNode2 != nil {
		// do something
		linkNode1 = linkNode1?.next
  	linkNode2 = linkNode2?.next
}

其实就是单纯把 while 条件中的且改成了或，但是代码依然可以正常使用。假设现在 linkNode1 已经到了尾部，而 linkNode2 还没有，在执行 linkNode1 = linkNode1?.next 的时候由于linkNode1值为nil，linkNode1?.next 的值也就同样为 nil ，而不会崩溃。多利用这样的特性，可以帮助我们写出更 Swift 的代码。

【3】无重复字符的最长子串

解题记录

最初使用了哈希表+双指针，一个指针指向当前子串的开头，用哈希表记录下每个字符出现的位置，一旦发现出现了重复的字符，首先利用指向子串开头的指针计算当前无重复字符的字串长度，然后将该指针改为指向第一次出现的该重复字符，并且将哈希表中所有出现位置在该指针之前的字符移除。以 abcdvdfvdf 为例，最初开头指针指向 a，末尾指针前进直到第6个字符 d 为止，前5个字符没有重复，当发现出现了重复的字符，先计算当前子串长度，也就是两个指针的差，计算为5，代表目前无重复字符子串长度为5，然后在哈希表中移除abcd四个字符，令开头指针指向第5个字符v，然后继续重复以上操作。

第一次提交耗时很不理想，在发现重复字符时，开头指针被我直接指向新的开头，此时移除哈希表中的元素由于没有一个起始标志，需要遍历哈希表中所有元素来进行移除，效率不高。更好的做法是将开头指针递增式的向后移动，每次移动删除对应的字符，直到开头指针移动到第一次出现重复字符的地方为止，这样就不需要记录元素的出现为止了，可以把哈希表改为使用Set集合。

【5】最长回文子串

解题记录

这题有两种比较常用的解法，动态规划和中心扩散法。

先说动态规划的方法，回文串的对称结构天生就适合使用动态规划进行求解，有一个核心性质：一个长度大于2的回文串将头尾都删除后剩下的依然是回文串，我们要利用这个性质来进行动态规划求解。动态规划本质上是一种暴力解法，只不过在暴力求解的过程中可以利用之前每一步的结果简化计算。

我先尝试了暴力解法，遍历每一个可能的子串，对每个可能的子串调用String类的reversed()方法获得一个逆序的字符数组进行回文判断，根据苹果官方文档显示，时间复杂度是 $O(1)$ ，如果按照这个时间复杂度计算的话，暴力解法不同于其他语言，可以达到 $O(n^2)$ 的时间复杂度，而其他语言判断回文串需要额外的 $O(n)$ ，最后总时间复杂度为 $O(n^3)$ ，但是我试下来暴力法的耗时与动态规划和中心扩散有两个数量级的差距，所以时间复杂度只能作为参考，实际时间复杂度其实还有系数与项数，再加上测试用例的不同，相同复杂度的算法也会有巨大的区别。

继续回到动态规划，动态规划快就快在它可以不断利用之前计算过的结果，只需要把所有计算结果保存起来即可，是一种空间换时间的算法。那么我们应该先计算什么呢？每个字符串是否是回文串，取决于这个字符串掐头去尾后是否是回文串，以及这个字符串的头尾是否是相等，于是我们可以得到一个状态转移方程：

dp[i][j] = dp[i + 1][j - 1] || s[i] == s[j]

在这个里面，dp[i][j] 代表字符串中第i～第j个字符组成的子串是否为回文串，s[i] 表示第i个字符。这个式子很好理解，但是我们开始编码时还要考虑一个问题，我们的计算顺序是什么？如果把 dp 作为一个数组保存，每个元素都依赖于它左下角的元素，又由于i不会大于j，所以整个数组有一半的元素是无意义的，我们只需要首先计算对角线的元素即可，因为对角线位于所有有意义元素的左下方，而对角线其实无需计算，对角线元素表示为 dp[i][j] && i == j ，截取为子串就是第i个字符，也就是对角线元素表示第i个字符是否是回文串，单个字符一定是回文串，所以对于对角线元素，直接设置为true，接下来就是与暴力法相同的进行遍历，遍历的时候利用状态转移方程判断是否有效即可，需要注意的是，头尾相等可以直接作为长度小于3的子串的判断方式，无需在进行状态转移。

第二种方法是中心扩散法，中心扩散法的思想就是对每一个可能的中心向左右进行扩展，计算以该点为中心可能的最长的回文串的长度。中心扩散法的难点在于如何区别偶数长度的串和奇数长度的串，偶数长度的串，中心落在两个字符之间，而奇数长度的串中心落在某个具体的字符上，这是最大的区别。

我们考虑使用两个数，左起点和右起点表示一个可能的中心，对于落在字符上的中心，左起点和右起点是重合的，就位于该字符，对于落在字符之间的中心，左右起点分别为中心左右的字符，，通过这样的设计，可以将两种情况合二为一。在得到回文串长度后，还有一个小难点是如何根据中心位置和长度获取回文串起点，这里有一个关系式， $begin = i - (length - 1) / 2$ ，i是当前的中心位置，length是计算出来的回文串长度。

其实解决这个问题有一种时间复杂度为 $O(n)$ 的解法，叫做Manacher算法，但是这个算法确实比较复杂，还没有掌握。

【6】Z字形变换

解题记录

只要找到字符串的规律这题就不难了。我选择的是以行为顺序，也就是找到结果字符串的规律，Z字形的每一行里的每一个字符，下标都是存在规律的，把Z想象成波峰波谷，每一行波峰到波峰，波谷到波谷的距离都是固定的，通过这个固定的距离，可以跳跃式的在原字符串中找到构建新字符串需要的字符，把这些字符顺序的添加到结果中即可。

【8】字符串转换整数

解题记录

这题的难点在于对各种特殊用例的处理，例如溢出、不规范的字符串进行处理。我使用的方法是比较传统的使用if-else判断边界条件对字符串进行预处理，这种方法如果不考虑仔细的话很容易漏过一些特殊的用例，官方题解介绍了一个新的方法，叫做自动机。通过保存每一种状态，以及每一种状态下读取到字符种类的不同决定下一个状态，从而完整的判断所有可能。以这题为例，可以列出一个表格：

	空格	符号(+/-)	数字	其他
开始	开始	赋符	读数	结束
赋符	结束	结束	读数	结束
读数	结束	结束	读数	结束
结束	结束	结束	结束	结束

以第三行为例，如果当前状态为正在读数，那么除非下一个字符是数字，否则均进入结束的状态。

第二个难点是溢出的处理，这题要求溢出时返回最大/小的32位整型数，在Swift中整型的最大值是超过题目的限定的，就不用担心在进行加法的时候溢出，只需要和 Int32.max, Int32.min 进行比较就能知道是否溢出。另外一种方法是每次在进行加法前先进行减法，例如要知道 a + b 是否溢出，我们可以先计算 Max - a，如果 Max - a 大于等于b，就不会溢出，反之溢出。这个判断方法更安全，如果语言中没有长度更长的整型，就需要使用这个方法。

在读取每一位字符转换为数字的时候，我们需要乘以10的相应幂，第二个可能溢出的地方就是计算10的幂的时候，字符串的数字部分可能有几十位，而我们是无法存储10的2、30次幂的，在这里我的处理方式是记录下最大可以存储10的几次方，只要指数小于记录下的那个数，乘法就不会溢出，反之溢出。同样的，这里也有一个通过除法判断是否溢出的方法，同上不再赘述。

【11】盛最多水的容器

解题记录

看到这题双指针的标签的时候我大概想到怎么做了，两个指针不断向中间逼近，一开始我想到的是从高度更低的一侧靠近，因为容器的容量取决于两侧的高度和距离，如果高度低的一侧变高自然就有可能装更多的水。

首先我们将从第a个高度到第b个高度形成的容器记为 $[a,b]$ 。

如果一开始选择 $[0, count-1]$ ，也就是最左侧和最右侧形成的容器，假设0更矮，按照我们的思路，接下来应该比较 $[1,count-1]$ ，这里涉及到一个问题，我们如何肯定为什么 $[0,count-1]$ 是以0为左界限最大的容器，必须解决这个问题，我们才能放心的将指向0的指针右移到1，舍去所有以0为左界限的可能。

我一开始也是不知道如何解决这个问题，只能说凭直觉感觉应该这么做，看了LeetCode的题解想明白的。

如果 $[a,b]$ 这个容器b高于a，将b向左移动，有三种可能，第一种，b-1比b矮，但是依然高于a，第二种，b-1比b高，对于这两种可能，新的容器都只能以a为高，因为a更矮，但是底却缩短了，最后容器变小。第三种可能，b-1比a矮，对于这种可能，不但容器高度变低了，从a变成b-1，底也缩短了，也会变小。

所以可以得出结论，对于 $[a,b]$ 这个容器，如果a的高度比b的高度矮，那么a，b之间不会再有以a为左界限的更大的容器，所以我们需要将a右移进行下一步的比较。

【12】整数转罗马数字

解题记录

这题很像是给一个钱数，问最少能用几张货币凑出给定的钱数，对于这个问题我们就直接使用贪心法，先将整数和罗马数字的对应关系使用哈希表保存下来，每次要找到最大的能够减掉的数，然后将这个减掉的数对应的罗马数字加到结果中，下一次减的数不会大于这次剪的数，所以我们可以令罗马数字对应的整数有序，从大到小来做处理。

【15】三数之和

解题记录

两数之和在LeetCode上是第一题，许多人都做过，比较好的方法就是使用哈希表存储出现过的数字，遍历的时候每次查看哈希表中是否有一个数与当前数相加为给定和，这是两数之和的解法。

到了三数之和，不再是给定和，而是三个数相加为0. 有一个方法利用了两数之和的解法，每次选择一个数，然后求出与0的差，那么我们再找两个数相加等于这个差即可，问题又变成了两数之和。在两数之和中由于数组没有排序，我们必须遍历每一个元素才能找到存在的那个可能，而在三数之和中，我们可以先对数组进行排序，排序后的数组当我们标定了目标数后，寻找两数之和时，可以从排序数组两端开始双指针查找，可以提高查找效率。

【16】最接近的三数之和

解题记录

这题就是在第15题的基础上进行了微小的改动，同样是固定一个值，然后对剩下的数进行双指针遍历，区别在于每次需要计算当前与目标值的距离，然后更新最小距离，最后根据最小距离返回最接近的和。

【17】电话号码的字母组合

解题记录

这题可以使用回溯算法，每次利用 $[0,n - 1]$ 的子串和最后一个字符进行回溯，如果子串为空，返回最后一个字符可能的字母数组，否则对两个数组进行笛卡尔乘积。以"234"为例，第一次回溯处理"23"和"4"，“23"继续回溯，处理"2"和"3”，“2"继续回溯，处理”“和"2”，此时因为第一个参数已经为空，返回"2"可能出现的字符，[“a”,“b”,“c”]，与"3"可能出现的字符[“d”,“e”,“f”]，进行笛卡尔乘积，然后得到的结果与"4"可能出现的字符继续笛卡尔乘积，就能得到需要的结果。

【19】删除链表的倒数第N个节点

解题记录

需要一趟遍历完成这题就需要用到双指针，保持两个指针之间间隔N个节点，当第一个指针遍历到末尾时，删除第一个指针指向的元素即可，需要注意删除头节点的情况，单独进行处理。

【20】有效的括号

解题记录

这道题难得的思路跟官方题解几乎一样，看到这道题的第一时间我立马就想起了用栈解决问题。我一开始想到的是将所有读取到的左括号压入栈，同时每读取到一个右括号就比较栈顶元素是否与其是配对的括号。而左括号和右括号使用字典存储，左括号作为Key，右括号作为Value即可比较左右括号是否是配对的括号。

一开始我没考虑到右括号可能出现在第一个的位置，如果第一个匹配到右括号直接去比较栈顶元素的话，由于此时栈为空，所以会出错，增加判定栈空的条件以后解决了这个问题。然后我的程序如果只有一个左括号也会返回true，在开头写了一个判定条件，如果长度为单数的字符串直接返回false解决问题。我还没考虑到如果字符串全是左括号，全部压入栈后需要在最后判定栈是否为空，只有栈为空才说明所有左括号已经弹出与右括号匹配了。

【21】合并两个有序链表

解题记录

一开始看到这道题我就感觉没有特别灵光的思路，我想到的是把两个链表先拼在一起，再对拼好的链表进行排序。但是涉及到引用值的操作，很容易错误的操作链表。尝试了多次后还是没能通过引用值对链表进行排序的操作，看了下别人的算法，通过新构建一个链表，从两个链表的头部开始读取，将较小节点的值作为新节点的值插入到构建的新链表中，然后继续对比两个链表的头部，直到其中一个为空代表已经有一个链表读取完，那么剩下的就是将另一个链表剩下的值依次插入我们构建的链表的尾部。题目有一个值得注意的点，所给定的两个链表均为有序链表，而这个算法也是符合我们正常思考方式的一个算法。如果给定的两个链表无序就不能使用这个算法了，受到这个算法的启发，在无序的情况下，我可能会先将两个链表的值读入到一个数组中，然后再对数组进行排序，最后用数组中的值顺序的构建一个新链表，从而避免操作引用值。

【22】括号生成

解题记录

这题很容易想到回溯算法，以有三组括号，也就是n=3的字符串为例，一定是在有两组括号字符串的基础上插入了一个连续的紧挨在一起的括号对，可能是插入在开头，可能是插入在末尾，也可能是插入在某一个左括号后，完整的列出n=3的字符串如下：

["()()()", "()(())", "(())()", "(()())", "((()))"]

// 每个n = 3的字符串都是由一个n = 2的字符串，在开头末尾或某一个左括号后插入一个括号对组成的
"()()()" -> "()()" + "()" //在末尾或开头插入
"()(())" -> "(())" + "()" //在开头插入
"(())()" -> "(())" + "()" //在末尾插入
"(()())" -> "(())" + "()" //在第一个左括号后插入
"((()))" -> "(())" + "()" //在第二个左括号后插入

所以设计出一个回溯策略，每次利用n-1对括号的字符串，在开头、末尾和每一个左括号后插入括号对，得到一个完整的可能。但是这么做有一个问题，列举出来的许多结果是重复的。

1 2	`"()(())" -> "(())" + "()" //在开头插入 "()(())" -> "()()" + "()" //在第二个左括号后插入`

以这个为例子，同一个n=3的字符串可以有两种构造方式，为了解决重复的问题，我使用Set作为存储结构，进行去重，但是根本上还是没解决出现重复结果的问题。以n=5为例，有42种字符串，但是这个算法实际上构造出了360种字符串，其中很多是重复的。

还是观察n=3，当有3对括号时，有那么几种构造方式：

将所有n=0的可能放在一对括号中，再将n=2的所有可能放到末尾；
将所有n=1的可能放在一对括号中，再将n=1的所有可能放到末尾；
将所有n=2的可能放在一对括号中，再将n=0的所有可能放到末尾。

这么做最终可以做到不重不漏，。

但是比较令我震惊的是在Xcode中，第一种使用Set去重的方式比第二种在n较小时几乎快一倍，当n增大到10以上时，依然有50%以上的速度优势。

我做了个实验，以n=10为例，第一种方式每次得到的结果只与n-1的结果有关，最终回溯函数调用9次。第二种方式每次的结果与0～n-1都有关系，虽然我们可以保存每次的结果，但是调用函数也会有性能开支，最终回溯函数被调用149226次，并且随着n继续变大，第二种方式的函数调用次数会更快的指数级增长，这可能就抵消了第一种方式里Set去重和重复枚举带来的性能损失。

【24】两两交换链表中的节点

解题记录

将两个一前一后的节点分别命名为a和b，我们首先用一个temp指针指向a的上一个节点，然后将a的下一个节点改成b的下一个节点，此时a已经连接到了b的下一个节点，b可以和他的下一个节点脱离连接，将b的下一个节点指向a，完成a和b的交换，但是此时还要将temp的下一个节点指向b，才能让之前的链表与当前交换后的后半部分连接。然后将temp指向a，此时temp的下一个节点就是下一对一前一后的节点中靠前的一个，命名为a，a的下一个节点就是b，继续循环即可。

【26】删除排序数组中的重复项

解题记录

我第一次做这个题的时候调用了Swift内置的API，remove(at index: Int)。当时对Swift的理解还不够深入，我觉得时间复杂度是 $O(n)$ ，但其实这个API本身也具有一个线性的时间复杂度。这题的思路还是双指针，但是不需要把重复的元素删除，每次两个指针指向的元素不相等，就对第一个指针指向的下一个位置重新赋值。

【27】移除元素

解题记录

这题和【26】题比较像，直接遍历如果是需要移除的元素就移除，这题第一次用Swift提交就过了，简单的难以置信。但是正好因为这题和【26】题我都是使用Swift进行解答的，我试着用Java去进行解答就发现了一个问题，在Swift中我使用了remove函数来移除数组的指定元素，这个函数移除了指定元素后会将后续的元素自动往前移动，这省去了很多事情，但是在Java语言中，并不存在这样的一个函数供我们调用，所以这题使用其他元素来进行解答的话会更加困难。在Java中，需要用快慢双指针，当快慢指针同时指到需要删除的元素的时候，快指针向后移动到不是要删除的元素为止，然后将值赋给慢指针所指向的数组元素

【29】两数相除

解题记录

首先处理特殊情况和溢出情况，除数如果为1，直接返回被除数，除数如果为-1，有可能会溢出，如果被除数是32位有符号整数的最小值，此时无法返回该数的相反数，只能返回32位有符号整数的最大值，除此之外，其他情况直接返回被除数的相反数。

然后处理符号，我们要将所有除法简化为正数除正数的除法，判断除数与被除数的符号，设置flag变量标识正负号，然后取除数和被除数的绝对值，进行计算。对于两个数相除，最容易想到的就是看被除数可以减去多少次除数，结果就为多少。这个方法可行，但是效率低。

我们以 $63\div2$ 为例，首先判断被除数是否小于除数，小于的话返回0，否则另商等于1，再设置一个临时变量，值与除数相等，在这题中即为2。因为2小于63，所以商至少为1，然后倍增2为4，由于4依然小于63，所以商也可以倍增为2；继续倍增4为8，4小于63，商倍增为4；
倍增8为16，16小于63，商倍增为8；
倍增16为32，32小于63，商倍增为16；
倍增32为64，64大于63，停止倍增商。

此时商为16，说明被除数63里至少有16个除数2。然后对63的剩余部分31继续进行这一个操作，累加我们得到的商，就能得到结果。

可以用二进制理解这个方法，以63为例，二进制表示为111111，我们令临时变量为除数2，二进制表示为10，不断倍增除数，可以找到63里最靠左的1表示多少个2，不断重复就能得到63中所有的1加起来表示多少个2。

【31】下一个排列

解题记录

这题我自己没有想出来，看的官方题解。对于一个排列，如果是逆序的排列，就不会有下一个排列，例如54321，没有下一个排列。有下一个排列的排列，一定有至少一个位置后一个数大于前一个数，这样的话交换两个数就能得到更大的排列，所以我们从数组的末尾向前遍历，寻找一个符合后一个数大于前一个数这样条件的位置。

如果我们找到了这个位置，我们需要从这个数之后找一个更大的数和这个数交换，为了找到下一个排列，我们需要找到尽可能小的更大的数，例如1236542，3-6这个位置，是符合我们条件的位置，而3之后更大的数有6、5、4，而尽可能小的更大的数，指的就是比3大的数里尽可能小的数，那个数与3互换就完成了一半的工作。

从最小的排列，例如123456，到最大的排列654321有一个规律，顺序排列小于逆序排列，在排列中的局部也有这种性质，例如123654大于123456，因为456是顺序的，654是逆序的。由于我们寻找位置的原理是找到第一个后一个数大于前一个数的位置，所以这个位置以后的排列一定是逆序的。还是以1236542为例，我们找到的位置是3，3后面的6542是一个逆序的子排列，并且3与4互换后，6532依然是逆序的，此时我们只需要将6532逆序就能得到这四个数的最小的排列，得到的1242365就是下一个排列。

总结一下，主要分三步，第一步找到第一个后一个数比前一个数大的位置，找到这个位置说明可以从这个位置之后找一个更大的数来与之互换形成更大的排列；第二步，在我们上一步找到的位置之后找到一个尽可能小的，但是比这个位置大的数，将找到的数与上一步找到的位置进行互换；第三步，互换后将后面的子序列逆序，得到下一个排列。

【33】搜索旋转排序数组

解题记录

看到时间复杂度要求为 $O(logn)$ ，题目又与查找一个元素有关系，就应该想到二分查找。对于这个数组，由于无序的位置只有一个，也就是说对于任意的一个元素，左右两侧形成的数组，一定有一个是有序的，对于有序的那个数组，我们可以判断我们要寻找的target是否落在该有序区间内，如果是，就进入这个区间进行二分查找，此时就是常规的二分查找，如果没有落在这个区间内，说明我们要寻找的元素可能在另一个无序区间内，此时进入无序区间继续上述操作。

【34】在排序数组中查找元素的第一个和最后一个位置

解题记录

这题还是考察了二分查找，用二分查找查找左边界和右边界的知识。与普通的二分查找不一样的地方在于查找到给定的目标时，并不是直接返回，而是根据要查找的是左边界还是右边界，对当前的边界进行收缩。具体的细节在博客内转载的二分查找细节详解中已经提到过这种情况了。

【35】搜索插入位置

解题记录

我一开始对排序数组进行遍历找到目标位置，十分容易就能找到我们需要的位置。但是实际上这题更好的解题方法时使用二分查找。因为给定的数组是已经排好序的，且无重复元素，使用二分查找法可以更快速的查找到目标值所在的位置，唯一需要注意的就是二分查找法左标和右标如何改变以及最后返回什么值，特别是要注意当目标值大于数组最大值或者小于数组最小值时，如何使用二分查找法进行查找。

【36】有效的数独

解题记录

判断一个数独是否有效主要看三个方面，每一行、每一列和每一个宫格内1-9各出现且只出现一次。对于行、列和宫格三种情况需要分开判断。对于每一行每一列每一个宫格，我们创建一个哈希表，一共27个哈希表。我们可以很容易从数组的下标确认这一个数属于第几行第几列，确认了这个以后，可以将得到的数保存到对应的哈希表中，每个数需要检查对应的三个哈希表中是否存在，如果对应的哈希表中已经有这个数，说明这个数在这一行/列/宫格已经出现过，此时说明数独无效。

稍微有一点难度的就是通过数组下标确认宫格，宫格按照从左到右从上到下的顺序，依次标号为0-8，对于board[i][j]有如下关系：boxIndex = (i / 3) * 3 + j / 3，这个关系的由来就不说了，在纸上画一画很容易就能得到。

【39】组合总和

解题记录

以数组[2,3,5]，目标8为例，我们要凑出一个8，如果已经有一个2，我们只需要从剩下的元素中凑一个6，如果又有一个2，我们再凑一个4，以此类推，我们最后已经有了3个2，还需要凑一个2，在数组中找到2，可以返回得到一个答案[2,2,2,2]，我们返回到有一个2需要凑6的地方，因为已经寻找了所有2可能的结果，接下来我们以3为基础，先凑出5，然后在数组中寻找3，以此类推，就可以找到所有答案。

【40】组合总和 II

解题记录

这题与39的区别就是不能使用重复的数字，我们需要对数组进行排序，思路与39相似，对数组进行排序后下一次进行回溯的时候就只需要寻找当前数字以后的数组，而不需要寻找整个数组。

【43】字符串相乘

解题记录

这题的思路是模拟竖式乘法的过程，如果模拟竖式乘法，以 $123\times456$ 为例，需要计算3次乘法， $123\times6,123\times5,123\times4$ ，再把三个乘积相加，进行2次加法，最终得到答案。这个方法实际操作起来是比较麻烦的，加法和乘法要分开处理，多了很多处理步骤。我们可以在进行乘法的时候同步进行加法。

以这题为例，我们实际上执行了9次个位数的乘法，每次乘法得到的结果都可以累加到一个具体的位，例如 $2\times5$ 的结果是10，对应到结果的第3位，此时就参考第2位是否有溢出，对第3位的结果进行更新。所以我们需要找到每次乘法的结果会对应到哪一位，第一个乘数的第i位与第二个乘数的第j位相乘，对应到结果就是第i+j位，使用一个数组保存每一位的结果。

【46】全排列

解题记录

这一题思路上有点类似【22】括号生成，使用递归的方式每次获得除了最后一个元素的子数组的全排列，然后将最后一个元素依次插入每一个可能出现的位置。以[1,2,3]为例，首先获取[1,2]的全排列，而要获取[1,2]的全排列，要获取[1]的全排列，也就是[[1]]，将2分别插入1的前面和后面，可以得到[[1,2],[2,1]]，这便是[1,2]的全排列，再将3插入[1,2]的每一个位置，可以得到[[3,1,2],[1,3,2],[1,2,3]]，再将3插入[2,1]中，得到[[3,2,1],[2,3,1],[2,1,3]]，与之前得到的3个结果加起来就是[1,2,3]的全排列。

【49】字母异位词分组

解题记录

要对字母异位词进行分组，首先要知道互为异位词的单词有什么共同特征？一开始我使用了排序，对每个单词按照字典序进行排序，如果两个单词互为异位词，那么两个单词排序后的结果也是一样的，以排序后的单词作为哈希表的键，就可以将所有排序结果相同的词作为值添加到对应的键值对中。这个方法可以通过LeetCode，但是耗时不是最优。基本的思路已经正确了，就是要提取异位词的共同特征作为哈希表的键，通过哈希表对具有共同特征，也就是异位词进行分组。

两个单词如果由同样的字母组成，那么对两个单词进行字符计数，得到的结果一定是相同的。使用这个特征来进行归类，只需要 $O(n)$ 的时间就可以对一个单词进行分组，而如果使用排序的话，需要 $O(nlogn)$ 的时间。

【50】Pow(x, n)

解题记录

题目的标签里有二分查找，有点迷惑了思路。这题要使用递归的思想，对n进行递归，求解 $x^n$ 可以由 ${x^{\frac n2}}^2$ 这个式子得到，但是n不一定是偶数，如果是奇数的话，需要再额外乘上一个 $x$ ，如果想不到递归的思路，这题就会没有头绪，知道了递归的思路以后这题就变得很简单了。

【53】最大子序和

解题记录

直接看到这个题确实没有思路，只能想到用暴力遍历，看看所有1个数、2个数、3个数、N个数的组合中谁的和最大便返回谁。这肯定不是最好的思路，查了一下这题要用动态规划法，而动态规划是对贪心算法的改进，它一般可以用于解决无后效性和最优子结构的问题。无后效性意思是给定一个阶段的状态，未来的发展不受这阶段以前状态的影响，也就是未来与过去无关，最优子结构意思是大问题的最优解可以由小问题推出。以这题为例，要求最大子序和，我们要知道给定的数组的某一部分的最大和，而对于给定的数组的部分，我们只关心给定数组的最大和，而不关心是如何得到的，这就是无后效性。而包含数组的最大子序和的子数组，这个最大子序和也必然是子数组的最大子序和，这就是最优子结构。

这题要求整个数组的最大子序和，可以从第一个元素开始，先求第一个元素的最大子序和，然后求第一个元素与第二个元素和在一起的最大子序和，以此类推。最终遍历一次数组就可以完成寻找最大子序和的任务。时间复杂度为O(n)。

【54】螺旋矩阵

解题记录

我们可以模拟人螺旋式读取矩阵的方式，首先是在第一行从左到右，然后在最后一列从上到下，最后一行从右到左，第一列从下到上，这样可以完成最外一层的读取。然后进入里面一层，以同样的顺序读取，如此重复直到读取完毕。我们只需要设置边界，读取的时候以边界为限定，以固定的顺序读取贴合边界的四条边，每次读取完一圈后更新边界即可重复读取。

【55】跳跃游戏

解题记录

一开始我感觉这题应该是要用回溯+贪心，每次往后跳跃能跳跃的最大步数，遇到无法跳过去的情况，也就是0，就回溯到上一个不为0且没有访问过的节点，如果回溯的时候回溯到数组的起点，说明无法跳到终点，这个方法可以通过LeetCode，但是耗时很糟糕。实际上官方题解有 $O(n)$ 时间复杂度的方法，只需要遍历数组，维护一个可以达到的最远距离，每次判断当前遍历的点是否在最远距离以内，如果在，说明可以跳到这个点，此时利用这个点的值更新可以达到的最远距离。如果不在，说明无法跳到这个点，直接返回false即可，实在是很妙的方法，自己为什么就想不到。

【56】合并区间

解题记录

一开始想到的方法是创建一个数组模拟数轴，依次读取每一个区间，填充“数轴”，最后读取数轴有数的位置即可知道答案。但是这个方法无法在开始的时候确定数组的长度，而且如果区间并不多，但是区间之间间隔非常大，会造成极大的空间浪费。

正确的方法是首先将区间按照起点排序，我们只需要观察后一个区间的起点是否落在前一个区间内就可以确定相邻的两个区间是否可以合并了。需要注意的是在Swift中需要给数组进行排序的话，需要使用到 func sorted(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> [Element] 显式的指定排序规则。

【58】最后一个单词的长度

解题记录

看到这个题一开始就能想到从字符串尾部开始遍历，直到遇到空格结束遍历，记下这段时间中的字母个数即为所求。这题没太大的难度，困扰我的地方是我不知道如何用Swift对字符串进行从后往前的遍历，查找了资料以后才明白在Swift中需要将字符串先转换成字符数组，但由于Swift只有for-in循环，没有Java-like的三段式for循环，所以在循环条件上也有所不同，算是学到一些语法上的小技巧。

【59】螺旋矩阵 II

解题记录

这题和螺旋矩阵I是相似的，使用的方式都是按层模拟，区别在于之前那题是按层读取数据，这一题是按层填充数据，过程非常相似。

【60】第k个排列

解题记录

我们首先观察4位数的排列：

我们可以观察到一个规律，排列一定是分组出现的，4位数的排列，可以分为4组，以1开头的，以2开头的，以3开头的和以4开头的，每一组有6个排列。

我们用以3开头的排列为例，又可以继续分组，第二位为1、为2、为4的又可以分为3组，每一组有2个排列。

现在假设我们要找第15个排列，首先根据第一次分组的结果，第15个排列一定位于第3组，准确的说，第13-18个排列都位于第3组，所以第15个排列的第一位就是3；然后确认第二位，因为第三组从13-18，13-18被我们分为了3个组，15处于第二组的第一个位置，所以第15个排列的第二位就是2；然后确认第三位，同样的，以32开头的排列可以分为两组，321X，324X分别为一组，因为在上一位的时候处于第二组的第一个位置，所以在这一位就处于第一组，也就是321X；最后3214自然就是我们要找的。

基础的思想就是将位数对应的数字不断分组，每找到一个父组，就能确定一个位置的数。

【61】旋转链表

解题记录

这题有两种思路，都是 $O(n)$ 级别的时间复杂度，我用的思路是首先找到新的头的位置，在这里断开，再将链表的末尾与当前数组的头相连。LeetCode官方的思路是首先将链表的头尾相连，然后再去寻找需要断开的位置，得到新的头，两种思路本质上都差不多，只是执行顺序有不一样。

【62】不同路径

解题记录

很容易就能发现一个网格的路径数量是它左侧网格的路径数量与上方网格的路径数量之和，我们用符号化语言表示，将长m，宽n的网格的路径数量记为(m, n)，那么(m, n) = (m - 1, n) + (m, n - 1)，有了这个关系，我们就可以使用递归的方式求解，递归是最容易想到的，代码也最简单：

class Solution {
    func uniquePaths(_ m: Int, _ n: Int) -> Int {
        if m <= 1 || n <= 1 {
            return 1
        }
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)
    }
}

但是递归效率很低，计算了大量重复的网格，我们可以使用动态规划进行优化，动态规划的状态转移关系与上述递归的关系相似，思想就是保存每一个网格的路径数量，只计算一次，第二次使用时直接调用保存的数据，减少重复计算量，我们可以使用一个二维数组保存计算的结果，首先将二维数组的第一行与第一列全部填充上1，接下来依次遍历每一个位置计算即可。

继续优化的话可以将二维数组改为一维数组，由于每次计算(m, n)都只依赖(m - 1, n)和(m, n - 1)，在二维数组中，(m - 1, n)在(m , n)的上面，(m, n - 1)在(m, n)的左侧，我们不断维护一个一维数组，每次array[i] += array[i - 1]，直接用自身的值表示之前位于上面的那个值，最后数组末尾的值就是我们需要的那个值，问题解决完成。

【63】不同路径 II

解题记录

相较于上一题，这题加入了障碍物的设定，对于有障碍物的单元格，路径数量为0，除此之外与上一题是相同的，都是采用动态规划和滚动数组进行题解。

【64】最小路径和

解题记录

这题是动态规划路径问题的第三题，思路还是一样的，使用滚动数组记录每一列的路径和，第一列的值等于上方方格的路径和与当前方格的路径值之和，第一行的值等于左侧方格的路径和与当前方格的路径值之和，对于其他格子，路径和等于上方和左侧更小的路径和与当前方格的路径值之和。

【66】加一

解题记录

这题看到题目的一瞬间想到的其实还是将数组转换为一个整型数加一后再取各位为数组元素返回数组。但是稍微多思考一下就想到由于只有进位和非进位的区别，从数组后向前进行遍历，如果元素为9，就将其重置为0，同时挪到下一个元素，直到数组元素不为9，对该元素加一，完成操作。第一次提交没有通过，我忽略了有个问题，当数组元素全为9的时候，如果不改进的话会导致数组下标溢出，所以增加对数组下标的检测，当数组下标为-1的时候，向数组头部新插入一个0，即可完成题目，时间复杂度为O(n)，最坏的情况下，例如数组元素全为9也只需要遍历一遍数组。

【69】x 的平方根

解题记录

这个题我使用了二分查找法进行根的查找，对于所有大于4的数，其平方根不会大于自身的一半，又由于这题只求平方根的整数部分，所以当二分查找的中间位置的平方小于目标数，中间位置+1的平方大于目标数时返回此时的中间数即可求出平方根，再针对1进行单独的处理。

【70】爬楼梯

解题记录

前两天做53题的时候正好学习了动态规划的相关知识，看到这题就想到可以用动态规划来做，仔细分析题目，每一次可以爬1或者2阶楼梯，这就意味着我们要知道n阶台阶的爬楼梯的方法，需要知道n-1阶与n-2阶的方法，n-1阶再爬1阶，n-2阶再爬2阶就是n阶台阶的所有方法。分析完毕这题就十分清晰了，其实就是斐波那契数列的求解，一开始我使用了递归，结果在LeetCode上运行的时候就超时了，递归在问题规模变大的时候确实是一个比较差的选择，尤其是这题当规模上升到数十个台阶以后，递归的运行速度将会肉眼可见的慢。最后将递归转成非递归，解决问题。

【71】简化路径

解题记录

顺序遍历字符串，使用栈记录路径顺序，如果遇到"/“就判断记录下来的路径，如果是”…“就要将栈顶元素弹出，如果是”“或者”.“无需进行操作，如果是别的就要压入栈。遍历完字符串后，栈内元素的顺序就是我们的路径顺序，在中间依次插入”/"就能得到答案。

这题利用一些API可以简化代码，我们可以使用func split(separator: Character, maxSplits: Int = Int.max, omittingEmptySubsequences: Bool = true) -> [Substring]函数，设置分隔符为"/"，得到一个数组，数组中的每个元素就是每个子路径，然后按照同样的逻辑判断需要压入还是弹出，最后得到栈后，可以使用func joined(separator: String = "") -> String，将数组内的元素按照给定的分隔符拼接成一个新的字符串。

【73】矩阵置零

【74】搜索二维矩阵

解题记录

这题实际上还是一个二分查找，先找到这个数可能在哪一个子数组中，然后再去对应的子数组中搜索。

【75】颜色分类

解题记录

一开始我想到的方法也是记录下0和2的个数，然后通过个数对数组进行重新赋值，需要遍历两遍数组，使用常数空间。只遍历一次的做法我已经想到一点点了，但是细节没搞清看了题解。

我们从头开始遍历数组，设置两个指针分别指向数组的开头和末尾，如果一个元素是2，那么肯定要将这个元素与末尾的元素对调，如果一个元素是0，将其与开头的元素对调。这里涉及到一个问题，也是我没有想明白的地方，如果我们将2与末尾的元素对调，末尾的元素也是2怎么办？

首先我们要先弄明白，当前指针左侧的元素是什么，当前指针左侧是已经有序的，只包含0和1的序列，并且左侧的指针指向第一个1，我们在下一次搜索到0的时候要将0与这个1对调，并且指针右移到下一个1，也就是说，我们在将当前指针与开头的元素进行对调的时候，是可以保证调过来的元素一定是0或者是1。但是如果当前指针与末尾的元素进行对调的时候，无法保证对调过来的元素一定是1或是0，也就无法维持这样的一个有序状态。所以我们在末尾的元素对调过来的时候，不能移动当前指针，需要继续对当前指针进行判断，如果为2就继续与末尾的元素进行对调。

【77】组合

解题记录

我们如果要求1-4的2位组合，我们可以确定第一位最大只可能为3，如果第一位为4，就无法再找到两位组合，所以我们首先将结果集合设置为[[1],[2],[3]]，对于结果集合中的每一个数，我们需要尝试添加一位得到多一位的组合，对于1，我们可以将2-4与1添加，得到新的组合，对于2，我们可以将3-4与2添加得到新的组合，得到多一位的组合，此时已经得到两位组合，可以返回结果。

但是如果要求1-6的3位组合，步骤其实也是相似的，求出所有两位组合后，继续尝试添加一位得到三位组合，对于每一个已经求出来的两位组合，从组合的最后一个元素开始遍历到n - k + 1，n为数字的总和，k为当前离最终目标还缺的位数，这其中的数是可以添加到第三位的数。比如已经有一个两位组合[1,2]，此时n=6，k=1，所以最后一位是可以遍历到6的，如果要求的是四位组合，则n=6，还缺两位，k=2，此时只能遍历到5，需要留给第四位空间。

【78】子集

解题记录

首先，无论对于任何数组，空集一定是它的子集，也就是 [] ，所以我们可以在一开始就把空集加入到结果集合中。数组的子集与它的子数组的子集又是有关系的，例如[1,2,3]的子集是[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]，而[1,2]的子集是[[], [1], [2], [1, 2]]，观察可以发现，将[1,2]的所有子集末尾加上3，再添加到子集中，就是[1,2,3]的所有子集。

【79】单词搜索

解题记录

从每一个可能开始的单词进行深度优先搜索，搜索的时候要注意，不能使用重复的元素，所以需要再使用一个数组保存访问状态，标记已经访问过的元素，对于每个元素的上下左右四个元素，检查下标溢出，检查元素是否被重复使用，对满足要求的元素进行深度优先搜索，搜索单词的下一个字符。

【80】删除排序数组中的重复项 II

解题记录

【83】删除排序链表中的重复元素

解题记录

这题没有难度可言，就是在考察对链表的操作，也是我刷LeetCode以来第一次没有本地测试直接提交就通过的题。

【88】合并两个有序数组

解题记录

这题与合并两个有序链表很像，我直接就想到了双指针的方法，与合并两个有序链表不同的是这题需要将两个有序数组合并到给定的第一个有序数组中，这就涉及到一个问题，假设第二个数组的第一个元素小于第一个数组的第一个元素，此时将第二个数组的第一个元素赋值给第一个数组的第一位，则第一个数组的第一个元素的值就丢失了，所以我们需要申请额外的空间使用一个辅助数组存储排序值，时间复杂度为 $O(n+m)$ ，空间复杂度为 $O(m)$ ，m，n分别为两个数组的长度。但是这题有更巧妙的解法，同样是双指针，如果从后往前而不是从前往后，就能不申请额外空间，直接将最大的值排到第一个数组的尾部即可，这么做就不会覆盖任何我们需要用到的值，从而也就不用申请额外空间，时间复杂度没变，空间复杂度大大降低为 $O(1)$ 。

【89】格雷编码

解题记录

n位的格雷编码，可以由n - 1位的格雷编码推导而出。我们观察n = 2和n = 3的格雷编码：

1 2	`[000,001,011,010] // n = 2 [000,001,011,010,110,111,101,100] // n = 3`

不难发现，n = 3的格雷编码的前4位与n = 2的格雷编码是一样的，与此同时，后4位的数字在不考虑最高位的前提下，是前4位的逆序。这也好理解，第5位如果想与第4位只有一位的差距，因为前4位已经将所有0开头的编码用完了，所以第5位与第4位的区别就是第5位的最高位从0变成1，其余位不动。由于第5位后面的每一位要与前一位相差一位，而第4位与前面的每一位也已经相差了一位，所以我们可以在第5位之后逆序的套用前4位除了最高位的结果。同理可以推广到第n位和第n - 1位，递归的解决这个问题。

LeetCode刷题笔记（1-99）

LeetCode刷题笔记（1-99）

解题记录

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录

相关标签

解题记录