-
第一章 字符串
-
1.1 旋转字符串
-
1.2 字符串包含
-
1.3 字符串转换成整数
-
1.4 回文判断
-
1.5 最长回文子串
-
1.6 字符串的全排列
=====================================
1.数学研究最抽象的数与结构的量、量变及其关系，算法用它与逻辑来发现从具象的问题空间到解空间的逻辑映射。算法的思想就来自于数学、逻辑及求解的工具、方法与规律中。
2.算法本身与程序无关（更与编程语言无关），程序代码是算法的一种表示方式。
3.算法通过数据结构来封装数据及对数据的操作，并基于数据结构来实现算法过程（最简单例子就是算法过程中操作数组-别拿数组不当数据结构！）。有时数据结构本身的性质也能用于设计算法，如最大堆用于堆排序。
4.算法是基于问题的，每种算法有它自己的问题背景。但是有时一种算法的思想能借鉴应用到另一个问题的解决方式中。算法的设计过程即是一个如何解题的过程。
按问题目标的类型划分
-
排序
-
插入排序
- 直接插入排序(Insert Sort) O(n^2)
- 折半插入排序(Binary Insert Sort)
- 希尔排序(Shell Sort)
-
交换排序
- 冒泡排序(Bubble Sort) O(n^2)
- 快速排序(Quick Sort)?? O(nlogn)
-
选择排序
- 直接选择排序(Select Sort) O(n^2)
- 锦标赛排序(Tournament Sort) O(nlogn)
- 堆排序(Heap Sort) O(nlogn)
-
归并排序(Merge Sort) O(nlogn)
-
基数排序(Radix Sort) O(d(n+radix))
-
桶排序(Bucket Sort) O(nlogn)
-
-
查找/搜索
-
二分查找(Binary Search)
-
树型
- 二叉搜索树(Binary Search Tree)
- 平衡搜索树(AVL Tree)
- 并查集(Union-Find Set)
-
哈希(Hashing)
-
最优化剪枝
-
可行性剪枝
-
记忆化搜索
-
枚举搜索(Enumeration)
-
深度优先(Depth First Search)
-
广度优先(Breadth First Search)
-
启发式搜索(Heuristic Search)
-
-
压缩
- 哈夫曼编码
-
加密
- 对称加密
- AES
- DES
- RC4
- 非对称加密
- RSA
- IDEA
- 对称加密
-
最优解
- 递推
- 递归(Recursion)
- 贪心算法(Greedy)
- 动态规划(DynamicProgram)
- 随机搜索
- 爬山法
- 模拟退火法
- 遗传算法
-
并行
-
机器学习
- 回归算法
- 最小二乘法(Ordinary Least Square)
- 逻辑回归(Logistic Regression)
- 逐步式回归(Stepwise Regression)
- 多元自适应回归样条(Multivariate Adaptive Regression Splines)
- 本地散点平滑估计(Locally Estimated Scatterplot Smoothing)
- 基于实例的算法
- k-Nearest Neighbor(KNN)
- 学习矢量量化（Learning Vector Quantization， LVQ）
- 自组织映射算法（Self-Organizing Map ， SOM）
- 正则化方法
- Ridge Regression
- Least Absolute Shrinkage and Selection Operator（LASSO）
- 弹性网络（Elastic Net）
- 决策树学习
- 分类及回归树（Classification And Regression Tree， CART）
- ID3 (Iterative Dichotomiser 3)
- C4.5
- Chi-squared Automatic Interaction Detection(CHAID)
- Decision Stump
- 随机森林（Random Forest）
- 多元自适应回归样条（MARS）
- 梯度推进机（Gradient Boosting Machine， GBM）
- 贝叶斯方法
- 朴素贝叶斯算法
- 平均单依赖估计（Averaged One-Dependence Estimators， AODE）
- Bayesian Belief Network（BBN）
- 基于核的算法
- 支持向量机（Support Vector Machine， SVM）
- 径向基函数（Radial Basis Function ，RBF)
- 线性判别分析（Linear Discriminate Analysis ，LDA)
- 聚类算法
- k-Means算法
- 期望最大化算法（Expectation Maximization， EM）
- 关联规则学习
- Apriori算法
- Eclat算法
- 人工神经网络
- 感知器神经网络（Perceptron Neural Network）
- 反向传递（Back Propagation）
- Hopfield网络
- 学习矢量量化（Learning Vector Quantization， LVQ）
- 深度学习
- 受限波尔兹曼机（Restricted Boltzmann Machine， RBN）
- Deep Belief Networks（DBN）
- 卷积网络（Convolutional Network）
- 堆栈式自动编码器（Stacked Auto-encoders）
- 降低维度算法
- 主成份分析（Principle Component Analysis， PCA）
- 偏最小二乘回归（Partial Least Square Regression，PLS）
- Sammon映射
- 多维尺度（Multi-Dimensional Scaling, MDS）
- 投影追踪（Projection Pursuit）
- 集成算法
- Boosting
- Bootstrapped Aggregation（Bagging）
- AdaBoost
- 堆叠泛化（Stacked Generalization， Blending）
- 回归算法
- 组织结构
- 集合结构
- 线性结构
- 线性表(Linear List)
- 栈(Stack)
- 队列(Queue)
- 数组(Array)
- 串(String)
- 广义表(General List)
- 跳跃表
- 树型结构
- 树(Tree)
- 胜者树
- 左偏树
- 二项树
- 线段树
- 后缀树
- 哈夫曼树
- trie树(静态建树、动态建树)
- 静态二叉检索树
- RMQ
- 堆(Heap) 二叉堆 斜堆
- 树(Tree)
- 图型结构
- 图(Graph)
- trie图
- 有限状态自动机
- 图(Graph)
- 统计结构
- 树状数组
- 虚二叉树
- 线段树
- 矩形面积并
- 圆形面积并
- 关系结构
- Hash表
- 并查集
- 路径压缩思想
- 组合数学
- 加法原理和乘法原理.
- 排列组合
- 容斥原理
- 抽屉原理
- 置换群与Polya定理
- 递推关系和母函数
- MoBius反演
- 偏序关系理论
- 数论
- 素数与整除问题
- 进制位
- 同余模运算
- 博奕论
- 极大极小过程
- Nim问题
- 概率论
- 数理统计
- 运筹学
- 计算几何学
- 几何公式
- 叉积和点积的运用(如线段相交的判定,点到线段的距离等)
- 凸包
- 坐标离散化.
- 扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).
- 多边形的内核(半平面交)
- 几何工具的综合应用
- 半平面求交
- 可视图的建立
- 点集最小圆覆盖.
- 对踵点
按数学领域划分
-
图论
- 图的深度优先遍历和广度优先遍历.
- 最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
- 最小生成树算法(prim,kruskal)
- 拓扑排序
- 二分图的最大匹配 (匈牙利算法)
- 最大流的增广路算法(KM算法)
- 度限制最小生成树和第K最短路.
- 最优比率生成树.
- 次小生成树.
- 无向图、有向图的最小环
- 差分约束系统的建立和求解
- 最小费用最大流
- 双连通分量
- 强连通分支及其缩点
- 图的割边和割点
- 最小割模型、网络流规约
-
动态规划
- 四边形不等式理论
- 函数的凸凹性
- 规划方向
- 旅行商问题
- 最优二分检索树
- 树型动态规划
- 状态动态规划
- 记录状态的动态规划
- LCA(Least Common Ancestors),即最近公共祖先
- RMQ(Range Minimum/Maximum Query),即区间最值查询
- 最长子序列系列问题
- 最长不下降子序列
- 最长公共子序列
- 最长公共不下降子序列
- 不完全状态记录
- 青蛙过河问题
- 利用区间dp
- 背包类问题
- 0-1背包，经典问题
- 无限背包，经典问题
- 判定性背包问题
- 带附属关系的背包问题
- +-1背包问题
- 双背包求最优值
- 构造三角形问题
- 带上下界限制的背包问题(012背包)
- 线性的动态规划问题
- 积木游戏问题
- 决斗（判定性问题）
- 圆的最大多边形问题
- 统计单词个数问题
- 棋盘分割
- 日程安排问题
- 最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)
- 方块消除游戏(某区间可以连续消去求最大效益)
- 资源分配问题
- 数字三角形问题
- 邮局问题与构造答案
- 最高积木问题
- 两段连续和最大
- 2次幂和问题
- N个数的最大M段子段和
- 交叉最大数问题
- 判定性问题的dp(如判定整除、判定可达性等)
- 模K问题的dp
- 特殊的模K问题，求最大(最小)模K的数
- 变换数问题
- 单调性优化的动态规划
- 1-SUM问题
- 2-SUM问题
- 序列划分问题(单调队列优化)
- 剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)
- 凸多边形的三角剖分问题
- 乘积最大问题
- 多边形游戏(多边形边上是操作符,顶点有权值)
- 石子合并(N^3/N^2/NLogN各种优化)
- 贪心的动态规划
- 最优装载问题
- 部分背包问题
- 乘船问题
- 贪心策略
- 双机调度问题Johnson算法
- 状态dp
- 牛仔射击问题(博弈类)
- 哈密顿路径的状态dp
- 两支点天平平衡问题
- 一个有向图的最接近二部图
- 树型dp
- 完美服务器问题(每个节点有3种状态)
- 小胖守皇宫问题
- 网络收费问题
- 树中漫游问题
- 树上的博弈
- 树的最大独立集问题
- 树的最大平衡值问题
- 构造树的最小环