记录

这里用来记录自己在LeeCode上学习编程技能的经历，希望自己可以坚持每天至少做一道题吧！

Day 1：两数之和

问题描述：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

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

        return []

现在还只会用双循环，哈希表还有待学习… 不过官方的哈希表做法也放上来吧：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

Day 2: 两数相加

问题描述：

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        temp = l1.val + l2.val
        add_next = temp // 10
        result = ListNode(temp % 10, None)
        l1 = l1.next
        l2 = l2.next

        while(l1 != None and l2 != None):
            temp = l1.val + l2.val + add_next
            add_next = temp // 10
            result = ListNode(temp % 10, result)
            l1 = l1.next
            l2 = l2.next
        
        while(l1 != None):
            temp = l1.val + add_next
            add_next = temp // 10
            result = ListNode(temp % 10, result)
            l1 = l1.next
        
        while(l2 != None):
            temp = l2.val + add_next
            add_next = temp // 10
            result = ListNode(temp % 10, result)
            l2 = l2.next
        
        if (add_next > 0):
            result = ListNode(add_next, result)


        if (result != None and result.next != None):
            tail = None
            while(result.next != None):
                second = result.next
                result.next = tail
                tail = result
                result = second
            result.next = tail
        return result

首先计算两个链表头节点的值的和，并将进位（如果有）存储在 add_next 中。然后创建一个新节点 result 来存储结果链表的头节点，并移动 l1 和 l2 到它们的下一个节点。

接下来，使用循环遍历链表 l1 和 l2，同时处理进位情况，直到其中一个链表遍历完。

在循环中，计算当前节点的值以及进位的和，并将结果添加到结果链表 result 中，同时更新进位 add_next，并将 l1 和 l2 移动到它们的下一个节点。

如果其中一个链表还有剩余节点，继续处理剩余节点，并更新结果链表。

如果还有进位，则将进位添加到结果链表的末尾。

最后，为了返回正确的结果链表，需要将结果链表逆转。

Day 3: 无重复字符的最长子串

题目描述：

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

class Solution:
    def lengthOfLongestSubstring(self, s):
        if not s:return 0
        left = 0
        lookup = set()
        n = len(s)
        max_len = 0
        cur_len = 0
        for i in range(n):
            cur_len += 1
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:max_len = cur_len
            lookup.add(s[i])
        return max_len

使用的方法是滑动窗口：在内部while循环中，如果当前遍历到的字符s[i]已经在lookup集合中存在（即已经出现过），则需要将窗口左边界右移，直到删除掉重复的字符，确保窗口内没有重复字符为止。在这个过程中，每次左移一个字符，都会更新cur_len以及相应地从lookup中移除左边界字符。

其中使用了集合这一数据类型，在Python中，集合（Set）是一种无序且不重复的数据结构，其中的元素互不相同，可以用于去除列表、元组等数据结构中的重复元素，也可以用来高效地进行成员关系测试，即判断一个元素是否在集合中，另外由于set内部采用哈希表实现，因此在set内查找指定元素的时间复杂度只有O(1)。

Day 4: 合并数组的中位数

题目描述：

给定两个大小分别为m和n的正序（从小到大）数组nums_1和 nums_2。请你找出并返回这两个正序数组的中位数。
算法的时间复杂度应该为 O(log(m+n)) 。

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        nums1.extend(nums2)
        list = sorted(nums1)
        if len(list)%2 == 0:
            res = (list[int(len(list)/2-1)]+list[int(len(list)/2)])/2
        else:
            res = list[int((len(list)-1)/2)]
        return float(res)

直接用了标准的排序函数sort，先合并再排序，最后找到中位数。

Day 5: 最长回文字串

题目描述：

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
给一个字符串s，找到s中最长的回文子串。

class Solution:
    def longestPalindrome(self, s):
        n = len(s)
        if n < 2:
            return s
        
        max_len = 1
        begin = 0
        # dp[i][j] 表示 s[i..j] 是否是回文串
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        
        # 递推开始
        # 先枚举子串长度
        for L in range(2, n + 1):
            # 枚举左边界，左边界的上限设置可以宽松一些
            for i in range(n):
                # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                j = L + i - 1
                # 如果右边界越界，就可以退出当前循环
                if j >= n:
                    break
                    
                if s[i] != s[j]:
                    dp[i][j] = False 
                else:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                
                # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i
        return s[begin:begin + max_len]

使用的方法是动态规划。
注意到对于一个子串而言，如果它是回文串，并且长度大于2，那么将它首尾的两个字母去除之后，它仍然是个回文串。
根据这样的思路，可以用动态规划的方法解决本题。我们用表示字符串s的第i到j个字母组成的串（下文表示成）是否为回文串：

$如果子串是回文串其它情况$

这里的「其它情况」包含两种可能性：

本身不是一个回文串；
，此时本身不合法。

接下来可以写出动态规划的状态转移方程：

也就是说，只有是回文串，并且 s 的第 i 和 j 个字母相同时，才会是回文串。

上文的所有讨论是建立在子串长度大于 2 的前提之上的，我们还需要考虑动态规划中的边界条件，即子串的长度为 1 或 2。对于长度为 1 的子串，它显然是个回文串；对于长度为 2 的子串，只要它的两个字母相同，它就是一个回文串。因此我们就可以写出动态规划的边界条件：

根据这个思路，我们就可以完成动态规划了，最终的答案即为所有中（即子串长度）的最大值。注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此要注意动态规划的循环顺序。

ALL YOU NEED IS LOVE

LeeCode刷题记录

记录

Day 1：两数之和

Day 2: 两数相加

Day 3: 无重复字符的最长子串

Day 4: 合并数组的中位数

Day 5: 最长回文字串