数位动态规划（Digit Dynamic Programming，数位DP）是一种动态规划算法，用于解决涉及数字各位数的组合问题。以下是一个数位DP的Java代码示例，用于计算在区间 [1, N] 内，所有数字的各位之和等于给定值 K 的个数：
1 | public class DigitDP { |
在这个示例中，countNumbersWithDigitSum 方法使用数位DP解决了计算各个数字各位数之和等于给定值 K 的数字个数问题。算法通过构建一个二维数组 dp 来保存状态转移，从而计算符合条件的数字个数。
这个示例是一个数位DP的实现，实际应用中可能需要根据不同的问题进行适当的修改。
插头DP（Socket DP）是一种动态规划算法，通常用于解决一些组合优化问题，如硬币找零问题、背包问题等。以下是一个插头DP的Java代码示例，用于解决硬币找零问题：
1 | public class SocketDP { |
在这个示例中，coinChange 方法使用插头DP解决了硬币找零问题。算法通过构建一个一维数组 dp 来保存每个金额所需的最小硬币数量。通过逐步填表，我们可以找到构成给定金额的最少硬币数量。
这个示例是一个插头DP的实现，实际应用中可能需要根据不同的问题进行适当的修改。
拉格朗日乘子法（Lagrange Multiplier Method）是一种优化算法，用于求解带有约束条件的优化问题。以下是一个使用拉格朗日乘子法求解约束最优化问题的Java代码示例：
1 | import org.apache.commons.math3.optim.*; |
在这个示例中，我们使用了Apache Commons Math库来实现拉格朗日乘子法。我们定义了一个线性目标函数，一组线性约束条件和变量的边界范围，并通过线性规划求解器进行求解。这个示例求解了以下问题：
最大化：f(x, y) = x + y
约束条件：2x + y >= 1, x + 2y >= 1
变量范围：x >= 0, y >= 0
请注意，实际应用中的问题可能更加复杂，代码也可能需要进行适当的调整。
/**
* 无向图
*/
public class NoDirectionGraph {
private int mMaxSize; //图中包含的最大顶点数
private GraphVertex[] vertexList; //顶点数组
private int[][] indicatorMat; //指示顶点之间的连通关系的邻接矩阵
private int nVertex; //当前实际保存的顶点数目
public NoDirectionGraph(int maxSize) {
mMaxSize = maxSize;
vertexList = new GraphVertex[mMaxSize];
indicatorMat = new int[mMaxSize][mMaxSize];
nVertex = 0;
//初始化邻接矩阵元素为0
for(int j=0;j<mMaxSize;j++) {
for(int k=0;k<mMaxSize;k++) {
indicatorMat[j][k] = 0;
}
}
}
public void addVertex(GraphVertex v) {
if(nVertex < mMaxSize) {
vertexList[nVertex++] = v;
} else {
System.out.println("---插入失败，顶点数量已达上限!");
}
}
/**
* 修改邻接矩阵，添加新的边
* @param start
* @param end
*/
public void addEdge(int start,int end) {
indicatorMat[start][end] = 1;
indicatorMat[end][start] = 1;
}
/**
* 打印邻接矩阵
*/
public void printIndicatorMat() {
for(int[] line:indicatorMat) {
for(int i:line) {
System.out.print(i + " ");
}
System.out.println();
}
}
/**
* 深度优先遍历
* @param vertexIndex 表示要遍历的起点,即图的邻接矩阵中的行数
*/
public void DFS(int vertexIndex) {
ArrayStack stack = new ArrayStack();
//1.添加检索元素到栈中
vertexList[vertexIndex].setVisited(true);
stack.push(vertexIndex);
int nextVertexIndex = getNextVertexIndex(vertexIndex);
while(!stack.isEmpty()) { //不断地压栈、出栈，直到栈为空(检索元素也没弹出了栈)为止
if(nextVertexIndex != -1) {
vertexList[nextVertexIndex].setVisited(true);
stack.push(nextVertexIndex);
stack.printElems();
} else {
stack.pop();
}
//检索当前栈顶元素是否包含其他未遍历过的节点
if(!stack.isEmpty()) {
nextVertexIndex = getNextVertexIndex(stack.peek());
}
}
}
/**
* 得到当前顶点的下一个顶点所在行
* @param column
* @return
*/
public int getNextVertexIndex(int column) {
for(int i=0;i<indicatorMat[column].length;i++) {
if(indicatorMat[column][i] == 1 && !vertexList[i].isVisited()) {
return i;
}
}
return -1;
}
/**
* 广度优先遍历
* @param vertexIndex 表示要遍历的起点,即图的邻接矩阵中的行数
*/
public void BFS(int vertexIndex) {
ChainQueue queue = new ChainQueue();
vertexList[vertexIndex].setVisited(true);
queue.insert(new QueueNode(vertexIndex));
int nextVertexIndex = getNextVertexIndex(vertexIndex);
while(!queue.isEmpty()) {
if(nextVertexIndex != -1) {
vertexList[nextVertexIndex].setVisited(true);
queue.insert(new QueueNode(nextVertexIndex));
} else {
queue.remove();
}
if(!queue.isEmpty()) {
nextVertexIndex = getNextVertexIndex(queue.peek().data);
queue.printElems();
}
}
}
}
/**
使用数组实现栈结构
*/
public class ArrayStack {
private int[] tArray;
private int topIndex = -1; //表示当前栈顶元素的索引位置
private int CAPACITY_STEP = 12; //数组容量扩展步长
public ArrayStack() {
/创建泛型数组的一种方法/
tArray = new int[CAPACITY_STEP];
}
/**
- 弹出栈顶元素方法
- @return
*/
public int pop() {
if(isEmpty()) {
System.out.println(“错误，栈中元素为空，不能pop”);
return -1;
} else {
int i = tArray[topIndex];
tArray[topIndex–] = -1; //擦除pop元素
return i;
}
}
/**
- 向栈中插入一个元素
- @param t
*/
public void push(int t) {
//检查栈是否已满
if(topIndex == (tArray.length-1)) {
//扩展容量
int[] tempArray = new int[tArray.length + CAPACITY_STEP];
for(int i=0;i<tArray.length;i++) {
tempArray[i] = tArray[i];
}
tArray = tempArray;
tempArray = null;
} else {
topIndex ++;
tArray[topIndex] = t;
}
}
/**
- 得到栈顶元素，但不弹出
- @return
*/
public int peek() {
if(isEmpty()) {
System.out.println(“错误，栈中元素为空，不能peek”);
return -1;
} else {
return tArray[topIndex];
}
}
/**
- 判断当前栈是否为空
- @return
*/
public boolean isEmpty() {
return (topIndex < 0);
}
/**
- 打印栈中元素
*/
public void printElems() {
for(int i=0;i<=topIndex;i++) {
System.out.print(tArray[i] + “ “);
}
System.out.println();
}
}
/**
使用链表实现队列
*/
public class ChainQueue {
private QueueNode head; // 指向队列头节点
private QueueNode tail; // 指向队列尾节点
private int size = 0; // 队列尺寸
public ChainQueue() {
}
/**
插入新节点到队列尾
*/
public void insert(QueueNode node) {
// 当然也可以这么写,添加tail.prev = node
if (head == null) {
head = node;
tail = head;
} else {
node.next = tail;
tail.prev = node; // 双向连接，确保head.prev不为空
tail = node;
}
size++;
}
/**
- 移除队列首节点
*/
public QueueNode remove() {
if (!isEmpty()) {
QueueNode temp = head;
head = head.prev;
size–;
return temp;
} else {
System.out.println(“异常操作，当前队列为空!”);
return null;
}
}
/**
- 队列是否为空
- @return
*/
public boolean isEmpty() {
if (size > 0) {
return false;
} else {
return true;
}
}
/**
- 返回队列首节点，但不移除
*/
public QueueNode peek() {
if (!isEmpty()) {
return head;
} else {
System.out.println();
System.out.println(“异常操作，当前队列为空!”);
return null;
}
}
/**
- 返回队列大小
- @return
*/
public int size() {
return size;
}
/**
- 打印队列中的元素
*/
public void printElems() {
QueueNode tempNode = head;
while(tempNode != null) {
System.out.print(tempNode.data + “ “);
tempNode = tempNode.prev;
}
System.out.println();
}
}
/**
- 节点类
- @author wly
*/
class QueueNode {
QueueNode prev;
QueueNode next;
int data;
public QueueNode(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
@Override
public String toString() {
// TODO Auto-generated method stub
super.toString();
return data + “”;
}
}
单调队列优化算法（Monotonic Queue Optimization）是一种优化技巧，通常用于解决一些需要维护滑动窗口中最大（最小）值的问题。以下是一个单调队列优化的Java代码示例，用于解决滑动窗口中的最大值问题：
1 | import java.util.ArrayDeque; |
在这个示例中，maxSlidingWindow 方法使用单调队列优化解决了滑动窗口中的最大值问题。算法通过维护一个单调递减的队列来存储当前窗口内的元素下标，从而在常数时间内找到窗口内的最大值。
请注意，单调队列优化通常适用于需要在滑动窗口内求最大值（最小值）的问题，可以根据问题的具体需求进行相应的修改。
区间动态规划（Interval Dynamic Programming，简称区间DP）是一种动态规划算法，用于解决涉及区间的问题。以下是一个区间DP的Java代码示例，用于解决最长回文子序列问题：
1 | public class IntervalDP { |
在这个示例中，longestPalindromicSubsequence 方法使用区间动态规划解决了最长回文子序列问题。通过构建一个二维数组 dp[i][j] 来保存字符串区间 s[i..j] 的最长回文子序列长度。通过填表过程，我们可以找到最长回文子序列的长度。
这个示例是一个区间动态规划的实现，实际应用中可能需要根据不同的问题进行适当的修改。
关键路径算法（Critical Path Method，CPM）是一种用于项目管理的算法，用于确定项目中最长的路径，即关键路径，以及各个任务的最早开始时间和最晚开始时间。以下是一个关键路径算法的Java代码示例：
1 | import java.util.*; |
在这个示例中，我们使用关键路径算法来计算一个简单项目的关键路径。Task 类表示任务，其中包含任务名称、持续时间和依赖关系。calculateCriticalPath 方法计算每个任务的最早开始时间和最晚开始时间，并根据最早开始时间和最晚开始时间的差异来确定关键路径。
这个示例是一个简化的关键路径算法实现，实际应用中可能需要考虑更多的细节和优化。
自然界现象抽象化得到的数列模型——斐波那契数列
繁殖得到 一对刚出生的兔子-> 第1步总结： 当月的兔子数=上月兔子数+当月新生兔子 数列的当前列=前两列之和
指数阶算法，效率较低，时间复杂度爆炸增量
Fib1(int n)
{ if(n<1)
return -1;
if(n==1||n==2)
return 1;
return Fib1(n-1)+Fib1(n-2);
}
时间复杂度从指数阶降到了多项式阶O(n),空间复杂度O(n)
Fib2(intn)
{
if(n<1)
return-1;
int[] a=new int[n];
a[1]=1;
a[2]=1;
for(int i=3;i<=n;i++)
a[i]=a[i-1]+a[i-2];
return a[n];
}
}
不记录中间结果，只记录中间项，空间复杂度降到O(1)
Fib3(intn)
{
inti,s1,s2;
if(n<1)
return-1;
if(n==1||n==2)
return1;
s1=1;s2=1;
for(i=3;i<=n;i++)
{
s2=s1+s2;//辗转相加法
s1=s2-s1;//记录前一项
}
return s2;
}
斐波那契数列(F(n),F(n-1))为(1,1)与{{1,1},{1,0}}的n-2次幂的乘积, 可通过递推求证
public static int ValueN(int n){
if(n<1){
return 0;
}
if(n==1 || n==2){
return 1;
}
int [][] base={{1,1},{1,0}};
int [][] res=matrixPower(base,n-2);
return res[0][0]+res[1][0];
}
public static int[][] matrixPower(int[][] m,int p){
if(p==0)
return null;
if(p==1)
return m;
int[][] res=matrixPower(m,p>>1);
res=muliMatrix(res,res);
if((p&1)==1){
res=muliMatrix(res,m);
}
return res;
}
//求两个矩阵相乘得到一个新的矩阵
public static int[][] muliMatrix(int[][] m1,int[][] m2){
int [][] res=new int[m1.length][m2[0].length];
for(int i=0;i<m1.length;i++){
for(int j=0;j<m2[0].length;j++){
for(int k=0;k<m2.length;k++){
res[i][j]+=m1[i][k]*m2[k][j];
}
}
}
return res;
}
}
倍增算法（也称为指数跳跃算法）是一种高效的算法，用于解决一些特定的查找问题，例如在数组中查找某个区间内的最小值或最大值。以下是一个倍增算法的Java代码示例，用于解决查找最小值的问题：
1 | public class SparseTable { |
在这个示例中，buildSparseTable 方法构建了一个稀疏表，用于在数组中查询指定范围内的最小值。queryMin 方法用于查询指定范围内的最小元素。这种方法的时间复杂度为O(1)查询，但需要O(n log n)的预处理时间和O(n log n)的空间。
倍增算法在一些特定的查找问题中非常有用，如查找最小值、最大值等。但请注意，它适用于不会频繁修改数组内容的情况，因为构建稀疏表的开销较大。
二分查找（Binary Search）是一种高效的搜索算法，用于在有序数组中查找特定元素。以下是一个二分查找的Java代码示例：
1 | public class BinarySearch { |
在这个示例中，binarySearch 方法使用二分查找算法在有序数组中查找特定元素。算法通过比较目标值与中间元素的大小来逐步缩小搜索范围，直到找到目标元素或搜索范围为空。
请注意，二分查找只适用于有序数组。如果数组无序，需要先进行排序操作。