一些常见的数据结构和算法总结
数据结构
- 数组和链表的区别？
- 链表的一些操作（反转，链表环路判断，双向链表，循环链表）？
- 队列的应用？
- 栈的应用？
- 二叉树的遍历（三种遍历的递归和非递归的实现）？
- 二叉树的层序遍历？
- AVL 树是什么？
- AVL 树的旋转？
- 红黑树是什么？
- 有哪些地方应用到红黑树？
- 红黑树和 AVL 树的比较？
- B 树、B+ 树的原理？
算法
- 请简单解释算法是什么？
- 知道哪些排序算法？
- 解释什么是快速排序算法？
- 解释算法的时间复杂度？
- 有没有 O(n) 的排序算法？
- 说明什么是Skip list？
- 解释什么是“哈希算法”，它们用于什么？
- 列出一些常用的加密算法？
- 输出所有和为 S 的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
- 字符序列 S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”
- 输入一棵二叉树，判断该二叉树是否是平衡二叉树
- 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回
- 判断二叉树是否对称
- 查找字符串中第一个不重复的字符
- 统计一个数字在排序数组中出现的次数
- 实现非递归先序、中序、后序遍历二叉树
- 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径
- 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示
- 用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作
- 定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的 main 函数
- 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
- 请实现一个函数，将一个字符串中的空格替换成“%20”
- 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则
- 输入一个链表，输出该链表中倒数第k个结点
- 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序
- 从上往下打印出二叉树的每个节点，同层节点从左至右打印
- 输入一棵二叉树，求该树的深度
- 给定的二叉树，将其变换为源二叉树的镜像
- 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字
- 输入两棵二叉树 A，B，判断 B 是不是 A 的子结构。（我们约定空树不是任意一个树的子结构）
- 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树
- 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变
- 给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent。求 base 的 exponent 次方
- 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字
- TopK 问题：输入n个整数，找出其中最小的K个数
- 在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置
- 从上到下按层打印二叉树，同一层结点从左至右输出
- 请实现一个函数按照之字形打印二叉树（第一行按照从左到右打印，第二层按照从右至左打印，第三行按照从左到右打印）
- 一个链表中包含环，请找出该链表的环的入口结点
- 输入一个链表，反转链表后，输出链表的所有元素
- 输入一个链表，从尾到头打印链表每个节点的值
- 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法
假设淘宝一天有5亿条成交数据，求出销量最高的100个商品并给出算法的时间复杂度
- 有10亿个杂乱无章的数，怎样最快地求出其中前1000大的数
- 给一列无序数组，求出中位数并给出算法的时间复杂度
- 输入一个整型数组，求出子数组和的最大值，并给出算法的时间复杂度
- 给出10W条人和人之间的朋友关系，求出这些朋友关系中有多少个朋友圈（如A-B、B-C、D-E、E-F，这4对关系中存在两个朋友圈），并给出算法的时间复杂度
- 如图所示的数字三角形，从顶部出发，在每一结点可以选择向左走或得向右走，一直走到底层，要求找出一条路径，使路径上的值的和最大
- 有一个很长二进制串，求出除以3的余数是多少
答案待补充.