HackerRank -拾取数

Question

我对编程很陌生，这是我在这里的第一个问题。

https://www.hackerrank.com/challenges/picking-numbers/problem?isFullScreen=true已经连续三天尝试解决这个挑战，但是仍然有3/10的测试用例失败。

在这里，我使用的算法：

1. 对主数组中的每个元素创建一个子数组，其中所有元素都等于或不小于1
2. ，由此检查子数组的数目(等于第一个数组中的元素数)，这意味着每个元素等于或不小于1
3. ，找到最长的有效子数组并返回其大小为

的子数组。

以下是解决方案的代码：

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'pickingNumbers' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts INTEGER_ARRAY a as parameter.
     */

    public static int pickingNumbers(List<Integer> a) {
        int maxLength = 0;
        boolean isValidArray = false;
        List<Integer> subarray = new ArrayList<Integer>();

        for (int i = 0; i < a.size(); i++) {
            subarray = findValidSubarray(a, a.get(i));
            isValidArray = arrayValidityCheck(subarray);
            if ((isValidArray) && (subarray.size() > maxLength)) {
                maxLength = subarray.size();
            }
        }
        return maxLength;
    }

    private static List<Integer> findValidSubarray(List<Integer> array, Integer integer) {
        List<Integer> subarray = new ArrayList<Integer>();

        for (int elem : array) {
            if ((elem == integer) || (elem + 1 == integer) || (elem == integer + 1)) {
                subarray.add(elem);
            }
        }
        return subarray;
    }
//check that all elements are equal or not more or less than 1 to each other
    private static boolean arrayValidityCheck(List<Integer> subarray) {
        boolean isValid = false;

        for (int i = 0; i < subarray.size(); i++) {
            for (int j = 0; j < subarray.size(); j++) {
                if ((subarray.get(i) == subarray.get(j)) || (subarray.get(i) + 1 == subarray.get(j)) || (subarray.get(i) == subarray.get(j) + 1)) {
                    isValid = true;
                } else {
                    isValid = false;
                    break;
                }
            }
            if (!isValid) {
                break;
            }
        }
        return isValid;
    }
}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
        int n = Integer.parseInt(firstMultipleInput[0]);

        List<Integer> a = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                .map(Integer::parseInt)
                .collect(toList());
        bufferedReader.close();

        int result = Result.pickingNumbers(a);
        System.out.println(result);
    }
}

正在失败的测试用例数据示例：

100

和

14 18 17 10 9 20 4 19 19 19 15 15 17 6 5 15 12 18 20 20 20 12 12 16 20 20 20 12 14 18 20 20 20 12 12 16 20 20 20 12 15 16 20 20 12 12 16 18 20 20 20 12 12 5 10 10 11 18 5 15 4 10 10 11 18 20 13 4 18 14 3 19 9 9 4 20 10 19 14 2 2 5 13

有效答案：

15

我的答案是：

13

我想不出虫子在哪里了。你能帮帮我吗？

PS:我知道这个算法不是最优的。任何优化提示将不胜感激。

Answer 1

编辑:正如注释中所指出的，只检查其他元素是否大于检查中的第一个元素，就足以进行一种类型的检查。答案已相应修改

您的问题是，当您构建您的子数组时，您允许其中的数字比您开始使用的第一个元素高一个和低一个。然后，您将尝试通过重新验证生成的数组来清理您的结果，但是这不会解决使用您的方法不会生成任何可能的有效子数组的问题。

我修复您的代码的建议是：

1. 修改您的findValidSubarray方法，以便只允许其中更高的元素。(当较低的数字作为迭代的起始元素时，将在其他迭代中处理较低的数字的情况)

1. 移除arrayValidityCheck，因为不再需要这个，因为上面的这些只会直接生成有效的子数组。

改进的findValidSubarray方法：

private static List<Integer> findValidSubarray(final List<Integer> array, final Integer integer) {
    final List<Integer> subarray = new ArrayList<Integer>();
    for (final int elem : array) {
         if ((elem == integer) || (elem + 1 == integer)) {
             subarray.add(elem);
         }
    }
    return subarray;
}

调用该方法：

public static int pickingNumbers(final List<Integer> a) {
    int maxLength = 0;
    List<Integer> subarray = new ArrayList<Integer>();

    for (int i = 0; i < a.size(); i++) {
        subarray = findValidSubarray(a, a.get(i));
        if ((subarray.size() > maxLength)) {
            maxLength = subarray.size();
        }
    }
    return maxLength;
}