数据结构总结
数组,字符串
优点:
构建数组简单
能在O(1)的时间里根据数组的下标查询某个元素
缺点
构建时必须分配一段连续的内存空间
查询某个元素是否存在需要遍历整个数组,耗费O(n)的时间
LeetCode 242
查询两个字符串之间是否元素和个数都相同
链表
单链表:链表中每个元素有个指针指向下一个元素
双链表:双链表的每个节点俩指针
优点
灵活分配空间
能在O(1)的时间内删除或者添加元素
缺点
查询元素要O(n) 的时间
解题技巧:
利用快慢指针,判断链表有环
LeetCode 25
三个指针
栈
特点
后进先出LIFO
可用一个单链表实现
算法基本思想
只关心上一次的操作
LeetCode 20
给了一堆大小括号,判断是否正确闭合,可以放到栈里,如果闭合了,就弹出
队列
先进先出FIFO
可使用双链表实现
常用场景
广度优先搜索
双端队列
可使用双链表实现
头尾能在O(1)的时间进行添加删除查看
常用场景
实现一个长度动态的区间
LeetCode 239
给定一个数组,滑动窗口大小为k,每次向右移动一位,返回窗口最大值
树
树的共性
结构直观
通过树考察递归
面试常考
普通二叉树
平衡二叉树
完全二叉树
二叉搜索树
四叉树
多叉树
树的遍历
前序遍历
中序遍历
后序遍历
LeetCode 230
给定一个二叉搜索树,查找第k个最小的元素,用中序遍历就好了