题目列表
- 寻找两个正序数组的中位数 5. 最长回文子串 15. 三数之和
4. 寻找两个正序数组的中位数
这个题被标记为困难主要是因为需要实现$O(log(m+n))$的解法，我最开始想到的是$O(log(m+n))$的解法，就是利用双指针，不过不是最优解，更适合合并正序数组，最优解法是看了官方的题解才会的，官方的题解解释的比较好一些。
双指针
双指针法的思路很简单，因为是两个正序数组嘛，所以知道两个数组长度，中位数在第几小的位置一定能看的出来。就开始利用两个指针，每次比较两个数组指针位置元素的大小，谁小就指针向前移动并计数，把元素加入列表中。当进行到$\frac{len(nums1) + len(nums2)}{2} + 1$的位置时，这时对于总长为奇数的数组来说，列表的最后一个元素就是中位数，取出即可。对于总长为偶数的数组来说，列表的最后一个元素和倒数第二个元素就是中位数，全部取出求均值即可。因为遍历一半两个数组，因此时间复杂度是$O(m + n)$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
if len(nums1) + len(nums2) == 1:
if len(nums1) == 1:
return nums1[0]
else:
return nums2[0]
list = []
flag = False
i = 0
p_nums1 = 0
p_nums2 = 0
tar_num = (len(nums1) + len(nums2)) // 2 + 1
if (len(nums1) + len(nums2)) % 2 == 0:
flag = True
while i < tar_num:
if p_nums1 == len(nums1):
list.append(nums2[p_nums2])
i += 1
p_nums2 += 1
continue
if p_nums2 == len(nums2):
list.append(nums1[p_nums1])
i += 1
p_nums1 += 1
continue
if nums1[p_nums1] < nums2[p_nums2]:
list.append(nums1[p_nums1])
i += 1
p_nums1 += 1
else:
list.append(nums2[p_nums2])
i += 1
p_nums2 += 1
if flag:
return (list.pop(-1) + list.pop(-1)) / 2
else:
return list.pop(-1)
二分查找
官方写法已经非常详细了，我也是照着官方的思路写的，这里贴一下官方的链接LeetCode。大概的思路就是转换成寻找第k小的数。如果我们要找的元素是k的话，取两个数组的$\frac{k}{2} - 1$处比较大小。对于较小值，最多有$k-2$个元素比它小，因此对于这个元素和它数组内比它小的元素，肯定不会是第k小的值，可以直接舍弃掉，然后k也要减去相应舍去的值，如此循环直到$k=1$时停止。这里有三种特殊情况，第一就是$k=1$时，我们这时候只需要排除一个值就可以了，也就是说要得到两个指针处的较小值。第二种是如果$\frac{k}{2} - 1$处对于数组越界了，我们要取这个数组最后一个值并且$k$值减小时也要根据具体的数量进行判断。第三种就是如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第$k$小的元素。时间复杂度：$O(\log(m+n))$
1 | class Solution(object): |
5. 最长回文子串
这道题是动规类型的，不是特别熟悉，因此看了题解，有两种解法，动态规划和中心扩散法
动态规划
对于动规问题来说，最重要的是找到状态转移方程。对于一个回文串来说，去掉两头的字母的子串也还是回文串。用$s(i,j)$ 表示字符串$s$的第$i$到$j$个字母组成的串，所以状态转移方程可以为
当然还要考虑边界的问题，对于长度为1的字符串显然是回文串，长度为2的则需要相同字符才可以。最后，一定要从字符串长度小的向长度大的转移。
1 | class Solution(object): |
中心扩散法
15. 三数之和
起初，拿到这道题时，想到了两数之和中的哈希表解法，但是尝试了之后发现不太可行，因为利用字典建立哈希表会要求key值不是可变变量，因此list不能作为键值来去重，最后还是参考了题解中的排序加双指针的做法
排序+双指针
首先，我们先用时间复杂度为$O(N^3)$的三重循环来考虑问题。由于题目中要求时不允许有重复项，如果直接使用三重循环的话，是会产生重复项的（列表有重复元素）。因此，题解中使用了排序和跳跃的方法。我们需要保证
- 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；
- 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。
当排完续后，三元组 $(a, b, c)$ 满足 $a \leq b \leq c$ ，保证只有一种顺序会被列举到。但是如果含有重复元素，那么$(a, b, c)$这个组合可能再次遇到。这时就要使用跳跃跳到下一个不相同的元素。此时时间复杂度还是$O(N^3)$，因此还可以使用双指针的方法进一步改进。我们固定$a$的值，把代表$b, c$的指针分别指向$a$的后一位和末尾，由于数组元素是递增的，如果$a + b + c > 0$的话，继续移动b的位置是会导致和是递增的而向前移动b的指针是递减的。这时，我们移动$c$的指针直到$a + b + c \le 0$，然后我们判断当前数值是否满足$a + b + c = 0$，如果满足则计入列表中。因为此时的$a + b + c \le 0$，所以我们需要移动$b$来增加数组的值（不要忘记“跳跃”）。这时，c指针的位置不需要重新回到末尾，因为前面的对于上一个$b$满足$a + b + c > 0$的话，对于这个也肯定满足（数组递增）。因此，双指针可以把第二三重循环时间复杂度降为线性的。最后时间复杂度为$O(N\log N + N^2) = O(N^2)$。
1 | class Solution(object): |