/**
* a[]：搜索的数组
* x：所要搜索的数值
* n：数组长度
* */
int BinarySearch(int a[], int x, int n){
int left =0;
int right = n-1;
while(left <= right){
int middle = (left - right)/2;
if(x == a[middle]) return middle;
if(x > a[middle]) left = middle + 1;
else right = middle-1;
}
return -1;
}
void mergeSort(int[] arr,int low,int high,int[] tmp){
if(low<high){
int mid = (low+high)/2;
mergeSort(arr,low,mid,tmp); //对左边序列进行归并排序
mergeSort(arr,mid+1,high,tmp); //对右边序列进行归并排序
merge(arr,low,mid,high,tmp); //合并两个有序序列
}
}
void merge(int[] arr,int low,int mid,int high,int[] tmp){
int i = 0;
int j = low, k = mid+1; //左边序列和右边序列起始索引
while(j <= mid && k <= high){
if(arr[j] < arr[k]){
tmp[i++] = arr[j++];
}else{
tmp[i++] = arr[k++];
}
}
//若左边序列还有剩余，则将其全部拷贝进tmp[]中
while(j <= mid){
tmp[i++] = arr[j++];
}
while(k <= high){
tmp[i++] = arr[k++];
}
for(int t=0;t<i;t++){
arr[low+t] = tmp[t];
}
}
void function(int[] arr, int low, int high){
if(low>high){
return;
}
int i = low;
int j = high;
int temp = arr[low];
while (i<j){
// while (arr[high]
// while (arr[low]>arr[i]) i++;
while (temp<arr[j] && i<j) j--;
while (temp>arr[i] && i<j) i++;
// if (arr[i]>arr[j]){
if(i<j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[low] = arr[j];
arr[j] = temp;
function(arr, low, j);
function(arr, j+1,high);
}
void function(int[] p){
int n = p.length+1;
int[][] dp = new int[n+1][n+1];
int[][] breakPoints = new int[n+1][n+1];
for(int i=0;i<n;i++) dp[i][i]=0;
for(int r=2;r<n;r++){
// for(int i=0;i/**
* val[] 物品价值
* w[] 物品重量
* m 背包的容量
* n 物品的数量
* */
void function(int[] val, int[] w, int m, int n){
// dp[i][j] 表示在前i个物品中能够装入容量为j的背包中最大价值
int[][] dp = new int[n+1][m+1];
for (int i = 1; i < n+1; i++) {
for (int j = 0; j < m+1; j++) {
//根据公式，当新增的商品重量大于当前背包的容量时，采取上一次的装入策略
if (w[i-1] > j) dp[i][j] = dp[i-1][j];
//当新增重量等于或者或者小于背包容量时，判断剩余容量的最佳策略+当前容量的最佳策略，与上次策略哪个大，取大的。
else dp[i][j] = Math.max(dp[i-1][j],val[i-1] + dp[i-1][j - w[i-1]]);
}
}
}
int function(String A, int n, String B, int m) {
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = 0;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (A.charAt(i - 1) == B.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m];
}
void function(int[][] metrics) {
int n = metrics.length+1;
int[][] dp = new int[n][n];//存放解
for (int i = 0; i < n; i++)//初始化
dp[i][i] = 0;
//r为间隔边数，先从两条边开始，即三个点组成的凸多边形（三角形）
for (int r = 2; r < n; r++) {
for (int i = 1; i < n - r; i++) { //i初始边
//i的范围 (n-1-1)-(i-1)>=r → i
int j = i+r-1;//j为i加上间隔边数
//metrics[i-1][i]+metrics[i][j]+metrics[i-1][j]: 求三角形权重
dp[i][j] = dp[i][i] + dp[i+1][j] + metrics[i-1][i]+ metrics[i][j]+ metrics[i-1][j];
//当边的取值是从i到j时的最优解 是i到i时最优解和i+1到j时的最优解再加三角形的权值
//开始考虑不同的k值
for (int k = i + 1; k < j; k++) {
int min = dp[i][k] + dp[k+1][j] + metrics[i-1][k]+ metrics[k][j]+ metrics[i-1][j];
//metrics[i-1][k]+metrics[k][j]+metrics[i-1][j]: 求三角形权重
if (min < dp[i][j]) {//有更优解
dp[i][j] = min;
}
}
}
}
}
//c 载重量
//w 每个集装箱重量
int function(int[] w, int c){
Arrays.sort(w);
int result = 0;
for(int i=0;i<w.length;i++){
if(result+w[i] <= c) result += w[i];
else break;
}
return result;
}
//n 物品的个数
//C 背包容量
//weights[] 物品重量
//values[] 物品价值
//putin[] 用来记录第i个物品是否装入背包
double function(double[] weights, double[] values, double[] putin, double C, int n){
sort(weights, values,n); //以物品的 价值/重量 为基准，对物品价值、重量这两个数组进行排序
int i;
double total = 0;
for (i = 0; i < n; i++) {
if (weights[i] <= C){//如果背包剩余的容量大于等于第i个物体的重量
putin[i] = 1; //把第i个物体整个装进背包
C = C - weights[i]; //背包的剩余容量减少了第i个物体的重量
}else {
break; //退出循环
}
}
if (i < n){//判断是否第n个物体整个装进去背包里了,如果i<=n表示否定
putin[i] = C/ weights[i];//背包剩余容量/第i个物品的重量（第i个物品放进去了一部分）
}
for(i = 0; i < n; i++){
total = total+ putin[i]* values[i];//计算总价值
}
return total;
}
//matrix距离标记矩阵，没有直接联通的两个点距离用MAX_VALUE或所有距离之和
void dijkstra(int[][] matrix, int source) {
//最短路径长度
int[] shortest = new int[matrix.length];
//判断该点的最短路径是否求出
int[] visited = new int[matrix.length];
//存储输出路径
String[] path = new String[matrix.length];
//初始化输出路径
for (int i = 0; i < matrix.length; i++) {
path[i] = (source+1) + "->" + (i+1);
}
//初始化源节点
shortest[source] = 0;
visited[source] = 1;
for (int i = 1; i < matrix.length; i++) {
int min = Integer.MAX_VALUE;
int index = -1;
for (int j = 0; j < matrix.length; j++) {
//已经求出最短路径的节点不需要再加入计算并判断加入节点后是否存在更短路径
if (visited[j] == 0 && matrix[source][j] < min) {
min = matrix[source][j];
index = j;
}
}
//更新最短路径
shortest[index] = min;
visited[index] = 1;
//更新从index跳到其它节点的较短路径
for (int m = 0; m < matrix.length; m++) {
if (visited[m] == 0 && matrix[source][index] + matrix[index][m] < matrix[source][m]) {
matrix[source][m] = matrix[source][index] + matrix[index][m];
path[m] = path[index] + "->" + (m+1);
}
}
}
//打印最短路径
for (int i = 0; i < matrix.length; i++) {
if (i != source) {
String result;
if (shortest[i] == Integer.MAX_VALUE) {
result = (source+1) + "到" + (i+1) + "不可达";
} else {
result = (source+1) + "到" + (i+1) + "的最短路径为：" + path[i] + "，最短距离是：" + shortest[i];
}
System.out.println(result);
}
}
}
/**
* M：用于标记皇后放不放的矩阵
* x：目前在判断第x个皇后房放和不放
* num：一共有几种解法
* */
void dfs(int[] M, int x){
if(x==M.length){
num++;//如果最后一个空位已经被占满了, 那就表示找到了一种安全状态, 那计数器就可以+1
return;
}
for(int y=1;y<M.length;y++){
if (isSafety(M, x, y)) {//用于判断处在xy位置的王后是否是安全的(是否和之前已经存在的几个王后冲突)
M[x] = y; //只要判断如果王后在这个点上是安全的 那就可以放上了
dfs(M,x+1); //寻找当x=x+1的时候, 王后放的位置安全的状态, 递归
}
}
M[x] = 0;//如果能运行到这一步, 说明前面判定M已经满了, 开始进行回溯(如何保证第二次寻找安全状态不会和第一次一样?)
//这一步最好不要省, 因为在下面的判断当中, 为遍历的置为0有利于提高效率
}
/**
* int cityCount 城市数量
* int minVal 最小的值
* int[] minArr 最小的集合
* int minValTemp 临时 最小的值
* int[] chooseCity 临时 最小集合
* int[] chooseCity 记录是否走过这个城市
* int[][] Metrics 城市之间的距离
* */
void travel(int step){
if(step >= cityCount){//表示走完了所有城市
if(minValTemp < minVal){
minArr = Arrays.copyOf(minArrTemp,4);
minVal = minValTemp;
}
return;
}
for(int i = 0; i < cityCount ; i++){
//下一步没有走过，并且可达，则选中
if(chooseCity[i] == 0 && Metrics[minArrTemp[step-1]][i] != -1){
minArrTemp[step] = i;
minValTemp += Metrics[minArrTemp[step-1]][i];
chooseCity[i] = 1;
travel(step+1);
//还原现场
minArrTemp[step] = -1;
chooseCity[i] = 0;
minValTemp -= Metrics[minArrTemp[step-1]][i];
}
}
}
/**
* Item[] items; // 封装的物品
* float weight; // 背包容量
* float nowWeight = 0; // 记录当前以拿重量
* float nowPrice = 0; // 记录当前以拿价格
* float betterValue; // 记录最多的价格
* */
void traceBack(int t) {//t指的是 第t个物品
if (t >= items.length) {//当所有物品全都遍历完成的时候
betterValue = nowPrice;// 记录最多的价格
output(items);// 输出最多的价格
return;
}
// 首先判断第t个物品如果拿了会怎样
if (nowWeight + items[t].w < weight) {//首先需要重量加起来不超重
nowWeight += items[t].w;
nowPrice += items[t].v;
items[t].take = true;
traceBack(t + 1);//递归判断下一个t
// 还原现场
nowWeight -= items[t].w;
nowPrice -= items[t].v;
items[t].take = false;
}
// 推出回溯并还原现场，判断第t个物品如果不拿会怎样
// bound(int i) 用于计算右面的所有item如果把 量/重 从大到小放到背包中能得到的价值
if (bound(t + 1) > betterValue) {//注意这里是和betterValue比
traceBack(t + 1);
}
}
二分查找：O(nlogn)
归并排序：O(nlogn)
快速排序：O(nlogn)
矩阵连乘：时间复杂度O(n^2) 空间复杂度O(n^3)
最优三角剖分：时间复杂度O(n^2) 空间复杂度O(n^3)
最长公共子序列（LCS）：O(mn)
Dijkstra：O(n^2)
01背包问题：O(n2^n) 或 O(nc)
哈夫曼树：O(nlg(n))
渐进阶从低到高：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）