Answers
想法
大概思想就是归并, 向下划分成子问题. 首先找最大值, 最小值, 并设(数组长度-1)=a, 如果最大值最小值两者差 等于a, 则为连续字串; 大于a则分组计算; 不可能小于a.
归并的时候偷个懒, 简单按最大值最小值下标划出两个 重叠的字串; 这样最终结果存在 非最长的连续字串; 最后整理一下, 找出最大的 不重复的 连续子串.
应该还存在可以优化的空间.
程序
int max(int[] input) {
int max = input[0];
for (int i : input)
max= i> max? i:max;
return max;
}
int min(int[] input) {
int min = input[0];
for (int i : input)
min=i<min?i:min;
return min;
}
void print(int[] input) {
for (int i : input)
System.out.print(i + " ");
System.out.println("\n###########");
}
static class Result {
int[] list;
int max,min;
boolean ifFinal = true;
public Result(int[] list, int max, int min) {
this.list = list;
this.max = max;
this.min = min;
}
// beaten if it is overlapped with others and is shorter
public void ifBeat(Result r) {
if (max == r.max && min == r.min) {
r.ifFinal = false;
return;
}
if (max < r.min || min > r.max)
return;
if (r.list.length > list.length)
ifFinal = false;
else
r.ifFinal = false;
}
}
private List<Result> resultList = new ArrayList<>();
void compute(int[] input) {
int max = input[0], min = max, maxInd = 0, minInd = 0;
for (int i = 1; i < input.length; i++)
if (input[i] < min) {
min = input[i];
minInd = i;
} else if (input[i] > max) {
max = input[i];
maxInd = i;
}
if ((max - min) == input.length - 1){
if (input.length != 1)
resultList.add(new Result(input, max(input), min(input)));
}else {
int aMaxInd = Math.max(minInd, maxInd);
int aMinInd = Math.min(minInd, maxInd);
compute(Arrays.copyOfRange(input, 0, aMaxInd));
compute(Arrays.copyOfRange(input, aMinInd + 1, input.length));
}
}
private void computeAll(int[] input){
compute(input);
for (int i = 0; i < resultList.size() - 1; i++) {
Result r = resultList.get(i);
if (!r.ifFinal)
continue;
for (int j = 1; j < resultList.size(); j++) {
r.ifBeat(resultList.get(j));
}
}
for (Result x : resultList)
if (x.ifFinal)
print(x.list);
}
@Test
public void test11() {
int[] input = { 15, 4, 1, 3, 2, 6, 5, 13, -7, -8, -6, 10 };
computeAll(input);
}
运行结果为:
暗系见习魔法师
answered 10 years, 7 months ago