我最近遇到了一个问题,基本上是以下问题的变体:
我们想通过删除其中一个元素来使数组按非递减顺序排序。我们可以有多少种方法做到这一点?
例如,如果输入数组为[3, 4, 5, 4]
,则答案将为2,因为我们可以删除5
或第二个4
。
如果数组是[3, 4, 5, 2]
,则答案将为1
,因为我们可以删除2
。
如果数组是[1, 2, 3, 4, 5]
,则答案将为5
,因为我们可以删除任意一个元素。
我正在努力解决这个问题。对于解决方案的策略,任何指针/方向都将受到高度赞赏。
我最近遇到了一个问题,基本上是以下问题的变体:
我们想通过删除其中一个元素来使数组按非递减顺序排序。我们可以有多少种方法做到这一点?
例如,如果输入数组为[3, 4, 5, 4]
,则答案将为2,因为我们可以删除5
或第二个4
。
如果数组是[3, 4, 5, 2]
,则答案将为1
,因为我们可以删除2
。
如果数组是[1, 2, 3, 4, 5]
,则答案将为5
,因为我们可以删除任意一个元素。
我正在努力解决这个问题。对于解决方案的策略,任何指针/方向都将受到高度赞赏。
options = 0
for i is 1 to array.length - 1
if array[i-1] > array[i]
if options is not 0
return 0
if i is 1 or array[i-2] <= array[i]
++options
if i is array.length - 1 or array[i-1] <= array[i+1]
++options
if options is 0
return 0
if options is 0
options = array.length
return options
function numberOfWays(array) {
var options = 0
for (var i = 1; i < array.length; i++) {
if (array[i-1] > array[i]) {
if (options != 0) return 0;
if (i == 1 || array[i-2] <= array[i]) ++options;
if (i == array.length - 1 || array[i-1] <= array[i+1]) ++options;
if (options == 0) return 0;
}
}
return (options == 0) ? array.length : options;
}
var arrays = [[1,2,3,4],[1,3,2,4],[1,2,4,3],[1,3,4,2],[2,4,1,3],[2,2,1,1]];
for (var a in arrays)
document.write(arrays[a] + " → " + numberOfWays(arrays[a]) + "<br>");
public static int noOfWays(int[] arr) {
int count = 0;
if (arr != null) {
if (arr.length != 1) {
boolean[] startHere = new boolean[arr.length];
boolean[] endHere = new boolean[arr.length];
endHere[0] = true;
startHere[arr.length - 1] = true;
int j = arr.length - 2;
for (int i = 1; i < arr.length; i++) {
endHere[i] = endHere[i - 1] & (arr[i - 1] <= arr[i]);
startHere[j] = startHere[j + 1] & (arr[j] <= arr[j + 1]);
j--;
}
for (int i = 0; i < arr.length; i++) {
boolean leftSorted = true;
boolean rightSorted = true;
if (i - 1 >= 0)
leftSorted = endHere[i - 1];
if (i + 1 < arr.length)
rightSorted = startHere[i + 1];
if (leftSorted && rightSorted) {
if (i - 1 >= 0 && i + 1 < arr.length) {
if (arr[i - 1] <= arr[i + 1])
count++;
} else
count++;
}
}
}
}
return count;
}
我解决了一个类似的问题,它检查给定的整数列表是否可以通过仅删除一个元素而变为非递减。
bool almostIncreasingSequence(std::vector<int> sequence) {
int err = 0;
int loc = 0;
for(int i=0;i<sequence.size()-1;i++){
if(sequence[i]>=sequence[i+1]){
err++;
loc = i;
}
}
if(err>1) return false;
if(err==0) return true;
if(loc==0) return true;
else if(loc == sequence.size()-2) return true;
if(sequence[loc-1]<sequence[loc+1]) return true;
if(sequence[loc-1]==sequence[loc+1]){
if(sequence[loc]<sequence[loc+2])
return true;
}
return false;
}
我认为这会给你一个解决问题的整体思路。