raylew_algorithm

my work on algorithm

那些年做过的算法题

按题目来源分类

• book1-算法竞赛入门经典
• book2-算法导论
• book3-算法设计与分析基础
• hsoj-湖北师范大学oj
• lanqiaocup-工信部蓝桥杯算法大赛预赛真题
• ntoj-南通中学信息奥林匹克竞赛在线评测系统
• os-操作系统设计有关的算法
• other-一些来路不明的算法题
• poj-北京大学oj

按题目性质分类

一.基本算法

• 枚举
  • POJ1753
  • POJ2965
• 贪心
  • 突击战
  • 最大兼容活动集
• 递归和分治法
  • 归并排序
  • 最大子数组
  • 棋盘覆盖
• 递推
• 构造法
• 模拟法

二.图算法

• 深度优先遍历
  • 39级台阶
  • 八皇后问题
  • 还原ip地址
  • 困难的串
  • 四色问题
  • 素数环
  • 组合问题
• 广度优先遍历
  • 八数码问题
  • 倒水问题
  • 四子连棋
• 最短路径算法
  • 无向图中任意两点的最短路径

三.数据结构

• 串
  • 周期串
  • 困难的串
• 排序(快排、归并排(与逆序数有关)、堆排)
  • 排序算法合集
• 简单并查集的应用
• 哈希表和二分查找等高效查找法(数的Hash,串的Hash)
  • 折半查找
• 哈夫曼树
• 堆
• 树(静态建树、动态建树)

四.简单搜索

• 深度优先搜索
• 广度优先搜索
• 简单搜索技巧和剪枝

五.动态规划

• 背包问题
  • 01背包问题

六.数学

• 组合数学
  • 加法原理和乘法原理
  • 排列组合
    • 全排列
  • 递推关系
    • 子集1
    • 子集2
• 数论
  • 素数与整除问题
  • 进制位
  • 同余模运算
• 计算方法
  • 二分法求解单调函数相关知识

七.计算几何学

• 几何公式
• 叉积和点积的运用(如线段相交的判定,点到线段的距离等)
• 多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
• 凸包