leetcode官网:

官方网站

.

*

1

两数之和

.

① 题目

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

示例:

给定 nums = [2, 7, 11, 15], target = 9 
因为 nums[0] + nums[1] = 2 + 7 = 9 
所以返回 [0, 1]

② 思考

从一个列表里面查找两个有特定关系的数，也就是知道了一个数，求另一个对应数的位置，如果不存在对应的数就下一位。

1>用一般的遍历可以做，而且可以找出来全部的，简单，但是时间复杂度为O(n^2)，会超时。

2>联想到哈希表。哈希表中一个key值对应表中一个地址，且哈希表里面的数不重复，在python语言中，就类似于一个字典

dict={}

,一个key对应一个value，若key不在表中，就添加新的元素，若key在表中，可直接查询到value。在这个实例中，key就是对应的另一个数，value就是这个数的地址。

时间复杂度:

科普

.

哈希表:

哈希表

.

③ 源码

class Solution(object):    
	def twoSum(self, nums, target):
		another = {}        
		for i, n in enumerate(nums):            
			another_n = target - n            
			if another_n in another:                
				return(another[another_n], i)            
			another[n] = i        
		return None

凑巧，最近在看SECOND目标识别的源码，其中在生成体素数据时，就用到了哈希表。

2

两数相加

.

① 题目

两数相加

.粘贴出来太麻烦了

② 思考

链表还真是第一次接触，python里面原来真的没有这个东西。先了解一下什么是链表

链表定义

.

在程序中，一般都是通过一个指针访问地址，才能得到地址存放的数值。一个链表每个节点（node）上，包含两个域，第一域存放了一个数值，第二域存放了指针下一次要指向的地址，也就是说要访问一个链表的话，只能按顺序进行访问，不能打乱顺序。在c语言中，可以使用一个

typedef struct XXX

来定义，就像一个套娃，一个数套着一个数，python中也是用套娃实现的。

③ 答案

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        re = ListNode(0)                # 新建ListNode
        r = re                          # 考虑为什么要把re给到r，因为在循环过程中，r永远指向re的最后一位，re是总的
        carry = 0                       # 进位
        while l1 or l2:                 # x，y中只要有一个还有值，就一直计算
            x = l1.val if l1 else 0     # 没有值就给0
            y = l2.val if l2 else 0     # 没有值就给0
            s = carry+x+y               # 这一位的和
            carry = s//10               # 进位
            r.next = ListNode(s % 10)   # 创建一个新的ListNode，专门存放余位
            r = r.next                  # 套娃，r指向了原本r里面的一层，就是代表上一层已经处理好了，指向这一位的next了
            if l1 != None:              # l1还没结束，下一位，结束了的话就留在原地
                l1 = l1.next
            if l2 != None:              # l2还没结束。下一位，结束了的话就留在原地
                l2 = l2.next
        if carry > 0:                   # 最后一位还有进位，那就多加一位
            r.next = ListNode(1)
        return re.next                  # re的第一位是0，所以不要第一位了，只要next里的部分

在pycharm进行调试时，需要自己对

ListNode

进行定义，这里参考了

这里

.

3

无重复字符的最长子串

.

① 思考

这种题目的共性：从一整串数据里面拿出有一定规律的一个字串，都可以用滑动窗口法。

滑动窗口法：左边一个指针，右边一个指针，读取两个指针中间的数据，需要满足一定的规律，就找到了满足要求的字串。

② 源码

class Solution1:
    def lengthOfLongestSubstring(self, s):
        # 哈希集合，记录每个字符是否出现过
        occ = set()
        n = len(s)
        # 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                # 左指针向右移动一格，移除一个字符，一直右移到删掉了s[rk + 1]对应的字符，就可以开始右边界右移了
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                # 不断地移动右指针
                occ.add(s[rk + 1])
                rk += 1
            # 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1)
        return ans

class Solution2(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        st = {}     # 这个字典key是字符，value是字符截止到j最后出现的位置
        i, ans = 0, 0
        for j in range(len(s)):
            if s[j] in st:
                i = max(st[s[j]], i)
            ans = max(ans, j - i + 1)
            st[s[j]] = j + 1
        return ans;

class Solution3:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        last_pos = {}
        left_pos = -1
        ans = 0
        if len(s) == 0:
            return 0
        for i in range(len(s)):
            if s[i] in last_pos:
                left_pos = max(left_pos, last_pos[s[i]])
                last_pos[s[i]] = i
            else:
                last_pos[s[i]] = i
            ans = max(ans, i - left_pos)
        return ans

第一种方法，滑动窗口，用哈希表，一旦发现窗口里面有重复就从左指针开始检测重复的位置，然后移动左指针直到没有重复，记录长度。

第二种方法，使用了一个哈希表，或者说字典，记录了重复内容上一次出现的位置，直接左指针移到这个位置，节约了时间，但增加了内存。

第三种方法，自己写的，和第二种一样。

4

寻找两个正序数组的中位数

.

① 思考

中位数指的是一个数组从小到大排列后，在中间位置的数，既第（m+n）/2个数，同时题目要求，时间复杂度要是O(logn)，如果将两个数组合并再找中位数，时间复杂度不符合要求，存在log，应该考虑到使用二分法查找。

二分法：每次取一半直到这个一半的数为1，说明下次再取就可以取到要取的数了。如要求8个数的中位数。先取2个小的，再取1个，就取走3个了，接下来的两个数取平均，就是中位数。

② 源码

# 首先看题目要求，时间复杂度要求为log（m+n），则联想到使用二分法，使用一般遍历方法时时间复杂度为m+n
# 但是在两个数列中，二分法有变形
# 求中值点，可以方便的联想到求中间位置的数，也就是求target=（m+n）/2,或者target=（m+n）/2+1这两个位置上的数
# 开始二分，l1和l2分别拿出第k/2个数，不够的话，用min(target // 2, len(nums1))，拿出直到最后一位数，比较拿出来的数大小
# 小的那一个数列的前这么多位肯定都是属于target位置之前的，去掉，同时target也减小这么多位，因为拿出去了一部分，剩下的再拿出去的话，就要少拿这么多个
# 直到把一个数列拿空了，或者target = 1，就是下一次拿的数中的某个数了
class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        def findTargetElement(nums1, nums2, target):
            while True:
                if len(nums1) == 0:
                    return nums2[target - 1]
                if len(nums2) == 0:
                    return nums1[target - 1]
                if target == 1:
                    return min(nums2[0], nums1[0])
                pos1 = min(target // 2, len(nums1)) - 1
                pos2 = min(target // 2, len(nums2)) - 1
                if nums1[pos1] >= nums2[pos2]:
                    nums2 = nums2[pos2 + 1:]
                    target -= pos2 + 1
                else:
                    nums1 = nums1[pos1 + 1:]
                    target -= pos1 + 1

        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        len_all = len(nums1) + len(nums2)
        left = (len_all + 1) // 2
        right = (len_all + 2) // 2
        return (findTargetElement(nums1, nums2, left) + findTargetElement(nums1, nums2, right)) / 2

5

最长回文子串

.

① 思考

1>使用滑动窗口法：每个窗口判断第一个点和最后一个点是否相等，再第二个与倒数第二个，依次判断是否对称回文，时间复杂度较高

2>遍历中心点，求臂长： 以每一个点为中心点，求该点的对称臂长，返回最大臂长

3>动态规划：若最长回文子串满足要求，则该字串的每一个字串都是一个回文子串，这样就符合动态规划的思想，递推或者分治。

② 源码

# 由于回文子串是一个嵌套着一个，里面的是回文子串，外面的才哟可能，因此考虑使用动态规划
# 东该规划就是递推或者分治，使用递推或者递归都可以，

class Solution(object):
    # 递归方法，反复调用地思想，从长到短
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        import numpy as np
        n = len(s)
        dp = - np.ones((n, n))
        if n == 0:
            return ""
        if n == 1:
            return s

        def is_true(lens, pos, s, dp):
            if lens == 1:
                dp[pos, pos + lens - 1] = 1
            if lens == 2:
                if s[pos] == s[pos + lens - 1]:
                    dp[pos, pos + lens - 1] = 1
            if lens > 2:
                if (is_true(lens -2, pos + 1, s, dp) == 1 and s[pos] == s[pos + lens - 1]):
                    dp[pos, pos + lens - 1] = 1
            return dp[pos, pos + lens - 1]

        for lens in range(n, 0, -1):
            for pos in range(n - lens + 1):
                if is_true(lens, pos, s, dp) == 1:
                    return s[pos:pos + lens]

        # # 递推方法，从短到长，遍历全部
        # print(dp)
        # for lens in range (n, 0, -1):
        #     for pos in range(n - lens + 1):
        #         if dp[pos, pos+lens-1] == 1:
        #             return s[pos:pos+lens]

    # def longestPalindrome(self, s: str) -> str:
    #     n = len(s)
    #     dp = [[False] * n for _ in range(n)]
    #     ans = ""
    #     # 枚举子串的长度 l+1
    #     for l in range(n):
    #         # 枚举子串的起始位置 i，这样可以通过 j=i+l 得到子串的结束位置
    #         for i in range(n):
    #             j = i + l
    #             if j >= len(s):
    #                 break
    #             if l == 0:
    #                 dp[i][j] = True
    #             elif l == 1:
    #                 dp[i][j] = (s[i] == s[j])
    #             else:
    #                 dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])
    #             if dp[i][j] and l + 1 > len(ans):
    #                 ans = s[i:j+1]
    #     return ans

实验结果发现：递归的时间比递推的时间要长，但是两者都是可行的，leetcode上递归会超时。

参考：以上的题目均来自于leetcode官网

官网

.