数据结构总结

数组,字符串

优点:

构建数组简单

能在O(1)的时间里根据数组的下标查询某个元素

缺点

构建时必须分配一段连续的内存空间

查询某个元素是否存在需要遍历整个数组,耗费O(n)的时间

LeetCode 242

查询两个字符串之间是否元素和个数都相同

链表

单链表:链表中每个元素有个指针指向下一个元素

双链表:双链表的每个节点俩指针

优点

灵活分配空间

能在O(1)的时间内删除或者添加元素

缺点

查询元素要O(n) 的时间

解题技巧:

利用快慢指针,判断链表有环

LeetCode 25

三个指针

特点

后进先出LIFO

可用一个单链表实现

算法基本思想

只关心上一次的操作

LeetCode 20

给了一堆大小括号,判断是否正确闭合,可以放到栈里,如果闭合了,就弹出

队列

先进先出FIFO

可使用双链表实现

常用场景

广度优先搜索

双端队列

可使用双链表实现

头尾能在O(1)的时间进行添加删除查看

常用场景

实现一个长度动态的区间

LeetCode 239

给定一个数组,滑动窗口大小为k,每次向右移动一位,返回窗口最大值

树的共性

结构直观

通过树考察递归

面试常考

普通二叉树

平衡二叉树

完全二叉树

二叉搜索树

四叉树

多叉树

树的遍历

前序遍历

中序遍历

后序遍历

LeetCode 230

给定一个二叉搜索树,查找第k个最小的元素,用中序遍历就好了