2017年秋招面试遇到了算法题？看这篇就够啦
2017-08-16 本文已影响0人
Harliz
Interviews
软件工程技术面试个人指南。
Maintainer - Kevin Naughton Jr.
目录
在线练习
在线面试编程
数据结构
Linked List
- 链表即是由节点（Node）组成的线性集合，每个节点可以利用指针指向其他节点。它是一种包含了多个节点的、能够用于表示序列的数据结构。
- 单向链表: 链表中的节点仅指向下一个节点，并且最后一个节点指向空。
- 双向链表: 其中每个节点具有两个指针 p、n，使得 p 指向先前节点并且 n 指向下一个节点；最后一个节点的 n 指针指向 null。
- 循环链表：每个节点指向下一个节点并且最后一个节点指向第一个节点的链表。
- 时间复杂度:
- 索引:
O(n) - 搜索:
O(n) - 插入:
O(1) - 移除:
O(1)
- 索引:
Stack
- 栈是元素的集合，其包含了两个基本操作：push 操作可以用于将元素压入栈，pop 操作可以将栈顶元素移除。
- 遵循后入先出（LIFO）原则。
- 时间复杂度:
- 索引:
O(n) - 搜索:
O(n) - 插入:
O(1) - 移除:
O(1)
- 索引:
Queue
- 队列是元素的集合，其包含了两个基本操作：enqueue 操作可以用于将元素插入到队列中，而 dequeeu 操作则是将元素从队列中移除。
- 遵循先入先出原则 (FIFO)。
- 时间复杂度:
- 索引:
O(n) - 搜索:
O(n) - 插入:
O(1) - 移除:
O(1)
- 索引:
Tree
- 树是无向、连通的无环图。
Binary Tree
- 二叉树即是每个节点最多包含左子节点与右子节点这两个节点的树形数据结构。
- 满二叉树: 树中的每个节点仅包含 0 或 2 个节点。
- Perfect Binary Tree: 二叉树中的每个叶节点都拥有两个子节点，并且具有相同的高度。
- 完全二叉树: 除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
Binary Search Tree
- 二叉搜索树（BST）是一种特殊的二叉树，其任何节点中的值都会大于或者等于其左子树中存储的值并且小于或者等于其右子树中存储的值。
- 时间复杂度:
- 索引:
O(log(n)) - 搜索:
O(log(n)) - 插入:
O(log(n)) - 删除:
O(log(n))
- 索引:
image
