数据结构与算法

  • 堆&栈的区别:
    • 数据结构上:
      • 栈:后进先出,桶状
      • 堆:根结点的值最小或者最大,树状
    • 内存分配上:
      • 堆内存用来放new的对象和数组
      • 栈内存用来存放方法或者局部变量
      • 堆先进先出,栈后进先出
      • 开发人员一般会自动回收堆内存
  • 最快的排序算法是哪个?
    • 希尔排序的增量数组随便(是素数最好)
    • 快速排序是最快的排序算法
    • O(nlogn)的算法:分成一半一半算的:快速排序,归并排序,堆排序
    • O(n^2)的算法:插入排序,选择排序,冒泡排序
    • 若n较小,采用插入或者选择
    • 文件初始状态基本有序:直接插入,冒泡,或快速
    • 若n较大,选择O(nlogn)的排序
      • 快速排序最快
      • 但是归并排序比较稳定
  • 堆和树的区别
    • 堆的根结点一定大于或者小于子节点,但是子节点的左右无所谓
    • 树的话无所谓,二叉树的话,左节点小于父节点小于右节点
  • 链表逆序的代码:
    • P = head.getNext()
    • Q = head.getNext().getNext()
    • T用来暂存Q.getNext()的位置
    • Q.setNext()指向P,P变成Q,Q变成T
  • 水仙花数:一个n位数,每个位上的n次幂之和等于它本身
  • KMP算法:求字符串S中是否包含字符串T
    • 对于T串重复情况的判定:
      • 模式函数
  • 蚁群算法:路径短的,频率快,留下更多信息素
  • 二叉树遍历
    • 先序遍历:根左右
    • 中序遍历:左根右
    • 后序遍历:左右根
    • 实现:递归~
      • Eg.根,左,右
    • 实现:堆栈~
  • 实现堆栈
    • Pop:li.removeFirst
    • Push:li.addFirst
    • Peek:li.peekFirst
  • 实现队列:
    • Get:li.removeFirst
    • Put:li.addLast
  • 线程安全类
    • 找出变量;找出不变条件;设计并发策略
    • synchronized关键字:代表这个方法加锁
    • 把非线程安全的对象封闭在线程安全的
    • 对象内部
Table of Contents