数据结构与算法

  • 堆&栈的区别：
    • 数据结构上：
      • 栈：后进先出，桶状
      • 堆：根结点的值最小或者最大，树状
    • 内存分配上：
      • 堆内存用来放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