算法在hackerrank上只有一个测试用例失败

Question

我尝试了https://www.hackerrank.com/challenges/poisonous-plants的黑客排名问题，并提出了以下算法。我需要一些帮助，因为我的解决方案是失败的只有2个测试用例，他们是大数据集，所以难以调试。我包含了测试用例的链接http://ideone.com/B2WWaH给出的答案是204，但根据暴力破解方法，正确答案是16。简而言之，问题是给定一个非空的正整数数组，在每次迭代中，数组元素大于它的前一个被删除。在多少次迭代之后将不会删除。

花园里有N种植物。每一种植物都被添加了一定量的农药。每过一天，如果任何一株植物比它左边的那株植物含有更多的农药，因为它比左边的那株弱，它就会死亡。你会得到每株植物中农药的初始值。打印没有植物死亡的天数，即没有植物的农药含量超过其左侧植物的时间。

输入格式

输入由整数N组成，下一行由N个整数组成，描述数组p，其中p [i]表示植物i中的农药量。

• 1≤N≤100000
• 0≤P[我]≤10 <一口> 9

输出格式

输出一个等于没有植物死亡的天数的值。

我做了一些观察

(1)第一个植物将永远存活，因为左边没有植物。

(2)最后最长递减子序列从第一个植株开始存活。

(3)我们只需要找出这些子序列元素之间的植物需要多少天死亡。

(4)提出了跟踪植物死亡日期的算法。

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class No {
    public static void main(String[] args) throws FileNotFoundException {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        int a = 0 , no = 0 ;
        Scanner scno = new Scanner(new File("D:\no.txt"));
        a = scno.nextInt();
        int[] arr = new int[a];


        int n[] = new int[a]; int n1 = 0;
        for ( int i = 0 ; i < arr.length ; i++ )
        {
            arr[i] = scno.nextInt();
            if ( 0 != i )
            {
                if ( arr[i] > arr[i-1] )
                {
                    n[1] = arr[i];
                    no = Math.max(no, 1);
                }
                else if ( arr[i] > arr[a] )
                {
                    for ( int j = no ; j >= 0 ; j-- )
                    {
                        if ( 0 == j )
                        {
                            n[++no] = arr[i];
                            break;
                        }
                        if ( arr[i] > n[j] )
                        {
                            n[j] = arr[i];
                            break;
                        }                       
                    }
                }
                else
                {
                    a = i;
                    n1 = Math.max(n1, no);
                    no = 0;
                    Arrays.fill(n, 0);
                }
            }
            else
            {
                a = i;
            }
        }
        System.out.println(Math.max(n1, no));   
    }
}

Answer 1

首先，你必须遵循一些步骤来解决任何问题。在这种类型的问题中，您必须:

1. 首先读取所有数据，这意味着一个独立的循环读取所有工厂数据。
2. 你应用你的进化模型，如果有一个。这是另一个独立的循环。你所做的假设是不充分的。我不知道是否有可能一次得到它，如果你先写一个有效的解决方案，你会很容易定义这些特征。肯定有效的解决方案是迭代并杀死植物。从右边开始迭代，杀死满足死亡条件的植物。如此重复，直到一个循环没有杀死任何植物。这样的天数是你循环的次数减去1(最后一次没有杀死任何植物)。ArrayList会让你的生活变得简单。

简而言之，您可以将数据数组声明为

    ArraList<int> arr = new ArraList(a)

填充为(读取

的大小a后)

    for ( int i = 0 ; i < a ; i++ ) arr.add(scno.nextInt());

并使用像这样的子例程来完成这项工作(这只是一个指示，我没有测试它)

    private static int numberDaysNoD(ArraList<int> arr){
        int nDays = 0;
        boolean haveKilled = true;
        while(haveKilled){
            haveKilled = false;
            for(int i = arr.size()-1; i>0; i--){
                if(arr.get(i)>arr.get(i-1)){
                    arr.remove(i);
                    haveKilled = true;
                }
            }
            nDays++;
        }
        return nDays--
    }

第二，在你的问题陈述中遗漏了一件事。植物体内的农药含量会进化吗?什么是进化模型?或者根本没有进化，每天我们只是杀死那些比左邻居拥有更多的人(如果一个人死了，左邻居就会自动改变)，然后等待第二天重复?