七天LeetCode刷题总结

引言

从今天起，为期7天LeetCode刷题记录。

2019/1/26：两数之和

问题说明

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

完整代码

那么我们就可以给出我们的解答，直接暴力：

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if target < 2:
        	return None
        for i in range(0,len(nums)-1):
            for j in range(i+1,len(nums)):
                if nums[i] + nums[j] == target:  
                    return i,j

最后得出来的结果是10264 ms，好吧，双重for循环挺容易想的，但复杂度也高。然后我马上就想到了第二种：

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums:
           return None 
        i = 0
        while i < len(nums):
            j = i + 1
            difference = target - nums[i]

            while j < len(nums):
                if nums[j] == difference:
                    return i, j
                j += 1
            i += 1

结果是9564 ms。。。只比第一种好那么一点点，但我觉得比第一种考虑的东西多了很多，另外复杂度我本来想着是能降两个千的。可惜，好像还是暴力了，感觉太年轻。。。然后去看了下大佬的代码，发现要用字典做：

class Solution:
   def twoSum(self, nums, target):

       if not nums:
           return None
       
       d = dict()
       for i, item in enumerate(nums):
           tmp = target - item
           if tmp in d:
               return [i, d[tmp]]
           d[item] = i
       
       return None

总结

总结：这次时间上来讲，有点急，家里有些事，晚上才开始刷，白天在弄美赛和另一篇博文，所以导致两种方法间隔半小时，接下来要好好规划一下时间了。

2019/1/28：寻找两个有序数组的中位数

问题说明

很抱歉的是，2019/1/27号并没有刷题，由于家里有一些饭局以及美赛已经到了比较刺激的时候，虽然最后还是划了一天的水，但我竟然用2016年小区模拟的MATLAB自动机代码去模拟了一条龙的生长，至于生长公式，那不就跟造火箭是一个性质的嘛。。。最后结果跑是跑出来的，但完全不知道是个啥，守恒是不可能了，爱因斯坦也阻止不了龙族崛起。

最后写了个段子，参考知乎热榜2019年美赛是种什么体验：吸了一天的毒，又养了一天的龙，发现龙变成了喷火龙，并飞向了巴黎，所以，我想带你去浪漫的卢浮宫看一场恐怖袭击，顺便运用无人机进行空中救灾演习，虽然我仅仅只有虚拟货币，但还是想维持生态稳定性。

言归正传，其实这次美赛我没有参加，只是有种遗憾和情怀想再去玩一下而已，中途效率起伏不定，家里事也比较多，基本也算半玩半做吧，但目前已经没思路了，准备撤了，另外补齐一下昨天的刷题吧：

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

这题可以写下分析，首先看到题目后面的难度为困难，说实话确实有点怕，代码水平不高，除了蓝桥杯还没做过困难的题，但没办法，眼看着又到交稿日期了，只能开干了，关于时间复杂度O(log(m + n))，不懂，没有学过数据结构，之前在一篇博文里总结过栈、队列和链表，我又回头看了一下，嗯，没啥用处。但时间复杂度是啥，没有太多概念，不过我好像在pythontop中刷过字符串转中位数的题，那么本题就有第一种解法了：

我希望将数组合并之后转换成字符串的格式，那么我就可以用之前的某道相似题做，这里大概就是用extend或者append合并，然后join得到结果，那么接下来就是字符串排序的问题了。但有一个问题就是，给的两个数组里的数据是整数，而不是字符串，后来我写程序写到一半，发现一直报错：TypeError: sequence item 0: expected str instance, int found，然后我搜狗了一下，发现join的seq参数需要要连接的元素序列、字符串、元组、字典。。。好吧，那里面还要转换，虽然可能可以转，用一些高级函数比如map，但不用想都知道时间复杂度已经超了，所以宣布暂停。

通过上面的一番调试，打消了我转换类型的想法，还是要规规矩矩的用列表进行得好，但我又发现（仔细看了遍题）这是两个有序列表，我突然想到了归并排序，这不就是归并的后两步嘛？让我们回想一下归并的步骤：
● 把长度为n的输入序列分成两个长度为n/2的子序列；
● 对这两个子序列分别采用归并排序；
● 将两个排序好的子序列合并成一个最终的排序序列。

这里就相当于归并算法，然后我顺便做了一个可视化：

所以，我直接以列表来排序不就行了？但我虽然感觉上是归并，但最后没有用归并。

没错，python里面还有更好的方式和归并等同，用一个内置函数，它里面的逻辑其实是用快排做的，那就是sort。如果忘了的朋友，可以看下我下面的这篇博文，不过这篇博文里我好像没提到这一点：
python内置函数总结与思维导图

完整代码

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums1.extend(nums2)  # 合并
        add = nums1
        if not add:
            return None
        add.sort()  # 改变原来的列表
        if len(add) % 2:   # 计数不是循环。
            return add[len(add)//2] / 1.0
        else:
            return (add[len(add)//2] + add[(len(add)//2)-1]) / 2.0

总结

总结：这个代码总共提交了3次，每次结果都不一样，最好在112ms，这也是排序的特性。另外需要注意sort和sorted的区别，如果是sorted需要赋给新的变量。然后我提交完后去查了下快排的时间复杂度，发现是O(nlogn)，那么本题就应该是O((n+m)log(n+m))了，好像和题意有些出入？。。不太清楚，官方题解没有看懂，但感觉递归法应该可行，不过我暂时没想了，有些朋友一年没见了，今天天气也还好，要去碰个面，晚上回来可能继续造龙？。。。感觉有点悬，还是吸个毒造个火箭吧。（手动笑脸）

2019/1/29：最长回文子串

问题说明

嗯，要开始认真刷题了，最近一些事情算忙完了，接下来又是新的开始。那么话不多说，开始今天的题。

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

题目意思相比于上题来讲，算很清楚了，但清楚的题目往往都不是很好做。然后鉴于现在时间还算充裕，我不知道这题对于暴力求解会不会超时，但暂时没想用了，有时候一味暴力容易陷入死局，大概看了一下官方题解，这个也比上题清晰，甚至有点太过笼统。。从动态规划到中心扩展算法，最后是Manacher，嗯，不懂。然后今天主要研究了一下动态规划。下面为分析：

最大公共子序列介绍与求解

可能本题我有点跑偏，因为之前确实没怎么看过动态规划这方面的东西，但无关大雅，作为动态规划里最经典的案例之一，最大公共子序列（Longest Common Subsequence，简称LCS），是从两个公共的序列中提取相同的子序列，子序列是指从原序列中任意去掉若干元素（不一定连续）的序列，本题因为是字符串，那么我们两段序列也为字符串，举个例子： $为"abccade"，为"dgcadde"，那么它们的最长公共子串即为"cad"。$

对于上面这个例子，可能我们想到的最简单的方法是采用蛮力法，假设字符串 $与的长度分别为和（假设 >= ）。那么可以先找出的所有可能子串，然后判断这些子串是否也是的子串，但效率非常低下，原因是比较次数过多，那么动态规划就是一种能通过减少比较次数从而降低时间复杂度的方法。$

那么，什么是动态规划？动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度，因此它比回溯法、暴力法等要快许多。

根据上面的意思，如果要运用动态规划来解决这个问题，首先我们要构造递归关系。假设 $为序列和的LCS长度，那么我们是否可以用更小的实例来求解呢？我们可以减少序列的长度，可能的子问题是$

$时，此时两个元素匹配，得到最优解。假如想让与匹配之前的元素，那么就需要保证下一次的匹配结果不能差于本次结果，所以最优情况是让两者匹配，那么就依赖于$

由此，我们可以根据上面的式子得到 $所有的值，进而找出最长的子串，另外关于上面我举的为"abccade"、为"dgcadde"的例子，我们可以画出动态规划的计算结果，为：可能有点小丑，但无伤大雅。通过上图所示，max为最长公共子串的长度，以及maxIndex为最长子串结尾字符在字符数组中的位置，由这两个值就可以确定最长公共子串为"cad"，实现代码参考python算法面试宝典，如下：$

"""
方法功能：获取两个字符串的最长公共字串
输入参数：str1和str2为指向字符的引用（指针）
"""
def getMaxSubStr(str1,str2):
    len1 = len(str1)
    len2 = len(str2)
    SJ = ''
    maxs = 0 # 用来记录最长公共子串的长度
    maxI = 0 # 用来记录最长公共字串最后一个字符的位置
    """申请新的空间来记录公共字符长度信息"""
    M = [[0 for i in range(len1 + 1)] for j in range(len2 + 1)]
    """利用递归公式构建二维数组"""
    i = 0
    while i < len1 + 1:
        M[i][0] = 0
        i += 1
    j = 0
    while j < len2 + 1:
        M[0][j] = 0
        j += 1
    i = 1
    """动态规划推导"""
    while i < len1 + 1:
        j = 1
        while j < len2 + 1:
            if list(str1)[i-1] == list(str2)[j-1]:
                M[i][j] = M[i-1][j-1] + 1
                if M[i][j] > maxs:
                    maxs = M[i][j]
                    maxI = i
            else:
                M[i][j] = 0
            j += 1
        i += 1
    """找出公共子串"""
    i = maxI - maxs
    while i < maxI:
        SJ = SJ + list(str1)[i]
        i += 1
    return SJ

问题分析

参照上面的理解，那么我可以将 $变为的逆序，图解为：意思是一样的，然后我改完代码之后在本地跑是可以实现的，除了时间长点以外，但我带入LeetCode提交后它显示一些莫名的报错信息，输入babad，我的代码输出结果为a？如果是爆内存还说得过去，但这判定好像有问题吧。。本地为bab，一切正常，我。。无话可说咯$