# 高速公路重建问题

## 举例分析

X3-x1=5-0=5,x3-x2=5-3=2,x4-x5=6-5=1,x5-x3=8-5=3,x6-x3=10-5=5,整好所有边集均清空，我们找到最终答案如下：

## 核心代码实现

```/**
* @param x
*            结果点集合
* @param distSet
*            边的优先队列，注意队列从大到小
* @param n
*            根据边集大小计算出来的 预计点个数， n(n-1)/2=distSet.size();
* @return
*/
public static boolean turnpike(int[] x, PriorityQueue<Integer> distSet, int n) {
// 倒序排列边集合
x[1] = 0;
x[n] = distSet.poll();
x[n - 1] = distSet.poll();
if (distSet.contains(x[n] - x[n - 1])) {
distSet.remove(new Integer(x[n] - x[n - 1]));
return place(x, distSet, n, 2, n - 2);
} else {
return false;
}
}

/**
* 重建高速公路-回溯算法核心
* @param x  结果集合
* @param distSet 剩余边集合 从大到小构建的堆
* @param n       预计包含的点集合
* @param left    本次尝试的左边界
* @param right   本次尝试的右边开始点
*/
private static boolean place(int[] x, PriorityQueue<Integer> distSet, int n, int left, int right) {
int dmax = 0;
boolean found = false;
if (distSet.isEmpty()) {
return true;
}
dmax = distSet.peek();
// 尝试x[right]为 dmax
if (CheckIfRight(x, distSet, n, left, right, dmax)) {
x[right] = dmax;
for (int j = 1; j < left; j++) {
distSet.remove(new Integer(Math.abs(x[j] - x[right])));
}
for (int j = right + 1; j <= n; j++) {
distSet.remove(new Integer(Math.abs(x[j] - x[right])));
}
found = place(x, distSet, n, left, right - 1);
if (!found) {
for (int j = 1; j < left; j++) {
}
for (int j = right + 1; j <= n; j++) {
}
}
}
// x[left]=x[n]-dmax
if (!found && CheckIfleft(x, distSet, n, left, right, dmax)) {
x[left] = x[n] - dmax;
for (int j = 1; j < left; j++) {
distSet.remove(new Integer(Math.abs(x[n] - dmax - x[j])));
}
for (int j = right + 1; j <= n; j++) {
distSet.remove(new Integer(Math.abs(x[n] - dmax - x[j])));
}
found = place(x, distSet, n, left + 1, right);
if (!found) {
for (int j = 1; j < left; j++) {
distSet.add(new Integer(Math.abs(x[n] - dmax - x[j])));
}
for (int j = right + 1; j <= n; j++) {
distSet.add(new Integer(Math.abs(x[n] - dmax - x[j])));
}
}
}
return found;
}```

# 正序全排列问题

## 举例说明

[1, 2, 3] [1, 2, 4] [1, 2, 5]

[1, 3, 4] [1, 3, 5]

[1, 4, 5]

[2, 3, 4] [2, 3, 5]

[2, 4, 5]

[3, 4, 5]

## 实现原理

1. 前提 数组a作为中间变量，存储可能的临时结果。 a[1]标示第一位，a[2]标示第2位，...，a[r]表示第r位 resultIndex 表示当前尝试位数，它从1开始，到r。
2. 步骤 2.1 我们从a[1]=1开始到a[1]>n-r+1结束。当resultIndex=r时存储到最终结果队列。 2.2 分支操作说明
• 当resultIndex<r 我们进行下探，即a[resultIndex+1]=a[resultIndex]+1
• 当resultIndexr==r时进行末位试探，即a[resultIndex]=a[resultIndex]+1
• 当 a[resultIndex+1]>n-r+resultIndex,进行回溯，即resultIndex--;a[resultIndex]=a[resultIndex]+1;
• 当resultIndex==r 并且 a[resultIndex+1]==n-r+resultIndex，进行末位回溯 即resultIndex--;a[resultIndex]=a[resultIndex]+1;

## 代码实现

```/**
* 核心处理方法
* @param selectIndexList 存储结果
*/
private void combOrder(List<int[]> selectIndexList) {

if(r==0){
return ;
}
if(r==1){
for (int i = 0; i<n; i++) {
}
return;
}
int resultIndex=1;
a[1]=1;
while(a[1]<=(n-r+1)){//根据第一位进行裁剪，第一位取值为1<a[1]<n-r+1 列入5个数选3个 第一位最大为5-3+1=3
if(resultIndex<r){
if(a[resultIndex]<=n-r+resultIndex){
a[resultIndex+1] = a[resultIndex]+1;
resultIndex++;
}else{// 已经超过每一位的最大值 n-r+resultIndex,进行回溯
resultIndex--;
a[resultIndex]=a[resultIndex]+1;
}
}else if(resultIndex==r){
int[] selectIndex = new int[r];
for (int j = 1; j <= r; j++) {//存储结果
selectIndex[j - 1] = a[j]-1;
}
if (a[resultIndex]==n) { // 若当前搜索结果为1，表示本次搜素完成，进行回溯 此时条件相当为 ri+a[ri]==r+1 因为ri=r所以简化啦
resultIndex--;
a[resultIndex] = a[resultIndex]+1; // 回溯
} else {
a[resultIndex] = a[resultIndex]+1; // 搜索到下一个数
}
}
}
}```

# 总结

• 回溯算法，一般需要分析 ，推导出回溯的条件。
• 回溯算法，效率一般比较低下。

# 代码地址

## github

0 条评论

• ### 面向对象设计4原则 原

若这时添加大乐透彩种的校验，需要修改OCPDemo中的validate的代码，加入另外一个else if 分支，这违反了OCP原则，并没有对修改而关闭。 可以...

• ### go语言：函数参数传递详解

参数传递是指在程序的传递过程中，实际参数就会将参数值传递给相应的形式参数，然后在函数中实现对数据处理和返回的过程。比较常见的参数传递有：值传递，按地址传递参数或...

• ### leetcode454. 4Sum II

现有四个等长且无序的整数数组，先要求从这四个数组中分别取一个数字，使得它们的和为0，问这四个数组中共有多少满足条件的数字集合。

• ### 景驰落户广州 王劲称不知百度为何指控 四条回应两大疑点

“我本人都是通过媒体才知道百度起诉我这件事儿的”。当然，景驰落户广州才是最重要的。 百度起诉前高管“侵犯商业秘密”事件又有新进展。 被问起百度起诉，“我本人都是...

• ### 高清不卡！MIT用机器学习让你更流畅的观看在线视频

问耕 编译整理 量子位 出品 | 公众号 QbitAI ? 摔！在线视频看到关键时刻，突然卡住了！ 你遇到过这样的情况么？有时候是卡住了，有时候是画质猛降。出现...

• ### 活动 | 如何从 0 到 1 打造一个爆款小程序？

对创业者而言，相比如今各大应用市场 app 的红海，高昂研发成本和用户不堪重负的手机内存。

• ### 利用手机指纹解锁电脑？？？

前几天偶然看到了一个国外大神开发的手机应用，在手机上装上这款应用之后就可以使用手机的指纹解锁来解锁PC电脑的密码，效果如下图。