难度: Hard
Submission
运行时间: 326 ms
内存: 86.4 MB
import heapq
class Video:
def __init__(self, id, data):
self.id = id
self.data = data
self.start = 0
self.end = 0
self.view = 0
self.like = 0
self.dislike = 0
class VideoSharingPlatform:
def __init__(self):
self.ids = 0
self.usedid = []
self.dict = {}
def upload(self, video: str) -> int:
if not self.usedid:
id = self.ids
self.ids += 1
else:
id = heapq.heappop(self.usedid)
self.dict[id] = Video(id, video)
return id
def remove(self, videoId: int) -> None:
if videoId in self.dict:
del self.dict[videoId]
heapq.heappush(self.usedid, videoId)
def watch(self, videoId: int, startMinute: int, endMinute: int) -> str:
if videoId in self.dict:
v = self.dict[videoId]
v.view += 1
e = min(endMinute, len(v.data))
if startMinute <= e and startMinute < len(v.data):
return v.data[startMinute:e + 1]
return "-1"
def like(self, videoId: int) -> None:
if videoId in self.dict:
self.dict[videoId].like += 1
return -1
def dislike(self, videoId: int) -> None:
if videoId in self.dict:
self.dict[videoId].dislike += 1
return -1
def getLikesAndDislikes(self, videoId: int) -> List[int]:
if videoId in self.dict:
return [self.dict[videoId].like, self.dict[videoId].dislike]
return [-1]
def getViews(self, videoId: int) -> int:
if videoId in self.dict:
return self.dict[videoId].view
return -1
# Your VideoSharingPlatform object will be instantiated and called as such:
# obj = VideoSharingPlatform()
# param_1 = obj.upload(video)
# obj.remove(videoId)
# param_3 = obj.watch(videoId,startMinute,endMinute)
# obj.like(videoId)
# obj.dislike(videoId)
# param_6 = obj.getLikesAndDislikes(videoId)
# param_7 = obj.getViews(videoId)
Explain
该题解设计了一个简单的视频共享平台，包含视频上传、删除、观看、点赞、点踩、获取点赞点踩数和观看次数的功能。其中，使用了一个字典来存储视频ID和视频对象的映射，以及一个最小堆来管理回收使用过的视频ID。每个视频对象有自己的ID、数据内容、观看次数、点赞数和点踩数。上传视频时，如果有回收的ID就使用，否则新分配一个。删除视频时，将其从字典中删除并将ID放入最小堆。观看视频时，更新观看次数并返回请求的视频片段。点赞和点踩功能分别更新视频对象的对应计数器。
时间复杂度: O(log n)
空间复杂度: O(n)
import heapq
class Video:
def __init__(self, id, data):
self.id = id # 视频ID
self.data = data # 视频内容
self.view = 0 # 观看次数
self.like = 0 # 点赞次数
self.dislike = 0 # 点踩次数
class VideoSharingPlatform:
def __init__(self):
self.ids = 0 # 用于生成新的视频ID
self.usedid = [] # 存储被删除视频的ID，用最小堆管理
self.dict = {} # 存储视频ID到视频对象的映射
def upload(self, video: str) -> int:
if not self.usedid:
id = self.ids
self.ids += 1
else:
id = heapq.heappop(self.usedid) # 从回收的ID中获取一个最小的ID
self.dict[id] = Video(id, video)
return id
def remove(self, videoId: int) -> None:
if videoId in self.dict:
del self.dict[videoId]
heapq.heappush(self.usedid, videoId) # 将删除的ID回收到最小堆中
def watch(self, videoId: int, startMinute: int, endMinute: int) -> str:
if videoId in self.dict:
v = self.dict[videoId]
v.view += 1 # 更新观看次数
e = min(endMinute, len(v.data))
if startMinute <= e and startMinute < len(v.data):
return v.data[startMinute:e + 1] # 返回视频内容的指定片段
return \"-1\"
def like(self, videoId: int) -> None:
if videoId in self.dict:
self.dict[videoId].like += 1 # 更新点赞次数
return -1
def dislike(self, videoId: int) -> None:
if videoId in self.dict:
self.dict[videoId].dislike += 1 # 更新点踩次数
return -1
def getLikesAndDislikes(self, videoId: int) -> List[int]:
if videoId in self.dict:
return [self.dict[videoId].like, self.dict[videoId].dislike] # 返回点赞和点踩的数量
return [-1]
def getViews(self, videoId: int) -> int:
if videoId in self.dict:
return self.dict[videoId].view # 返回观看次数
return -1
# Your VideoSharingPlatform object will be instantiated and called as such:
# obj = VideoSharingPlatform()
# param_1 = obj.upload(video)
# obj.remove(videoId)
# param_3 = obj.watch(videoId,startMinute,endMinute)
# obj.like(videoId)
# obj.dislike(videoId)
# param_6 = obj.getLikesAndDislikes(videoId)
# param_7 = obj.getViews(videoId)
Explore
在设计中，删除视频时会首先检查该视频ID是否存在于字典中。如果存在，才会进行删除操作，同时该视频ID被添加到最小堆中以供未来复用。为了增强安全性，可以在删除前检查视频是否正在被观看，例如通过增加一个'正在观看'的状态标记。如果视频正在被观看，可以暂时延迟删除操作或拒绝删除，直到没有用户正在观看该视频。这样可以避免删除正在观看的视频带来的问题。
使用最小堆来管理回收的视频ID可以确保每次分配给新视频的ID总是最小可用的ID。这有助于保持ID的紧凑分配，避免ID数值无限增长。如果使用栈或队列，则可能导致新视频获得较大的ID，即使存在更小的可用ID，从而导致ID的使用不够经济和有效。最小堆每次都能以对数时间复杂度提供最小元素，保证了效率和ID使用的最优化。
在设计中，只有在删除视频对象后，该视频的ID才会被添加到最小堆中。这个操作保证了所有在最小堆中的ID都是已经从字典中移除的，因此这些ID对应的视频已被删除。在上传视频时，从最小堆中取出的ID再次被使用之前，会从堆中移除并加入到字典中，这个过程保证了ID的唯一性和一致性，避免了ID的重复使用。