通过一些常见场景,梳理递归相关的数据结构和算法,如列表和树互转、驼峰和下划线互转。
主要的数据结构是
- Array
- Map
- Set
Array
比较特殊,有 push
、pop
、shift
、unshift
等方法,能够当作栈使用。
Map
映射操作也很常见,减少寻址的时间复杂度(经常使用 Object
来实现类似功能)。
常用到的算法是
Iteration
(迭代)DFS
(深度优先搜索)
js
原生语法有许多迭代器,用来处理数据,如数组的 forEach
、for of
,对象的 entries()
、keys()
。
递归能实现的迭代通常来说也可以实现,如数组扁平化。递归通常来说语义更简洁,但是性能更差;迭代代码可能更复杂不好理解,但是性能更好。
仓库文件命名遵循如下规则,
Name | value | Description |
---|---|---|
A | Array | 操作包含数组 |
MSO | Map、Set、Object | 操作包含映射、集合、对象 |
I | Iteration | 操作包含迭代 |
R | Recursion | 操作包含递归 |
如 A-I
表示重点是用到数组以及迭代方法,
A-R
表示重点使用到数组以及递归方法(尽管中间过程也借助了迭代的能力)
遵循数据结构在前,操作方法在后