leetcode刷题记录

原创文章，转载、引用请注明出处！

---

• hard：4、458

• medium：2、3、5、6、11、12、15、17、56、148、165、189、215

• easy：*1、7、9、20、21、26、27、53、66、70、88、*118/119、141、202、206、*231、283、*461、*2073

• 重难点：2、3、^4、5、15、20、21、53、70、141、148、206、215

---

2. 两数相加 [LinkList]

按顺序加，主要就是保持一个进位flag，以及如果最后有进位，需要再新设一个node，值为1。

3. 无重复字符的最长子串 [array]

设两个指针head和tail，分别从0和1开始，tail每次向下走一个，head走到在[head（包）,tail（不包）]区间内跟当前tail重复的位置，显然这个重复位置如果有的话那么就只有一个，如果无重复，那么head不动即可。每次tail走动一下后，将其区间长度的最大值保留即可。tail从头到尾走一遍就可以得到答案。

题解有提示到查看是否重复和以用到一些容器，比如python中的set和cpp中的map。上面解法时间太慢也是因为判断是否重复我没有用这类容器，但实际上也省下了空间，时间换空间属于是。

4. 寻找两个正序数组的中位数 [array/num/技巧题]

把两个数组放到一个里面，然后返回中位数即可。放的时候都从头循环，谁小就放谁。其中一个放空之后，把另一个剩下的所有跟上前面，就能保证新的依旧是有序的。

这题作为hard是因为要求的时间为O(log(m+n))，这样的话就需要二分查找来解决，说实话给的解析确实没看懂。

5. 最长回文子串 [array/DP/技巧题]

首先是好理解的方法，就是将这个倒置串，寻找本体和其倒置的 最长公共 回文 子串。该做法的时间和空间都是0(n*n)。对于这两个操作分两部分走：

• 最长公共子串就是设置一个len*len的数组arr，初始全部置0，从头循环，如果两个指针i、j指的字符相同，那么其状态就是他们的前面的最大子串长度+1，也就是arr[i][j]=arr[i-1][j-1]+1。这里需要注意的是当i和j是0的时候要单独判断。设置2个容器记录这个长度和末尾位置，每当当前的长度（arr[i][j]）大于记录的长度，那么就以当前的长度和i替换这两个记录容器。

• 在上述进行两个容器的记录之前需要判断这一段是否是回文串，具体做法有两种，一种就是把这一段整体取下来整体判断，另一种就是判断最末尾一位的下标。

在这里，对最长公共子串的求法是DP，而对这个题目本身有DP的做法，这两者的状态转移是完全不一样的，要区分好。

其次，还是要了解本题的扩展中心法和Manacher算法

6. Z字形变换 [array/num/技巧题]

没啥好说的，几行就设置几个str，按顺序往里存，最后从上到下排成一行。也可以找规律，每一行都是从某一位开始，间隔多少个数取（这个数肯定是不一样的）。

7. 整数反转 [array/num]

反转有符号整数，超过[−231, 231 − 1]就返回0。

常规方法设置一个n，每次对x取10的余数，再加上10倍的n（相当于前一位的进位）。

使用python的切片可以反转str，将int保留符号，转成str，然后再添上符号。

一定要注意反转后的数字有可能超过范围。

9. 回文数 [array]

判断一个数从前向后读和从后向前读是不是一样的，是就称为回文数。

常规思路就是和7. 整数反转，一样的操作，把这个整数反转然后看他们是否相等即可。偷鸡思路还是使用python切片反转str。

注意，负数一定不会是回文数，因为多个符号。

11. Container With Most Water [array]

直接两层循环会TLE，评论做法是从头和尾开始相对着走，实际上就是考虑了坐标轴长度，保留最大的h然后逐渐缩小坐标轴长度，时间O(1)。

12. 整数转罗马数字 [num/技巧题]

写好个位数，然后替换即可，替换规则都是相通的。

题解里有提到用贪心，就是写好1000、900、500、400、100、…，以9和4的开头是需要用减法构造的，单独写出来，剩下的所有内容都可以用加法构造，所以就每次用num减去最大的，说是贪心，但这是贪心的意义么，后面写到这类题再说。

15. 三数之和 [num/技巧题]

面试重点。

首先，思路方面，三重循环肯定是TLE，那么就力争变成二重循环。最外面的一层循环肯定不能省略，那么就要对里面的两层动心思。做法就是先排序，然后对内层的[i+1,n]区间的循环，设置双指针，j从i+1向后走，k从n向前走。能这么的核心就是因为排过序，前后操作是对应的。判断的时候，如果是0，那么记录结果，如果不是，就看是比0大还是比0小，结果比0大证明后面加的两个数过大了，那么k就往小变；同理，结果小了证明所加的数不够大，那么j就往大变。

其次，操作方面，比较重要的就是去重，对于ijk共同来说，就是要跳过相同的数，因为相同的数判断过会出现相同的结果，这里同时做到了去重和优化循环；对i来说，单独有一个优化，就是排了序之后，大于0的i，j和k都会大于，三个大于0的数相加必大于0。

最后整体做下来，排序用的是O(logN)，循环遍历用的是O(N*N)。

以及并不能为了去重而对nums上来就做去重，写题的时候就一直疑惑，写总结的时候突然发现确实不能这么写，不解释，懂得都懂。

17. 电话号码的字母组合 [DP]

并不算难，实际上是最简单的那种DP：把之前的内容，每一个都重新加上新加的这个就行。就是要记得对每个老内容，添加3或4个新内容之后，把老内容删了。

上述写法模拟了一个队列的操作，每次都操作队头的那个就行，count则控制每新添加一个数之前一共有多少老内容。

20. 有效的括号 [技巧题]

模拟栈（先进先出）的存储方式匹配括号序列。

21. 合并两个有序链表 [LinkList]

新设一个头和操作这个头的操作指针，两个链表从头遍历有两个操作指针，当前两个指针哪个指的值小，就把这个node接上，该node后面断掉，指针向前走一个。最后一定记得把两个表中剩下的部分接上。

26. Remove Duplicates from Sorted Array [array]

给定按非降序排序的整数数组nums，请删除重复项，以便每个唯一元素只显示一次。元素的相对顺序应保持不变。

这题返回值只有k，但检测结果还是操作num变成前k个不重复的值。

27. Remove Element [array]

将所有非val的数挪到list最前面，不论顺序，返回非val的个数。

与283. Move Zeroes同一个原理，就是把0换成是val然后做一个反向问题，代码都是一个逻辑，也是需要注意list长度是0或者list内没有要操作的数。

细细看了下，与26. Remove Duplicates from Sorted Array应该也是同理，在26的去重中，无非就是把k=0，k=val换成了动态的k，就是当前的重复的那个值。当然，能这么想只存在于26是有序的，无序的话就不是这个道理了。

时间O(1)，循环指针每次变动到新的不重复的值上，然后交换到当前k的位置，两件事情分开做就行。

53. 最大子数组和 [num/DP]

求在一个整数数组内，和最大的子序列的这个和。

屏蔽掉的是暴力求解，肯定TLE（亏我还想了半天，用矩阵存储了一部分结果，把每个子列求和的N省略了，以为从O(N^3)变成O(N^2)，TLE之后再一寻思，nmd用切片和sum函数求和好像也是线性，人家本来就是O(N^2)，我优化了个寂寞，我是个逆天）。

上面代码确实没体现出DP，好像就是用了常规的规律，但确实是DP的思想。

以及，这题是easy就多少有点说不过去了。

56. Merge Intervals [array]

融合所给区间，区间相交取交集。

自己想的方法：先求从第几个位置到第几个位置需要融合，然后融合了放进新的result，做得很复杂，要考虑开头结尾长度啥的，搞了半天还写的不对。

看评论区，实际上这题的思路非常简单，就是从头遍历，设置一个指针i，从0开始，看i和i+1，左区间是i[0]，右区间是max(i[1],i+1[1])。如果有融合，那么指针不动，没有做融合操作，指针再向前走。

66. Plus One [array]

设置一个进位flag。时间O(1)循环。

注意最后一位如果进位的话，要在第一个位置多加一个1.

70. Climbing Stairs [DP/array]

dp问题，本质上是fib，重点。

最高赞解释：

递归fib肯定会TLE，两种做法，一种是设置n个空间，一种是就用两个空间做连续数组存放。

这题也能看作是DFS，左子树是走一步，右子树是走两步，结果就是这棵树的子节点数量。

88. Merge Sorted Array [array]

两个升序数组融合，要求在nums1上修改。

这题有几个坑，首先如果用python的话，直接使用nums1=这种赋值方法，会改变内存空间，导致最后的结果系统不认；其次，需要考虑m和n是0的情况（图2），在考虑这个情况的时候同样要考虑前者。

python可以有两个做法，偷懒就是用切片把两个list合起来，然后sort()（图1）；其次就是常规做法，在时间O(m+n)下，倒着遍历两个list，谁比较大就放到nums1的最后，收尾工作就是把最小的那些挨着放到nums1的最前面即可（图3）。

这题逆大天，一定一定要注意python的赋值，这个以前从来没考虑过。

141. 环形链表 [LinkList]

检查是不是环形链表。

必须要遵从链表思想的话是做法是快慢指针：两个指针，一个每次前进1步，一个每次前进2步，如果有环的话它们必定相遇。此时内存用的是O(1)。

常规做法就是每过一个内存地址，就存储，如果得到一个重复的，证明有环，指针遇到末尾了证明无环。此时用的内存是O(N)。检查重复自然需要用到一些数据结构比如hash和set等，实际上还是第一个方法简单。

148. Sort List [Sort/LinkList]

链表排序。

三种方法：

第一种是只对每个node的value进行冒泡排序，不动next，这样做显然会TLE。

第二种是偷鸡做法，就是把所有value取到一个list里，直接对list进行排序，这时的排序就是线性表的排序而不是链表的排序，最后把排好序的内容从链表头开始依次填进去，这样做面试估计不给过。

第三种是正常做法，就是归并排序。

对于链表而言最好的排序方法就是归并。要牢牢记住第三种方法的流程：共三个函数，主函数返回head的归并排序调用；归并排序函数就是将当前表头一分为二，并且递归的归并排左和右，最后返回的左右两部分的merge函数调用；merge函数就是设置一个新的暂时链表头和两个指针，把两个子链表，用操作指针从头遍历融合，返回的是暂时链表表头的指针next。

三种O(logn)的排序算法：快排、堆排序、归并排序。

165. 比较版本号

题目比较拗口，但是不难，中等就这？

主要用到python的split和int强制类型转换时会忽略前导0。

189. Rotate Array [array]

根据题意，就是将list中的后k个挪到前面来，就是尾出头进k次，每次一个人，之后的队列顺序。

使用切片做即可。注意循环次数超过了队列长度，意味着要回归原位一次，那么先用k对list长度取余数即可。

206. 反转链表 [LinkList]

在我看来还是递归比较舒服一点：从头开始循环，两个指针分别是头p和头的下一个p_next，如果p_next的下一个，也就是p_next->next不为空，就递归传入p_next和p_next->next，p_next->next为空就证明循环到了最后俩，此时p_next->next指向p，也就是反转操作，p的下一个也就是p->next指空，也就是改递归边界。

不递归纯循环的话就从头设立两个指针p和p_next，初始化为head和head->next，然后翻转，反转之后根据p_next的定位，挪p，然后p_next向下指。

两种方法从操作顺序上来说，递归是从尾部开始反转，迭代就是从头部开始循环。

非常规方法就是设其他空间去记录一部分信息，比如将值信息按顺序取下来，反着再装到这个表里；再或者用栈记录从头到尾的位置信息，然后每次反转栈头的两个。

215. 数组中的第K个最大元素 [quick sort]

主要是快排的代码，背下来。

283. Move Zeroes [array]

将数组内的所有0挪到最后。

从头开始遍历，设置一个flag=0，非0的就放到flag位置，flag++，也统计了非0的个数，最后把从第flag位置到最后设置成0即可，注意list长度是0或者list内没有要操作的数这两个问题。

458. 可怜的小猪 [技巧题/num]

比传统的那个用2进制做的题多了一个测试次数。使用测试次数可以扩展维度，即从2进制（测试次数=1，2=1+1）变为测试次数+1进制。

可以以一个小时时长为例，每次15min，那么对于每个猪，就能测试4次。

当只有猪1时，测试4次就意味着猪1能断言一共5桶水的情况：如果前4次没死，有毒的就是第5桶，如果前4次死了的话那就是死了那次的那一桶。

两只猪的话，把25个桶排列成5*5，猪1每次喝列5桶，猪2每次喝行5桶，交叉死的就是有毒的；

三只猪的话，把125个桶排列成5*5*5，猪1每次喝x面的25桶，猪2每次喝y面的25桶，猪3每次喝z面的25桶；

四只猪的话，排5组的5*5*5，猪1每次喝这5组的x面共5*25=125桶，猪2、3同理，猪4每次喝一组的5*5*5共125桶；

五只猪的话，排列5*5=25组的5*5*5，猪4每次喝一列的555，猪5每次喝1行的555…

注意上述过程中的乘法，有助于理解，因为我们只有3维，猪喝水喝到4维之后就是3维又3维的叠加。

---

都是python和cpp

• python可以函数里面写函数；
• python max和min、count能用，list的许多操作可用，主要是append和extend；
• cpp中vector常用的函数：size()，可按数组循环；insert(locat,num,value)指定位置插入指定个数的指定元素；
• python的list切片，记住[:a]和[a:]的区别；
• 一些要求在原list上修改，不返回值的题，python操作数据赋值一定要用切片，不然会改变内存位置，导致过不去；
• 【56】python如果想写变循环上限的循环，一定不要用for，不管用：就是说用i当循环变量写for，如果在for内部修改了这个i，对于循环来说i的值是没有变动的，这一点非常重要，和c语言的循环是不一样的，如果想写，可采用外设循环i，然后用while当循环，在while内部修改i的值，这样才行；
• python str用切片反转：a -> a[::-1]（两个冒号）；
• 负数取余数和正数不一样；
• cpp链表，新设节点最好用ListNode *temp = new ListNode(val,next)，两个参数建议为-1和nullptr，用的时候直接用 -> 取元素即可；
• python str replace的话，一定记得用变量去接一下结果，直接调用不接的话，原本的str是不会变的，会导致误判，觉得replace没生效或者写错了啥的；
• python 用0初始化mn二维数组：arr=[[0]*m for _ in range(n)]；不能用arr=[[0]\m]*n，这样做修改某一行的某个位置会导致所有行的该位置做同样修改，意思就是把第一行的内存存了n遍；