数据结构

  1. 数组

优点:构建一个数组简单,能在O(1)的时间根据数组下标查询某个元素

缺点:构建是必须分配一段连续的空间;查询某个元素是否存在,需要变量整个数组,耗费O(n)的时间;删除某个元素同样需要耗时O(n)的时间

  1. 链表

优点:灵活分配内存空间,能在O(1)时间内删除或添加元素

缺点:查询某个元素耗时O(n)

总结:如果数据元素个数确定,需要经常查询,那建议不要使用链表,数组更适合;如果数据元素不确定,经常需要进行添加或删除,那建议选择链表;

解题技巧:

  • 利用快慢指针(有时候需要三个指针)
  • 构建虚假列表头

优点:后进先出

总结:可以使用单链表来实现栈;当你只关心最近一次的操作时,栈是最好的选择;

  1. 队列

特点:先进先出

总结:可以使用双链表实现队列;当我们需要按照一定顺序处理数据,并且数据在不断变化,使用队列更合适;

  1. 双端队列

特点:允许在队列两端能在O(1)的时间内进行数据的查看、添加和删除

总结:常用来实现一个长度动态变化的窗口或连续的区间

共性:结构直观

常有:普通二叉树、平衡二叉树、完全二叉树、二叉搜索树、四叉树、多叉树

特殊:红黑树、自平衡二叉搜索树(不常考)

总结:大多数考察题目,都是在考察递归算法;考察树的遍历

  • 前序遍历:根、左、右 ;主要用来树里的一些搜索,以及创建一颗新的树
  • 中序遍历:左、根、右;二叉搜索树使用最多,因为二叉搜索树的左孩子<根节点<右节点,且不会出现重复的值,所以被访问到的节点大小是按顺序进行的
  • 后序遍历:左、右、根;当你在对某个数据进行分析的时候,需要从底往上遍历

提示:几种遍历方式的递归写法和非递归写法必须掌握;

发表评论

邮箱地址不会被公开。 必填项已用*标注