java - 算法仅针对 hackerrank 的一个测试用例失败

Question

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

问题

花园里有 N 株植物。这些植物中的每一种都添加了一定量的杀虫剂。每天过后，如果任何一株植物的杀虫剂比它左边的植物多，比左边的植物弱，它就会死去。您将获得每种植物中农药的初始值。打印没有植物死亡的天数，即没有植物的杀虫剂含量高于其左侧植物的时间。

输入格式

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

约束

• 1≤N≤100000
• 0≤P[i]≤10⁹

输出格式

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

我做了一些观察

(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. 如果有的话，你应用你的进化模型。这是另一个独立的循环。 你所做的假设是不够的。我不知道是否有可能一次获得它，如果您首先编写一个有效的解决方案，您将很容易定义这些特征。肯定有效的解决方案是迭代并杀死植物。从右边开始迭代，杀死满足垂死条件的植物。并重复直到一个循环不会杀死任何植物。那些天数是你做的循环次数减去一(最后一个没有杀死任何植物)。 ArrayList 将使您的生活变得简单。

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

    ArraList<int> arr = new ArraList(a)

填充为(读取 vector 的大小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--
    }

其次，您的问题陈述中缺少一件事。植物中的杀虫剂水平会发生变化吗？什么是进化模型？或者根本就没有进化，每天，我们只是杀死那些比他们的左邻居多的人(如果有人死了，这会自动改变左邻居)并等待第二天重复？