难度: Medium
Submission
运行时间: 59 ms
内存: 18.4 MB
from typing import List
class TodoList:
def __init__(self):
self.tasks = {} # 用于存储任务的字典，键为用户ID，值为任务列表
self.task_count = {} # 用于跟踪每个用户的任务计数
self.next_task_id = 1 # 下一个任务的ID
def addTask(self, userId: int, taskDescription: str, dueDate: int, tags: List[str]) -> int:
if userId not in self.tasks:
self.tasks[userId] = []
self.task_count[userId] = 0
task_id = self.next_task_id
self.next_task_id += 1
task = {
'id': task_id,
'description': taskDescription,
'dueDate': dueDate,
'tags': tags,
'completed': False
}
self.tasks[userId].append(task)
self.task_count[userId] += 1
# 按到期日期排序任务
self.tasks[userId].sort(key=lambda x: x['dueDate'])
return task_id
def getAllTasks(self, userId: int) -> List[str]:
if userId not in self.tasks:
return []
return [task['description'] for task in self.tasks[userId] if not task['completed']]
def getTasksForTag(self, userId: int, tag: str) -> List[str]:
if userId not in self.tasks:
return []
return [task['description'] for task in self.tasks[userId] if tag in task['tags'] and not task['completed']]
def completeTask(self, userId: int, taskId: int) -> None:
if userId not in self.tasks:
return
for task in self.tasks[userId]:
if task['id'] == taskId:
task['completed'] = True
break
Explain
该题解实现了一个待办事项清单，允许多个用户添加、查询和完成任务。每个任务包含描述、截止日期、标签和完成状态。主要功能包括添加任务、获取所有未完成任务、按标签获取未完成任务和完成指定任务。实现思路如下： 1. 使用字典存储每个用户的任务列表和任务计数。 2. 添加任务时，生成唯一的任务ID并存储任务详细信息。任务按截止日期排序。 3. 查询功能允许按用户ID获取未完成任务列表，或按特定标签筛选。 4. 完成任务功能通过标记任务为已完成来更新任务状态。
时间复杂度: O(n log n) for addTask, O(k) for getAllTasks, getTasksForTag, and completeTask
空间复杂度: O(m)
from typing import List
class TodoList:
def __init__(self):
self.tasks = {} # Dictionary to store tasks per user
self.task_count = {} # Track number of tasks per user
self.next_task_id = 1 # ID for the next task
def addTask(self, userId: int, taskDescription: str, dueDate: int, tags: List[str]) -> int:
if userId not in self.tasks:
self.tasks[userId] = []
self.task_count[userId] = 0
task_id = self.next_task_id
self.next_task_id += 1
task = {
'id': task_id,
'description': taskDescription,
'dueDate': dueDate,
'tags': tags,
'completed': False
}
self.tasks[userId].append(task)
self.task_count[userId] += 1
# Sort tasks by due date
self.tasks[userId].sort(key=lambda x: x['dueDate'])
return task_id
def getAllTasks(self, userId: int) -> List[str]:
if userId not in self.tasks:
return []
return [task['description'] for task in self.tasks[userId] if not task['completed']]
def getTasksForTag(self, userId: int, tag: str) -> List[str]:
if userId not in self.tasks:
return []
return [task['description'] for task in self.tasks[userId] if tag in task['tags'] and not task['completed']]
def completeTask(self, userId: int, taskId: int) -> None:
if userId not in self.tasks:
return
for task in self.tasks[userId]:
if task['id'] == taskId:
task['completed'] = True
break
Explore
在实现中，如果用户ID不存在于系统中，系统会自动为该用户ID创建一个新的任务列表和任务计数。在`addTask`方法中，首先检查`userId`是否已存在于`tasks`字典中。如果不存在，就会为该用户初始化一个空的任务列表和任务计数设为0。因此，该方法可以无缝处理新用户的任务添加，不需要额外的错误处理或拒绝操作。
每次在添加任务后对任务列表进行排序确实会影响性能，尤其是当任务数量非常大时。在当前的实现中，使用的排序方法是`O(n log n)`的时间复杂度，这在任务列表较长时可能会成为性能瓶颈。为了提高效率，可以考虑使用优先队列（例如堆结构）来维护任务的有序状态。通过堆，插入新任务的时间复杂度可以降低到`O(log n)`，从而在处理大量任务时保持较高的效率。
在当前的`completeTask`方法实现中，如果指定的任务ID不存在于用户的任务列表中，则该方法不会执行任何操作，也不会提供任何错误反馈。为了改进用户体验和系统的健壮性，可以修改方法来返回一个状态指示，例如返回一个布尔值表示任务完成是否成功，或者抛出一个异常来通知调用者任务ID无效。这样可以使得调用者能够更明确地了解操作的结果并据此做出相应的响应。