第三部分
LeetCode在线编程题及参考答案





3．1第1章绪论
3．1．1LeetCode在线编程题
1． LeetCode1——两数之和

问题描述： 给定一个整数数组nums和一个目标值target，请在该数组中找出和为目标值的两个整数，并返回它们的数组下标。可以假设每种输入只会对应一个答案，但是不能重复利用这个数组中同样的元素。例如，给定nums=［2，7，11，15］，target=9，因为nums［0］+nums［1］=2+7=9，所以返回［0，1］。要求设计满足题目条件的如下方法： 


视频讲解



def twoSum(self，nums: List［int］，target: int)-> List［int］:

2． LeetCode9——回文数
问题描述： 判断一个整数是否为回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如，121是回文数，而-121不是回文数。要求设计满足题目条件的如下方法： 



视频讲解



def isPalindrome(self，x: int) -> bool:

3．1．2LeetCode在线编程题参考答案
1． LeetCode1——两数之和

解： 如果用两重循环求解，时间复杂度为O(n2)，改为用index一次遍历nums，用一个字典dict存放已经遍历的整数(关键字为整数，值为该整数在nums中的索引)，对于当前遍历的整数nums［index］，若在字典中找到关键字为targetnums［index］的元素(targetnums［index］,i)，则返回i，index索引对，否则将其添加到dict中。对应的算法如下： 

class Solution:

def twoSum(self,nums:List［int］,target:int)->List［int］:

dict={}#定义一个字典

for index,item in enumerate(nums):

if target-item in dict:#找到后返回结果

return dict［target-item］,index

dict［item］=index#添加到dict

运行结果： 通过，执行用时为56ms，内存消耗为14．2MB，语言为Python 3。


第三部分LeetCode在线编程题及参考答案
数据结构教程（Python语言描述）学习与上机实验指导
2． LeetCode9——回文数
解： 将整数x转换字符串，再转换为列表，若该列表与其逆置结果相同，则为回文数，否则不是回文数。对应的算法如下： 

class Solution:

def isPalindrome(self，x: int) -> bool:

y=list(str(x))

y.reverse()#逆置

return list(str(x))==y

运行结果： 通过，执行用时为56ms，内存消耗为12．6MB，语言为Python 3。
3．2第2章线性表
3．2．1LeetCode在线编程题

以下题目中的数组采用Python列表表示，链表均为不带头结点的单链表，结点类型定义如下： 

class ListNode:

def __init__(self, x):

self.val = x

self.next = None

1． LeetCode27——移除元素
问题描述： 给定一个数组nums和一个值val，原地移除所有数值等于 val 的元素，返回移除后数组的新长度。注意不要使用额外的数组空间。例如，给定nums=［3,2,2,3］，val=3，函数应该返回新的长度2，并且nums中的前两个元素均为2，不需要考虑数组中超出新长度的后面的元素。要求设计满足题目条件的如下方法： 


视频讲解



def removeElement(self，nums: List［int］，val: int) -> int:

2． LeetCode26——删除排序数组中的重复项
问题描述： 给定一个排序数组，原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。注意不要使用额外的数组空间，即算法的空间复杂度为O(1)。例如，
给定数组nums=［1,1,2］，函数应该返回新的长度2，并且原数组nums的前两个元素被修改为1，2，不需要考虑数组中超出新长度的后面的元素。
要求设计满足题目条件的如下方法： 

def removeDuplicates(self，nums: List［int］) -> int:



视频讲解


3． LeetCode80——删除排序数组中的重复项II
问题描述： 给定一个排序数组，原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。注意不要使用额外的数组空间，即算法的空间复杂度为O(1)。例如，
给定nums=［1,1,1,2,2,3］，函数应返回新的长度5，并且原数组的前5个元素被修改为1，1，2，2，3，不需要考虑数组中超出新长度的后面的元素。
要求设计满足题目条件的如下方法： 


视频讲解



def removeDuplicates(self, nums: List［int］) -> int:

4． LeetCode4——寻找两个有序数组的中位数
问题描述： 给定两个大小为m和n的有序数组nums1和nums2，请找出这两个有序数组的中位数。假设nums1和nums2不会同时为空。例如，
nums1=［1，3］，nums2=［2］，则中位数是2．0； 
nums1=［1，2］，nums2=［3，4］，则中位数是(2+3)/2=2．5。要求设计满足题目条件的如下方法： 


视频讲解



def findMedianSortedArrays(self, nums1: List［int］, nums2: List［int］) -> float:

5． LeetCode21——合并两个有序链表
问题描述： 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。例如，
输入链表为1>2>4，1>3>4，输出结果为1>1>2>3>4>4。
要求设计满足题目条件的如下方法： 


视频讲解



def mergeTwoLists(self,l1:ListNode,l2:ListNode)->ListNode:

6． LeetCode83——删除排序链表中的重复元素
问题描述： 给定一个已经排序的链表，删除所有重复的元素，使得每个元素只出现一次。例如，
输入链表为1>1>2，输出结果为1>2； 
输入链表为1>1>2>3>3，输出结果为1>2>3。
要求设计满足题目条件的如下方法： 


视频讲解



def deleteDuplicates(self, head: ListNode) -> ListNode:

7． LeetCode203——移除链表元素
问题描述： 删除链表中等于给定值val的所有结点。例如，

输入链表为1>2>6>3>4>5>6，val=6，输出结果为1>2>3>4>5。
要求设计满足题目条件的如下方法： 


视频讲解



def removeElements(self, head: ListNode, val: int) -> ListNode:

8． LeetCode19——删除链表的倒数第n个结点
问题描述： 给定一个链表，删除链表的倒数第n个结点，并且返回链表的首结点。例如，给定一个链表为1>2>3>4>5，n=2，当删除了倒数第2个结点后，链表变为1>2>3>5。假设给定的n保证是有效的。
要求设计满足题目条件的如下方法： 



视频讲解



 def removeNthFromEnd(self, head:ListNode,n:int) -> ListNode:

9． LeetCode234——回文链表
问题描述： 判断一个链表是否为回文链表。例如，
输入链表为1>2，输出为False； 
输入链表为1>2>2>1，输出为True。
要求设计满足题目条件的如下方法： 


视频讲解



def isPalindrome(self, head: ListNode) -> bool:

10． LeetCode61——旋转链表
问题描述： 给定一个链表，旋转链表，将链表的每个结点向右移动 k 个位置，其中 k 是非负数。例如，
输入链表为1>2>3>4>5>NULL，k=2，输出结果为4>5>1>2>3>NULL，即向右旋转一步为5>1>2>3>4>NULL，再向右旋转两步为4>5>1>2>3>NULL。要求设计满足题目条件的如下方法： 


视频讲解



def rotateRight(self, head: ListNode, k: int) -> ListNode:

3．2．2LeetCode在线编程题参考答案
1． LeetCode27——移除元素

解： 采用《教程》第2章中例2．3的3种解法。采用解法1的算法如下： 

class Solution:

def removeElement(self, nums: List［int］, val: int) -> int:

k=0

for i in range(len(nums)):

if nums［i］!=val:						#将不为val的元素插入nums中

nums［k］=nums［i］

k+=1

return k                        #返回新长度k

运行结果： 通过，执行用时为36ms，内存消耗为12．7MB，语言为Python 3。
采用解法2的算法如下： 

class Solution:

def removeElement(self, nums: List［int］, val: int) -> int:

k=0

n=len(nums)                 #求长度n

for i in range(n):

if nums［i］!=val:#将不为val的元素前移k个位置

nums［i-k］=nums［i］

else:    #累计删除的元素个数k

k+=1

return n-k#返回新长度n-k

运行结果： 通过，执行用时为44ms，内存消耗为12．7MB，语言为Python 3。
采用解法3的算法如下： 

class Solution:

def removeElement(self, nums: List［int］, val: int) -> int:

i=-1

j=0

while j<len(nums):#j遍历所有元素

if nums［j］!=val:   #找到不为val的元素nums［j］

i+=1    #扩大不为val的区间

if i!=j:#i、j不相同时将这两个元素交换

nums［i］,nums［j］=nums［j］,nums［i］

j+=1   #继续扫描

return i+1   #返回新长度i+1

运行结果： 通过，执行用时为36ms，内存消耗为12．6MB，语言为Python 3。
2． LeetCode26——删除排序数组中的重复项
解： 由于是有序数组，所以重复的元素是相邻的，可以采用《教程》第2章中例2．3的3种解法。这里采用其中的解法1，算法如下： 

class Solution:

def removeDuplicates(self, nums: List［int］)->int:

k=1

for i in range(1,len(nums)):

if nums［i］!=nums［k-1］:#将不重复的元素插入nums中

nums［k］=nums［i］

k+=1

return k#返回新长度

运行结果： 通过，执行用时为100ms，内存消耗为15．4MB，语言为Python 3。
3． LeetCode80——删除排序数组中的重复项II
解： 有序数组中所有重复的元素是相邻的，采用《教程》第2章中例2．3解法1的思路，先在nums中保留开头的两个元素，k=2，用i遍历其他元素，若nums［k-1］=nums［k-2］并且nums［i］=nums［k-1］，则说明nums［i］是重复的需要删除的元素，或者说nums［k-1］≠nums［k-2］ or nums［i］≠nums［k-1］，则nums［i］是要保留的元素，将其插入，最后返回k。对应的算法如下： 

class Solution:

def removeDuplicates(self, nums: List［int］) -> int:

n=len(nums)  #求长度n

if n<=2: return n

k=2    #nums中保留两个元素

for i in range(2,n):   #遍历其他元素

if nums［k-1］!=nums［k-2］ or nums［i］!=nums［k-1］:

nums［k］=nums［i］#nums［i］为要保留的元素，插入该元素

k+=1

return k#返回新长度k

运行结果： 通过，执行用时为64ms，内存消耗为12．6MB，语言为Python 3。
4． LeetCode4——寻找两个有序数组的中位数
解： 采用《教程》2．2．3节的有序顺序表二路归并算法，在归并的结果顺序表中求中位数。对应的算法如下： 

class Solution:

def findMedianSortedArrays(self, nums1: List［int］, nums2: List［int］) -> float:

m=len(nums1)

n=len(nums2)

if m==0: return self.middle(nums2)#nums1为空的情况

if n==0: return self.middle(nums1)#nums2为空的情况

i,j,k=0,0,0

res=［］#存放归并的结果

while i<m and j<n:

if nums1［i］<nums2［j］: #将较小的nums1［i］添加到res中

res.append(nums1［i］)

i+=1

elif nums2［j］<nums1［i］:#将较小的nums2［j］添加到res中

res.append(nums2［j］)

j+=1

else:#相等的情况

res.append(nums1［i］)

res.append(nums2［j］)

i+=1

j+=1

while i<m:#nums1没有遍历完，将剩下的元素添加到res中

res.append(nums1［i］)

i+=1

while j<n:#nums2没有遍历完，将剩下的元素添加到res中

res.append(nums2［j］)

j+=1

return self.middle(res)



def middle(self,num):#求非空num中的中位数

n=len(num)

if n%2==1:  #奇数个元素

return num［n//2］*1.0

else:  #偶数个元素

return (num［n//2-1］+num［n//2］)/2

运行结果： 通过，执行用时为136ms，内存消耗为12．9MB，语言为Python 3。
5． LeetCode21——合并两个有序链表
解： 采用两个有序单链表的二路归并算法。为了简单，先创建一个头结点head，让尾结点指针tail指向它，每次将l1和l2中当前较小的结点链接到tail结点的后面，最后返回head．next。对应的算法如下： 

class Solution:

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:

head=ListNode(0)#创建一个头结点

tail=head#尾结点指针

while l1!=None and l2!=None:#两个链表都没有遍历完时循环

if l1.val < l2.val:#将较小的结点链接到head的末尾

tail.next=l1

tail=l1

l1=l1.next

else:

tail.next=l2

tail=l2

l2=l2.next

if l1!=None: tail.next = l1#将不空的链表部分直接链接到head的末尾

else: tail.next=l2

return head.next#返回不带头结点的单链表

运行结果： 通过，执行用时为44ms，内存消耗为13．9MB，语言为Python 3。
6． LeetCode83——删除排序链表中的重复元素
解： 在排序链表中所有重复元素的结点是相邻的，用pre、p一对同步指针遍历单链表head，若p．val=pre．val，删除结点p，否则同步后移一个结点，最后返回head。对应的算法如下： 

class Solution:

def deleteDuplicates(self, head: ListNode) -> ListNode:

if head==None: return head

p=head.next

pre=head

while p!=None:

if p.val == pre.val:#p结点是重复的结点

pre.next=p.next#删除p结点

else:#p结点不是重复的结点


pre=p#pre、p同步后移

p=p.next

return head

运行结果： 通过，执行用时为44ms，内存消耗为12．6MB，语言为Python 3。
7． LeetCode203——移除链表元素
解法1： 通过pre、p一对同步指针遍历单链表head来删除值为val的结点。对应的算法如下： 

class Solution:

def removeElements(self, head: ListNode, val: int) -> ListNode:

head1=ListNode(0)#增加一个头结点

head1.next=head

pre=head1

p=head

while p!=None:#用p遍历所有结点

if p.val==val:#找到值为val的结点p

pre.next=p.next#通过pre删除结点p

else:

pre=p

p=p.next

return head1.next#返回不带头结点的单链表

运行结果： 通过，执行用时为72ms，内存消耗为15．5MB，语言为Python 3。
解法2： 采用尾插法建表的思路，遍历单链表head，将所有值不等于val的结点插入新单链表中，最后返回新单链表。对应的算法如下： 

class Solution:

def removeElements(self, head: ListNode, val: int) -> ListNode:

head1=ListNode(0)#建立新单链表的头结点

tail=head1#尾指针tail

p=head

while p!=None:#遍历单链表

if p.val!=val:#将值不等于val的结点链接到tail之后

tail.next=p

tail=p

p=p.next

tail.next=None#尾结点next置为空

return head1.next

运行结果： 通过，执行用时为124ms，内存消耗为15．6MB，语言为Python 3。
8． LeetCode19——删除链表的倒数第n个结点
解法1： 先添加一个头结点h，求出结点个数m，通过正向遍历找到的第m-n个结点即为倒数第n+1个结点p，通过结点p删除其后继结点,即删除倒数第n个结点。对应的算法如下： 

class Solution:

def removeNthFromEnd(self, head:ListNode,n:int) -> ListNode:

h=ListNode(0)#增加一个头结点h

h.next=head

p=h

m=0

while p.next!=None:#求出结点个数m

m+=1

p=p.next

p=h

j=0

while j<m-n and p!=None:#找到倒数第n个结点的前驱结点p

p=p.next

j+=1

p.next=p.next.next#通过结点p删除其后继结点

return h.next

运行结果： 通过，执行用时为36ms，内存消耗为12．7MB，语言为Python 3。
解法2： 添加一个头结点h，先让p指向第n+1个结点，q指向头结点，然后同步后移直到p为空，此时q指向倒数到第n+1个结点，通过结点q删除其后继结点即删除了倒数第n个结点(长度为m的单链表中倒数第n个结点就是正数第m-n+1个结点，其前驱为正数第m-n个结点)。对应的算法如下： 

class Solution:

def removeNthFromEnd(self, head:ListNode,n:int) -> ListNode:

h=ListNode(0)#增加一个头结点h

h.next=head

p=q=h

j=0

while p!=None and j<=n:#p指向正数第n+1个结点

p=p.next

j+=1

while p!=None:#q指向倒数第n+1个结点(即正数第m-n个结点)

p=p.next

q=q.next

q.next=q.next.next#通过结点q删除其后继结点

return h.next

运行结果： 通过，执行用时为28ms，内存消耗为12．7MB，语言为Python 3。
9． LeetCode234——回文链表
解： 先采用《教程》第2章中例2．6的快慢指针法找到中间结点slow，例如单链表为(1,2,3)，slow指向2，单链表为(1,2,3,4)，slow也指向2，再以slow断开分为两个单链表，逆置后者，然后比较它们对应的结点是否相同。对应的算法如下： 

class Solution:

def isPalindrome(self, head: ListNode) -> bool:

if head==None: return True#考虑特殊情况

slow=fast=head  #查找中间结点slow

while fast!=None and fast.next!=None and fast.next.next!=None:

slow=slow.next#慢指针每次后移一个结点

fast=fast.next.next#快指针每次后移两个结点

h=slow.next

slow.next=None

q=self.reverse(h) #逆置不带头结点的单链表h

p=head

while p!=None and q!=None:#比较对应的结点值

if p.val!=q.val: return False

p=p.next

q=q.next

if q==None: return True

else: return False  



def reverse(self,head):#逆置不带头结点的单链表

h=ListNode(0)#创建一个头结点

h.next=None

p=head

while p!=None:#用头插法建单链表h

q=p.next

p.next=h.next

h.next=p

p=q

return h.next

运行结果： 通过，执行用时为76ms，内存消耗为22．7MB，语言为Python 3。
10． LeetCode61——旋转链表
解： 对于单链表(1，2，3，4，5)，当k=2时，旋转链表的过程如下。
① 找到倒数第k+1个结点(即正数第n-k个结点)，分为两个单链表(1，2，3)和(4，5)。
② 将前一个单链表链接到后一个单链表之后，得到(4，5，1，2，3)，它就是结果单链表。
旋转链表如图3．1所示，先求出单链表的结点个数n，找到尾结点tail，再找到正数第n-k个结点t，置h=t．next，t．next=None，tail．next=head，则h就是结果单链表。


图3．1旋转链表的过程


对应的算法如下： 

class Solution:

def rotateRight(self, head: ListNode, k: int) -> ListNode:

if head==None or head.next==None or k==0:

return head#考虑特殊情况

n=1

tail=head

while tail!=None and tail.next!=None:#找到尾结点tail，求出长度n

n+=1

tail=tail.next

k=k%n#求n的模

if k==0: return head#k=0时直接返回head

t=head

j=1

while j<n-k: #查找第n-k个结点t

j+=1

t=t.next

h=t.next

t.next=None  #置结点t为尾结点

tail.next=head

return h

运行结果： 通过，执行用时为32ms，内存消耗为12．8MB，语言为Python 3。
3．3第3章栈和队列
3．3．1LeetCode在线编程题
1． LeetCode20—有效的括号

问题描述： 给定一个只包括 '('、')'、'{'、'}'、'［'、'］' 的字符串，判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合。注