一、No0002. 两数相加
题目
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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
- 题目数据保证列表表示的数字不含前导零
解题代码(Python3)
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
def getNum(p):
result = []
while p:
result.insert(0,str(p.val))
p = p.next
return int("".join(result))
sumNum = getNum(l1) + getNum(l2)
resList = [int(x) for x in list(str(sumNum))]
result = ListNode(resList[-1])
p = result
i = 1
n = len(resList)
while i < n:
q = ListNode(resList[-1-i])
p.next = q
p = q
i += 1
return result
思路：
- 设计自定义方法getNum去计算数值和，然后将其以int型存入到resList中
- 将result指向由resList最后一个元素构成的结点，然后通过p和q两个指针依次把剩余元素都接入到result后面
- 返回result，它代表的是一个链表
复杂度分析：
- 时间复杂度O(n)
- 空间复杂度O(l1+l2)
运行结果：
二、No0004. 寻找两个正序数组的中位数
题目
给定两个大小为 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
示例 3
- 输入：nums1 = [0,0], nums2 = [0,0]
- 输出：0.00000
示例 4
- 输入：nums1 = [], nums2 = [1]
- 输出：1.00000
示例 5
- 输入：nums1 = [2], nums2 = []
- 输出：2.00000
提示
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -106 <= nums1[i], nums2[i] <= 106
解题代码(Python3)
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
s = nums1 + nums2
length = len(s)
s.sort()
if length%2 == 0:
index = length//2
return (s[index]+s[index-1])/2
else:
index = (length-1)//2
return s[index]
思路：
- 利用python的sort方法将合并后的列表进行排序
- 若为偶数，则中位数是处于
length//2和length//2-1位置上数的平均值；若为偶数，则中位数是处于(length-1)//2位置的值
复杂度分析：
- 时间复杂度O(nlogn)
- 空间复杂度O(1)
运行结果：
三、No0005. 最长回文子串
题目
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1
- 输入：s = “babad”
- 输出：“bab”
- 解释：“aba” 同样是符合题意的答案。
示例 2
- 输入：s = “cbbd”
- 输出：“bb”
示例 3
- 输入：s = “a”
- 输出：“a”
示例 4
- 输入：s = “ac”
- 输出：“a”
提示
- 1 <= s.length <= 1000
- s 仅由数字和英文字母（大写和/或小写）组成
解题代码(Python3)-动态规划
class Solution:
def longestPalindrome(self, s: str) -> str:
length = len(s)
if length < 2:
return s
#生成状态矩阵
matrix = [[False]*length for i in range(length)]
max = 1
start = 0
for col in range(1,length):
for index in range(0,col+1):
if col == index:
matrix[index][col] = True
if s[index] == s[col]:
if col - index < 3:
matrix[index][col] = True
else:
matrix[index][col] = matrix[index+1][col-1]
if ((max < col - index + 1) and matrix[index][col]):
max = col - index + 1
start = index
return s[start:start+max]
思路：
-
设index和col代表着一个字符串中的左右索引，讨论（情况1）若col-index小于3，则夹在它们之间的子串必定为回文；（情况2）若col-index大于等于3，则需要讨论它们之间子串是否为回文且在index和col上的元素是否相等
-
新建matrix矩阵用于储存之前的状态，牺牲空间换取时间
-
第一层循环遍历每个col，第二层循环从0开始遍历到col（不含），若index和col位置上的元素不等，则直接跳过本轮循环；然后按情况1和情况2分别讨论。在第二层循环的结尾，判断matrix在当前位置的真假，然后将col-index+1与max进行比较，并将start设置为index（起始点）
-
返回
s[start:start+max]
复杂度分析：
- 时间复杂度O(n^2)
- 空间复杂度O(n^2)
运行结果：
感悟
不夸张地说，本人第一次有主观意识地使用动态规划，真的是打开了新世界的大门，希望做完50道题后，自己能有所精进，在AC之余保证时间和空间复杂度最优。