用回溯算法做只过了60%, 不知道错在哪了,求大佬们赐教~
public class Solution {
/**
* 返回最少多少次操作后能使这几个数变成一个等差数列,如果完全不能构造成功,就返回-1
* @param n int整型 代表一共有n个数字
* @param b int整型一维数组 代表这n个数字的大小
* @return int整型
*/
private int ans = Integer.MAX_VALUE;
public int solve (int n, int[] b) {
// 回溯算法
if(b.length == 1 || b.length == 2) return 0;
dfs(b, 0, 0);
return ans == Integer.MAX_VALUE?-1:ans;
}
public void dfs(int[] b , int ind, int op) {
//check
int i;
int gc = b[0] - b[1]; // 公差
for(i = 0; i < b.length - 1; i++) {
if(b[i] - b[i+1] != gc) {
if(i < ind - 1) return;
break;
}
}
// 满足等差数列
if(i >= b.length - 1) {
ans = Math.min(ans, op);
return;
}
// 剪枝
if(ans <= op) {
return;
}
if(ind >= b.length - 1) return;
//no operation
dfs(b, ind+1, op);
//plus one
b[ind]++;
dfs(b, ind+1, op+1);
b[ind]--;
//minus one
b[ind]--;
dfs(b, ind+1, op+1);
b[ind]++;
}
}
京公网安备 11010502036488号