沒什么思路啊，題目如下Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.
Example
For sequence = [1, 3, 2, 1], the output should bealmostIncreasingSequence(sequence) = false;
There is no one element in this array that can be removed in order to get a strictly increasing sequence.
For sequence = [1, 3, 2], the output should bealmostIncreasingSequence(sequence) = true.
You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].
Input/Output
[time limit] 4000ms (js)[input] array.integer sequence
Guaranteed constraints:2 ≤ sequence.length ≤ 105,-105 ≤ sequence[i] ≤ 105.
[output] boolean
Return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.
有個思路：2層循環，第一循環移除元素，第二層循環判斷移除這個元素后是否有自增序列。
4 回答
函數式編程
TA貢獻1807條經驗 獲得超9個贊
提供一個思路
作出逐差數組: 如 a=[1,3,2,1]，逐差后得 [2,-1,-1]
所謂刪除一個元素，即在在逐差數組中去頭或去尾，或把相鄰兩個相加合并成一個元素。
因此，若逐差數組中有多于一個負數，則不行; 若無負數，則可以; 否則對惟一的負數作以上操作，若其能被刪掉或被合并成正數，則可以
這樣一來，時間復雜度可以降到 O(n)
白板的微信
TA貢獻1883條經驗 獲得超3個贊
可以在 O(n) 時間做到:
對每個相鄰的
[a, b]，判斷是否a >= b。這樣的數對破壞嚴格遞增性。如果這樣的數對超過一個，返回false。如果一個也沒有，返回true。如果1中只有一對
[a0, b0]，判斷 "移除a0或b0后是否還是遞增" 并返回
GCT1015
TA貢獻1827條經驗 獲得超4個贊
結果是對的，但是超過規定的時間了，有更好的方法嗎？
function almostIncreasingSequence(sequence) {
var iscan = false;
var is = true;
var temp
for(var i=0;i<sequence.length;i++){
is = true;
temp = sequence.slice(0,i).concat(sequence.slice(i+1));
for(var j=0;j+1<temp.length;j++){
if(temp[j] <= temp[j+1]){
is = false;
break;
}
}
if(is){
iscan=true;
break;
}
}
return iscan;
}時間復雜度為O(n)的方法
boolean almostIncreasingSequence(int[] sequence) {
if(sequence.length<=2){
return true;
}
//找出逆序的數的index
int count = 0;
int biggerIndex = 0;
int smallerIndex = 0;
boolean isHave = true;
for(int i=0;i+1<sequence.length;i++){
//如果找到2組逆序，直接返回false
if(count>1){
isHave = false;
}
if(sequence[i]>=sequence[i+1]){
count ++;
biggerIndex = i;
smallerIndex = i+1;
}
}
//分別判斷當移除2個數后剩下的數組是不是自增的
for(int i=0;i+2<sequence.length;i++){
int cur = i;
int next = i+1;
if(i==biggerIndex){
continue;
}
if(i+1==biggerIndex){
next = i+2;
}
if(sequence[cur]>=sequence[next]){
isHave = false;
}
}
if(isHave){
return isHave;
}else{
isHave = true;
}
for(int i=0;i+2<sequence.length;i++){
int cur = i;
int next = i+1;
if(i==smallerIndex){
continue;
}
if(i+1==smallerIndex){
next = i+2;
}
if(sequence[cur]>=sequence[next]){
isHave = false;
}
}
return isHave;
}
添加回答
舉報
0/150
提交
取消