LeetCode1-5题

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

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        d = {}
        for i, num in enumerate(nums):
            if target - num in d:
                return [d[target - num], i]
            d[num] = i

2.两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        node1 = l1
        node2 = l2
        l3 = ListNode(0)
        l3.next = ListNode(0)#[0],[0]的特殊情况
        node3 = l3
        
        sum1 = 0
        coe = 1
        while not node1 is None:
            sum1 += node1.val * coe
            coe *= 10
            node1 = node1.next
        
        sum2 = 0
        coe =1
        while not node2 is None:
            sum2 += node2.val * coe
            coe *= 10
            node2 = node2.next
        
        sum = sum1 + sum2
        
        while sum > 0:
            node3.next = ListNode(sum % 10)
            node3 = node3.next
            sum //= 10
            
        return l3.next

3.无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        start = 0
        max_length = 0
        substring = {}
        for i, c in enumerate(s):
            if c in substring and start <= substring[c]:#只有当重复值是在start后面出现时才移动start
                start = substring[c] + 1#Slding Window的思想
            else:
                max_length = max(max_length, i - start + 1)
            substring[c] = i
            
        return max_length

4.寻找两个有序数组的中位数
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums = sorted(nums1+nums2)
        if len(nums)%2 ==0:
            answer = (nums[int(len(nums)/2-1)]+nums[int(len(nums)/2)])/2
        else:
            answer = nums[int((len(nums)+1)/2)-1]
        return answer

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

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        left = right = 0
        n = len(s)
        for i in range(n - 1):
            if 2 * (n - i) + 1 < right - left + 1:
                break
            l = r = i
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            if r - l - 2 > right - left:
                left = l + 1
                right = r - 1
            l = i
            r = i + 1
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            if r - l - 2 > right - left:
                left = l + 1
                right = r - 1
        return s[left:right + 1]