知识点总结系列之:(一)数据结构算法


一些常见的数据结构和算法总结

数据结构

  • 数组和链表的区别?
  • 链表的一些操作(反转,链表环路判断,双向链表,循环链表)?
  • 队列的应用?
  • 栈的应用?
  • 二叉树的遍历(三种遍历的递归和非递归的实现)?
  • 二叉树的层序遍历?
  • 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的余数是多少

答案待补充.

知识点总结系列


  1. 数据结构与算法
  2. Linux 与操作系统
  3. Mysql
  4. Redis
  5. 架构
  6. 网络
  7. PHP
  8. Go