向我展示数据结构
使用高级数据结构(链接列表,队列,树,递归函数...)解决六个编程任务
这些编程挑战是UDACITY 第二个项目的。
问题涵盖了与本课程中学习的数据结构相关的各种主题。 目的是考虑到代码的效率和设计选择,以Python编写干净有效的解决方案。 该代码应有充分的解释,优雅且易于阅读。
内容
问题1:最近最少使用的缓存
设计选择:我对存储的项目使用字典,因为它为获取/设置/删除操作提供了复杂度O(1)。 更准确地说,我使用orderedDict()结构来跟踪使用顺序。 orderedDict()可用作队列来管理最不常用的密钥。 dict()随着每个操作而更新,因此表现为队列结构。
时间复杂度:所有操作都有固定的时间。
空间复杂度:通过查看字典的长度来管理最大容量。 空间复杂度为O(capacity),它等效于O(1),因为它与执行的操作数无关。
问题2:查找文件
设计
1