LeetCode 1-5

1.两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= $10^4$
• -$10^9$ <= nums[i] <= -$10^9$
• –$10^9$ <= target <= -$10^9$
• 只会存在一个有效答案

 
 class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
1
2
3
4
5
6
7
8

方法一：暴力枚举

算法思路：
枚举数组中的每一个数 x，寻找数组中是否存在 target - x。
注意：每一个位于x之前的元素都已经和x匹配过。

 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 []
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 时间复杂度：$O(N^2)$，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
• 空间复杂度：$O(1)$

方法二：哈希表

算法思路：

创建一个哈希表，对于每一个x，我们首先查询哈希表中是否存在target - x，然后将x插入到哈希表中，即可保证不会让 x 和自己匹配。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: 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 []
1
2
3
4
5
6
7
8
9
10
11
12
13

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

2.两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

方法一：模拟

算法思路：

由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。

我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2，进位值为 carry 则它们的和为 n1+n2+carry 其中，答案链表处相应位置的数字为 (n1+n2+carry) mod 10 而新的进位值为
​$\lfloor \frac{n1+n2+carry}{10}\rfloor$.

如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0 。

此外，如果链表遍历结束后，有 carry>0，还需要在答案链表的后面附加一个节点，节点的值为 carry。

# 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
        """
        head = ListNode()
        current = head
        carry = 0

        while l1 or l2 or carry:
            # 获取当前节点的值，如果节点为空则默认为0
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0

            # 计算当前位的和，考虑进位
            current_sum = x + y + carry
            carry = current_sum // 10   # 计算进位
            current_digit = current_sum % 10 # 当前位的值 

            # 创建新节点并将其连接到链表
            current.next = ListNode(current_digit)
            current = current.next

            # 移动到下一位
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
    
        return head.next
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

• 时间复杂度 $(max(m,n))$，其中m和n分别为两个链表的长度。
• 空间复杂度：$O(1)$。（注意返回值不计入空间复杂度）

3.无重复字符的最长字串

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

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

请注意，你的答案必须是子串的长度，“pwke” 是一个子序列，不是子串。

提示：

• 0 <= s.length <= $5\ast 10^4$
• s 由英文字母、数字、符号和空格组成

算法思路：
假设我们选择字符串中的第k个字符作为起始位置，并且得到了不包含重复字符的最长字串的结束位置为$r_k$。那么当我们选择第 k + 1 个字符作为起始位置时，首先从 k + 1到 $r_k$的字符显然是不重复的，并且由于少了原本的第k个字符，我们可以尝试继续增大$r_k$，直到右侧出现了重复字符为止。

我们使用滑动窗口来解决这个问题。

我们使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着上文中枚举子串的起始位置，而右指针即为上文中的$r_k$。

在每一步的操作中，我们会将左指针向右移动一格，表示我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；

在枚举结束后，我们找到的最长的子串的长度即为答案。

使用 python 中的 set 来判断是否有重复字符。在左指针向右移动的时候，我们从哈希集合中移除一个字符，在右指针向右移动的时候，我们往哈希集合中添加一个字符。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        charIndex = {} # 存储字符及其最后出现的位置
        left = 0 
        max_length = 0

        for i in range(len(s)):
            if s[i] in charIndex and charIndex[s[i]] >= left:
                left = charIndex[s[i]] + 1 # 更新窗口的起始位置
            charIndex[s[i]] = i # 更新字符的最后出现位置
            current_length = i - left + 1 # 计算当前窗口的长度
            max_length = max(max_length, current_length)

        return max_length
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 $O(log(m+n))$ 。

示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• $-10^6$ <= nums1[i], nums2[i] <= $10^6$

方法一：二分查找

算法思路：

设现有两个正序数组，A[0,..., m-1]和B[0,...,n-1]。
当 m+n 是奇数时，中位数为两个有序数组中的第(m+n+1)/2个元素
当 m+n 是偶数时，中位数为第(m+n)/2个元素和第(m+n)/2 + 1个元素的平均值。
这道题可以转化成寻找两个有序数组中的第 k 小的数，其中k为(m+n)/2 或 (m+n)/2 + 1。

为寻找第k个元素，比较A[k/2 - 1]和B[k/2 - 1]。
对于两者中的较小值，最多只会有k-2个元素比它小，故它不可能是第 k 小的数。

比较后有三种情况：

1. 如果A[k/2-1] < B[k/2-1]，则排除A[0]到A[k/2-1]。
2. 如果A[k/2-1] > B[k/2-1]，则排除B[0]到B[k/2-1]。
3. 如果两者相等，则归入第一种处理。

需要特殊处理的情况有三种：

1. 如果A[k/2-1]或者B[k/2-1]越界，那么我们可以选取对应数组中的最后一个元素。在这种情况下，我们必须根据排除数的个数减少k的值，而不能直接将k减去k/2。
2. 如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第k小的元素。
3. 如果k=1，我们只要返回两个数组首元素的最小值即可。

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        def getKthElement(k):
            """
            - 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
            - 这里的 "/" 表示整除
            - nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
            - nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
            - 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
            - 这样 pivot 本身最大也只能是第 k-1 小的元素
            - 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
            - 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
            - 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
 

       """
        
        index1, index2 = 0, 0
        while True:
            # 特殊情况
            if index1 == m:
                return nums2[index2 + k - 1]
            if index2 == n:
                return nums1[index1 + k - 1]
            if k == 1:
                return min(nums1[index1], nums2[index2])

            # 正常情况
            newIndex1 = min(index1 + k // 2 - 1, m - 1)
            newIndex2 = min(index2 + k // 2 - 1, n - 1)
            pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]
            if pivot1 <= pivot2:
                k -= newIndex1 - index1 + 1
                index1 = newIndex1 + 1
            else:
                k -= newIndex2 - index2 + 1
                index2 = newIndex2 + 1
    
    m, n = len(nums1), len(nums2)
    totalLength = m + n
    if totalLength % 2 == 1:
        return getKthElement((totalLength + 1) // 2)
    else:
        return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2.0
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
44
45
46
47
48
49

• 时间复杂度：$O(log(m+n))$，其中 m 和 n 分别是数组 $num{s}_1$ 和 $nu{m}_2$的长度。初始时有 k = (m + n) / 2 或 k = (m + n) / 2 + 1，每一轮循环可以将查找范围减少一半，因此时间复杂度为$O(log(m+n))$。
• 空间复杂度：$O(1)$

方法二：划分数组

算法思路：

首先，在任意位置 i 将 A 划分成两个部分：
left_A : A[0], A[1], …, A[i - 1]
right_A : A[i], A[i + 1], …, A[m - 1]
采用同样的方式，在任意位置 j 将 B 划分成两个部分：
left_B : B[0], B[1], …,B[j - 1]
right_B : B[j], B[j + 1], …, B[n - 1]

将left_A 和 left_B 放入一个集合， right_A 和 right_B 放入一个集合，再把这两个新的集合分别命名为：left_part 和 right_part。

当 A 和 B 的总长度是偶数时候，如果可以确认：

1. len(left_part) = len(right_part)
2. max(left_part) $\le$ min(right_part)
   则 $median=\frac{max(left\_part)+min(right\_part)}{2}$

当 A 和 B 的总长度是奇数的时候，如果可以确认：

1. len(left_part) = len(right_part) + 1
2. max(left_part) $\le$ min(right_part)
   则 $median=max(left\_part)$

第一个条件对于总长度是偶数和奇数的情况有所不同，但是可以将两种情况合并。
第二个条件对于总长度是偶数和奇数的情况是一样的。

要确保这两个条件，需要：

1. i + j = m - i + n - j (当 m + n 为偶数) 或 i + j = m - i + n - j + 1 (当 m + n 为奇数)。
   即： i + j = $\frac{m+n+1}{2}$ (这里的分数结果只保留整数部分。)
2. 如果我们规定 m $\le$ n， 则对于任意的 i ∈ [0, m], 都有 j = $\frac{m+n+1}{2}$ - i ∈[0, n]。 （如果实际上 A 的长度较大，只需要交换 A 和 B 即可。）
3. 在[0, m]中找到最大的 i，使得：A[i - 1] $\le$ B[j]，其中 j = $\frac{m+n+1}{2}$ - i
   找到满足3的 i，即找到B[j−1]≤A[i] 以及 A[i−1]≤B[j]

为了简化分析，假设 A[i−1],B[j−1],A[i],B[j]总是存在。对于 i=0、i=m、j=0、j=n 这样的临界条件，我们只需要规定 A[−1]=B[−1]=−∞，A[m]=B[n]=∞ 即可。
这也是比较直观的：当一个数组不出现在前一部分时，对应的值为负无穷，就不会对前一部分的最大值产生影响；当一个数组不出现在后一部分时，对应的值为正无穷，就不会对后一部分的最小值产生影响。

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        m, n = len(nums1), len(nums2)
        low, high = 0, m

        while low <= high:
            i = (low + high) // 2
            j = (m + n + 1) // 2 - i

            maxX = float('-inf') if i == 0 else nums1[i - 1]
            minX = float('inf') if i == m else nums1[i]

            maxY = float('-inf') if j == 0 else nums2[j - 1]
            minY = float('inf') if j == n else nums2[j]

            if maxX <= minY and maxY <= minX:
                if (m + n) % 2 == 0:
                    return (max(maxX, maxY) + min(minX, minY)) / 2.0
                else:
                    return max(maxX, maxY)
            elif maxX > minY:
                high = i - 1
            else:
                low = i + 1
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

5.最长回文子串

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

示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：“bb”

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

方法一：动态规划

算法思路：

字串长度大于2：当 s[i + 1 : j - 1] 是回文串， 并且 s 的第 i 和 j 个字母相同时，s[i : j]才会是回文串。

当子串长度为1 ：显然是一个回文串
当子串长度为2 ：只要它的两个字母相同，它就是一个回文串

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        if n == 1:
            return s
        
        max_len = 1
        begin = 0

        #dp[i][j]表示s[i..j]是否是回文串
        # 外部的 for _ in range(n) 表示对每一行进行迭代，
        # 内部的 [False] * n 表示在每一行中创建长度为 n 的一维列表，并将其初始化为全是 False 的布尔值。
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        
        # 递推开始
        for L in range(2, n):
            for i in range(n):
                # 由L和i可以确定右边界
                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]
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

• 时间复杂度： $O(n^2)$，其中 n 是字符串的长度。
• 空间复杂度： $O(n^2)$

方法二：中心扩展算法

算法思路：
改进算法一，在从P(i + 1, j - 1)扩展到P(i, j)的过程中，如果两边的字母不同，我们就可以停止扩展了。

class Solution(object):
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return  left + 1, right -1
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)
            left2, right2 = self.expandAroundCenter(s, i, i + 1)
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        
        return s[start: end + 1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 时间复杂度：$O(n^2)$，其中 n 是字符串的长度。长度为 1 和 2 的回文中心分别有 n 和 n - 1个， 每个回文中心最多会向外扩展 $O(n)$次。
• 空间复杂度：$O(1)$。

方法3：Manacher算法

太难了，没看懂。

算法思路：

此处定义一个新概念：臂长，其表示中心扩展算法向外扩展的长度。
如果一个位置的最大回文字符串长度为 2 * length + 1， 其臂长为 length。

下面只讨论长度为奇数的回文字符串。（长度为偶数的回文字符串会在最后与长度为奇数的情况统一。）

我们可以通过一个特别的操作将奇偶数的情况统一起来：我们向字符串的头尾以及每两个字符中间添加一个特殊字符 #，我们就不需要再考虑长度为偶数的回文字符串了。

当在位置 i 开始进行中心拓展时，我们可以先找到 i 关于 j 的对称点 2 * j - i。那么如果点 2 * j - i 的臂长等于 n，我们就可以知道，点 i 的臂长至少为 min(j + length - i, n)。那么我们就可以直接跳过 i 到 i + min(j + length - i, n) 这部分，从 i + min(j + length - i, n) + 1 开始拓展。

class Solution(object):
   def longestPalindrome(self, s):
       """
       :type s: str
       :rtype: str
       """

       # 预处理的目的是在原字符串的每个字符之间插入一个特殊字符#
       # 这样做的目的是为了使字符串变为奇数长度，用以解决奇偶回文串长度的问题
       def preprocess(s):
           result = ['#']
           for char in s:
               result.extend([char, '#'])
           return ''.join(result)
       
       T = preprocess(s)
       n = len(T)
       P = [0] * n  # 辅助数组，用于存储每个位置上回文串的半径长度
       C, R = 0, 0  # C是初始化中心，R是最右边界

       for i in range(n):
           mirr = 2 * C - i

           if i < R:
               P[i] = min(R - i, P[mirr])

           a, b = i + (1 + P[i]), i - (1 + P[i])
           while a < n and b >= 0 and T[a] == T[b]:
               P[i] += 1
               a += 1
               b -= 1

           if i + P[i] > R:
               C, R = i, i + P[i]
           
       max_len, center_index = max((n, i) for i, n in enumerate(P))
       start = (center_index - max_len) // 2
       end = start + max_len - 1

       return s[start:end + 1]
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

• 时间复杂度：$o(n)$, 其中n为字符串的长度。
• 空间复杂度：$o(n)$