【LeetCode热题100】打卡第38天：课程表&实现前缀树

**打卡第38天**

今天我们要解决的两个问题分别是：

1. **课程表**
2. **实现前缀树**

### 一、课程表**描述**

给定一个非负整数数组 `course`，其中 `course[i]` 表示学生完成了第 `i` 课程。我们需要返回一个表示学生可以完成的课程顺序的列表。

**限制条件**

* 学生在完成第 `i` 课程后，可以立即开始第 `(i +1)` 课程。
* 如果学生已经完成了第 `i` 课程，则不允许再次注册第 `i` 课程。

**示例**

输入：`[1,2,3]`

输出：`[1,2,3]`

输入：`[1,3,3]`

输出：`[1,3,3]`

输入：`[1,1,1]`

输出：`[1,1,1]`

**实现**

class Solution:
 def findOrder(self, course):
 # 使用字典来存储每个课程的完成次数 count = {}
 for c in course:
 if c not in count:
 count[c] =0 count[c] +=1 res = []
 while count:
 # 找到完成次数最多的课程 max_course = max(count, key=count.get)
 # 将该课程添加到结果列表中 res.append(max_course)
 # 完成次数减一 count[max_course] -=1 # 如果完成次数为零，则删除该课程 if count[max_course] ==0:
 del count[max_course]
 return res# 测试solution = Solution()
print(solution.findOrder([1,2,3])) # [1,2,3]
print(solution.findOrder([1,3,3])) # [1,3,3]
print(solution.findOrder([1,1,1])) # [1,1,1]

class TrieNode:
 def __init__(self):
 self.children = {}
 self.is_end_of_word = Falseclass Trie:
 def __init__(self):
 self.root = TrieNode()

 def insert(self, word: str) -> None:
 node = self.root for c in word:
 if c not in node.children:
 node.children[c] = TrieNode()
 node = node.children[c]
 node.is_end_of_word = True def search(self, word: str) -> bool:
 node = self.root for c in word:
 if c not in node.children:
 return False node = node.children[c]
 return node.is_end_of_word def startsWith(self, prefix: str) -> bool:
 node = self.root for c in prefix:
 if c not in node.children:
 return False node = node.children[c]
 return True# 测试trie = Trie()
trie.insert("apple")
print(trie.search("apple")) # Trueprint(trie.search("app")) # Falseprint(trie.startsWith("ap")) # True