Leetcode精选50题

Leetcode精选50题

Leetcode精选50题-Day01

• 002 两数相加
• • • 思路&代码
    • 复杂度分析
• 004 寻找两个正序数组的中位数
• • • 思路&代码
    • 复杂度分析
• 005 最长回文子串
• • • 思路&代码
    • 复杂度分析

好菜，无从下手
第一场下来感觉学到的还挺多的，编程不仅仅是对编程语言的使用，也包含了数据结构的设计巧妙地减少复杂度，还有智力的比拼。。比如一些很妙的解法。
总而言之就是多做，多练，多见识

002 两数相加

题目地址：两数相加

思路&代码

参考几位大佬的解题思路：官方题解；画手大鹏

由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。
我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。

具体而言，如果当前两个链表处相应位置的数字为 n 1 , n 2 n1,n2 n1,n2，进位值为 c a r r y carry carry，则它们的和为 n 1 + n 2 + c a r r y n1+n2+carry n1+n2+carry；和被拆为两部分，其中，答案链表处相应位置的数字为 ( n 1 + n 2 + c a r r y ) % 10 (n1+n2+carry) % 10 (n1+n2+carry)%10，而新的进位值为 ⌊ n 1 + n 2 + c a r r y 10 ⌋ lfloorfrac{n1+n2+carry}{10}rfloor ⌊10n1+n2+carry​⌋。

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

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

TIPS: 对于链表问题，返回结果为头结点时，通常需要先初始化一个预先指针 head，该指针的下一个节点指向真正的头结点。使用预先指针的目的在于链表初始化时无可用节点值，而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#          = next
class Solution:def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:point = ListNode(None) # 创建一个头链表用来保存最终输出结果head = point # 保存头链表的位置用于最后的链表返回carry = 0  # 记录进位while l1 or l2: # 当l1或l2没走到链表尽头时new_point = ListNode(None) # 工具人，中间变量if not l1: # 如果l1先走到头了，只剩下l2sum_ = l2.val + carrynew_point.val = sum_ % 10 # 当前节点的值carry = sum_ // 10 # 进位值l2 = l2.nextelif not l2:sum_ = l1.val + carrynew_point.val = sum_ % 10carry = sum_ // 10l1 = l1.nextelse:sum_ = l1.val + l2.val + carrynew_point.val = sum_ % 10carry = sum_ // 10l1 = l1.nextl2 =  = new_point # 令point当前节点的指针指向当前计算所得结果point =  # 把前面保存的结果连过来# 最后判断有无多余的进位，如果有则需补充一个进位位if carry:new_point = ListNode( = new_point  # 用是因为head中保存的第一个节点是刚开始定义的空结点“0”

复杂度分析

时间复杂度： O ( m a x ( m , n ) ) O(max(m,n)) O(max(m,n))，其中 m , n m,n m,n 为两个链表的长度。虽然要遍历两个链表的全部位置，但是处理每个位置只需要 O ( 1 ) O(1) O(1) 的时间。

空间复杂度： O ( m a x ( m , n ) ) O(max(m,n)) O(max(m,n))。答案链表的长度最多为 较长链表的长度 +1。

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

思路&代码

暴力笨蛋法

使用暴力方法，但是时间复杂度为 O ( m + n ) O(m+n) O(m+n) 并不达标

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:numsum = []d(d(nums2)numsum.sort()if len(numsum) % 2 == 0:mid = (numsum[int(len(numsum)/2)-1] + numsum[int(len(numsum)/2)]) / 2elif len(numsum) % 2 == 1:mid = numsum[int(len(numsum)/2)]return mid

大神的世界，ACTION
Geek 三个视频，把第K小数法讲的特别详细；lesslielee

双指针法寻找中位数

将问题转化为寻找有序数组中的第K小的数
操作：折半删除
设有 m + n m+n m+n个元素，则中位数就是第 m + n 2 frac{m+n}{2} 2m+n​个，需要找的就是第 m + n 2 frac{m+n}{2} 2m+n​小的数

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:L = len(nums1) + len(nums2)if(len(nums1) <len(nums2)):nums1, nums2 = nums2 , nums1 #保持nums1比较长if L == 2:if len(nums2) == 0:return (nums1[0] + nums1[1]) / 2.0return (nums1[0] + nums2[0]) / 2.0if L%2 == 0: #evenEorO = True k = L // 2else: #OddEorO = Falsek = L // 2 + 1print(EorO, k)def helper(nums1,nums2,k): #本质上是找第k小的数if(len(nums1) <len(nums2) or (len(nums1) == len(nums2) and nums1[0] > nums2[0])):nums1, nums2 = nums2 , nums1 #保持nums1比较长；或者两个序列长度相等时，保持nums1[0]值最小if(len(nums2)==0): #递归返回条件之一，短序列nums2被剔空if EorO == True:return (nums1[k-1] + nums1[k]) / 2.0 #二序列长度之和为偶数，取nums1的第k小和k-1小数else:return nums1[k-1] #二序列长度之和为奇数，直接返回nums1的第k小数if(k==1): #递归返回条件之二，两个序列都有内容。二序列长度之和为偶数时，需判断很多边界条件。if EorO == True:n1 = min(nums1[0], nums2[0]) #取出最小的首元素if n1 == nums1[0]: #如果第一个序列的首元素最小return (n1 + min(nums1[1], nums2[0])) / 2.0 #因为此时，二序列长度不为0，nums1至少有两个元素，nums2至少有1个元素else: #如果nums2[0]最小if len(nums2) > 1: #若nums2长度大于1，则取nums2[1]与nums1[0]的较小者与nums2[0]为所需结果return (n1 + min(nums1[0], nums2[1])) / 2.0 else: #若nums2长度为1，则取nums1[0]与nums2[0]为结果return (n1 + nums1[0]) / 2.0else: #二序列长度之和为奇数return min(nums1[0],nums2[0])  #找最小数，比较数组首位t = min(k//2,len(nums2)) # 保证不上溢if( nums1[t-1]>=nums2[t-1] ): #递归调用，即每次以新的k值和新的nums1（比较后的长序列）nums2（剔掉k/2个元素的新序列）作为递归调用参数return helper(nums1 , nums2[t:],k-t)else:return helper(nums1[t:],nums2,k-t)return helper(nums1, nums2, k)作者：lesslielee
链接：/

复杂度分析

005 最长回文子串

可以说是动态规划的经典题目了

思路&代码

LeetCode-Solution

class Solution:def longestPalindrome(self, s: str) -> str:n = len(s)dp = [[False] * n for _ in range(n)]ans = ""# 枚举子串的长度 l+1for l in range(n):# 枚举子串的起始位置 i，这样可以通过 j=i+l 得到子串的结束位置for i in range(n):j = i + lif j >= len(s):breakif l == 0:dp[i][j] = Trueelif 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-Solution
链接：/

复杂度分析

时间复杂度： O ( n 2 ) O(n^2) O(n2)，其中 nn 是字符串的长度。动态规划的状态总数为 O ( n 2 ) O(n^2) O(n2)，对于每个状态，我们需要转移的时间为 O ( 1 ) O(1) O(1)。

空间复杂度： O ( n 2 ) O(n^2) O(n2)，即存储动态规划状态需要的空间。