java - 【算法题】给定int数组，移除不超过一个元素后，判断是否存在自增序列

Question

没什么思路啊，题目如下
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 be
almostIncreasingSequence(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 be
almostIncreasingSequence(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层循环，第一循环移除元素，第二层循环判断移除这个元素后是否有自增序列。

Answer 1

Berikan idea

Buat tatasusunan perbezaan demi perbezaan: Contohnya, a=[1,3,2,1], dan selepas perbezaan demi perbezaan, kita mendapat [2,-1,-1]

Apa yang dipanggil pemadaman elemen bermaksud mengalih keluar kepala atau ekor dalam tatasusunan perbezaan demi perbezaan, atau menambah dua elemen bersebelahan ke dalam satu elemen.

Oleh itu, jika terdapat lebih daripada satu nombor negatif dalam tatasusunan perbezaan, ia tidak akan berfungsi; jika tiada nombor negatif, ia akan berfungsi jika tidak, operasi di atas akan dilakukan pada satu-satunya nombor negatif boleh dipadamkan atau digabungkan menjadi nombor positif, ia akan berfungsi

Dengan cara ini, kerumitan masa boleh dikurangkan kepada O(n)

Answer 2

Boleh dilakukan pada O(n) masa:

1. Untuk setiap [a, b] bersebelahan, tentukan sama ada ia a >= b. Pasangan nombor sedemikian memusnahkan penambahan yang ketat. Jika terdapat lebih daripada satu pasangan sedemikian, pulangkan palsu. Jika tiada, kembalikan benar.

2. Jika terdapat hanya sepasang [a0, b0] dalam 1, tentukan "sama ada ia masih meningkat selepas mengalih keluar a0 atau b0" dan kembalikan

Answer 3

Hasilnya betul, tetapi ia melebihi masa yang ditetapkan. Adakah cara yang lebih baik?

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;
}

Kaedah dengan kerumitan masa 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;
}

Answer 4

Adakah ini mengira bilangan nombor terbalik?