几乎递增序列编码问题

Question

我正试图解决一个编码问题。问题如下：

boolean almostIncreasingSequence(int[] sequence) {
    
    int count =0;
    
    for(int i =0; i < sequence.length; i++){
        
        if (sequence[i] <= sequence[i-1]){
            count++;
        }
        
        if(count>1){
            
            return false;
        }
        
        if(sequence[i] <= sequence[i-2] && sequence[i+1] <= sequence[i-1]){ 
            return false;
        }
    }
    
    return true;
}

这是以下错误：

测试1的执行错误：您的程序有一个运行时错误。

任何帮助都将不胜感激。这似乎是个小问题，但我解决不了。

Answer 1

当严格升序条件没有实现时，一个实现可以基于只移除1个元素。

public class TestAlmostIncreasingSequence {

    public static boolean almostIncreasingSequence(int[] sequence) 
    {
        if(sequence==null) return false;
        //mandatory to remove just 1 element, if no one(or more) removed then false
        boolean flag_removed=false;
        for(int i=1, prev=sequence[0];i<sequence.length;i++)
        {
            if(prev>=sequence[i] && flag_removed==false)
            {
                //mark removed 
                flag_removed=true;
            }
            //if element was removed then false
            else if(prev>=sequence[i] && flag_removed==true)
            {
                return false;
            }
            else
            {
                //change only if element removed is not the current
                //comparisons will not be done with removed element
                prev=sequence[i];
            }
            //System.out.println(prev);
        }
        //could have a strictly increased arr by default which will return false [1,2,3]
        return flag_removed;
    }
    
    public static void main(String[] args) 
    {
        //only for printing purpose
        String arr="";
        
        int s1[] = {1,2,3,1};
        arr=Arrays.stream(s1).mapToObj(t->String.valueOf(t)).
                collect(Collectors.joining(",","[","]"));
        System.out.println(arr+"\n"+almostIncreasingSequence(s1)+"\n");
        
        int s2[] = {1,2,3};
        arr=Arrays.stream(s2).mapToObj(t->String.valueOf(t)).
                collect(Collectors.joining(",","[","]"));
        System.out.println(arr+"\n"+almostIncreasingSequence(s2)+"\n");
        
        int s3[] = {1,2,3,1,2};
        arr=Arrays.stream(s3).mapToObj(t->String.valueOf(t)).
                collect(Collectors.joining(",","[","]"));
        System.out.println(arr+"\n"+almostIncreasingSequence(s3)+"\n");
        
        int s4[] = {1};
        arr=Arrays.stream(s4).mapToObj(t->String.valueOf(t)).
                collect(Collectors.joining(",","[","]"));
        System.out.println(arr+"\n"+almostIncreasingSequence(s4)+"\n");
        
        int s5[] = {1,1};
        arr=Arrays.stream(s5).mapToObj(t->String.valueOf(t)).
                collect(Collectors.joining(",","[","]"));
        System.out.println(arr+"\n"+almostIncreasingSequence(s5)+"\n");
        
        int s6[] = null;
        arr="null";
        System.out.println(arr+"\n"+almostIncreasingSequence(s6)+"\n");

    }
}

输出

[1,2,3,1]
true

[1,2,3]
false

[1,2,3,1,2]
false

[1]
false

[1,1]
true

null
false

注意：当实现的结果是错误的[1,5,2,3]时，只需再更新一个带有删除元素的分支=前一个（不是当前元素）并检查两个分支（一个true表示true）

这应该能解决这个问题

//method name is misguided, removePrev is better 
public static boolean removeCurrent(int[] sequence) 
    {
        if(sequence==null) return false;
        //mandatory to remove just 1 element, if no one remove then false
        boolean flag_removed=false;
        for(int i=1, prev=sequence[0];i<sequence.length;i++)
        {
            if(prev>=sequence[i] && flag_removed==false)
            {
                //mark removed 
                flag_removed=true;
            }
            //if element was removed then false
            else if(prev>=sequence[i] && flag_removed==true)
            {
                return false;
            }
            //compared element will be the current one
            prev=sequence[i];
            
            //System.out.println(prev);
        }
        //could have a strictly increased arr by default which will return false [1,2,3]
        return flag_removed;
    }

并使用

int s1[] = {1,5,2,3};
arr=Arrays.stream(s1).mapToObj(t->String.valueOf(t)).
            collect(Collectors.joining(",","[","]"));
boolean result= (almostIncreasingSequence(s1)==false) ? removeCurrent(s1) : true;
System.out.println(arr+"\n"+result +"\n");

输出

[1,5,2,3]
true (from removeCurrent_branch)

似乎还有一种情况是错误的[5,6,3,4]，意味着需要查看元素[i-2]（仅在remove元素之后）是否大于current和上一个分支上的“prev”。

6>3移除6（prev=3,3<4但[5>4或5>3]所以为false）

public static boolean removeCurrent(int[] sequence) 
{
    if(sequence==null) return false;
    //mandatory to remove just 1 element, if no one remove then false
    boolean flag_removed=false;
    for(int i=1, prev=sequence[0], twoprev=Integer.MIN_VALUE;i<sequence.length;i++)
    {
        if(prev>=sequence[i] && flag_removed==false)
        {
            //mark removed 
            flag_removed=true;
            if(i>=2) twoprev=sequence[i-2];
        }
        //if element was removed then false
        else if(prev>=sequence[i] && flag_removed==true)
        {
            return false;
        }
        else if(twoprev>=sequence[i] || twoprev>=prev)
        {
            return false;
        }
            
        //compared element will be the current one
        prev=sequence[i];
        
        //System.out.println(prev);
    }
    //could have a strictly increased arr by default which will return false [1,2,3]
    return flag_removed;
}

输出

[5,6,3,4]
false

现在，在我看来，所有的案件似乎都涵盖了。

强力也可以生成一个解决方案，但不是最优的。（使用循环移除一个元素，对结果排序并与基进行比较）

public class TestInc {

    public static void main(String[] args) 
    {
        int s1[] = {1,1,2,3};
        System.out.println(checkInc(s1));
    }
    
    public static boolean checkInc(int[] arr)
    {
        if(arr==null || arr.length==1) return false;
        
        List<Integer> lst = Arrays.stream(arr).boxed().collect(Collectors.toList());
        //remove this check if requirement is other(or return true)
        if(checkIfAlreadySortedAsc(lst))
        {
            return false;
        }
        for(int i=0;i<lst.size();i++)
        {
            List<Integer> auxLst = new ArrayList<Integer>(lst);
            auxLst.remove(i);
            List<Integer> sorted = new ArrayList<Integer>(auxLst);
            sorted = sorted.stream().distinct().sorted().collect(Collectors.toList());
            
            if(auxLst.equals(sorted))
            {
            //  System.out.println("=");
                return true;
            }
            else
            {
            //  System.out.println("!=");
            }
        }
        return false;
    }
    //any ascending sorted list will be the same type if remove one element
    //but as requirement on this case will return false
    //(or don't use method in want other)
    public static boolean checkIfAlreadySortedAsc(List<Integer> lst)
    {
        List<Integer> auxLst = new ArrayList<Integer>(lst);
        auxLst = auxLst.stream().distinct().sorted().collect(Collectors.toList());
        if(auxLst.equals(lst))
        {
            return true;
        }
        return false;
    }
}

输出

[1,1,2,3]
true