java - 最长的蛇序列

Question

问题:一组由空格分隔的数字作为输入传递。程序必须打印数字中存在的最大蛇序列。蛇序列由相邻的数字组成，对于每个数字，右侧或左侧的数字是其值的 +1 或 -1。如果可能存在最大长度的多个蛇序列，则打印以自然输入顺序出现的蛇序列。

输入/输出 1 示例:

输入:

5 6 7 9 8 8

输出:

5 6 7 8 9 8

8 9 8 7 6 5

示例输入/输出 2:

输入:

9 8 7 5 3 0 1 -2 -3 1 2

输出:

3 2 1 0 1

void doPermute(int[] in, StringBuffer out, boolean[] used, int length, int level, StringBuffer max) {
    if (level == length) {
        int count = 0;
        for (int i = 1; i < out.length(); i++) {
            if (Math.abs(Character.getNumericValue(out.charAt(i)) - Character.getNumericValue(out.charAt(i - 1))) != 1) {
                //System.out.println(Character.getNumericValue(i) - Character.getNumericValue(i - 1) + "  " + i + "   yes");
                count++;
                break;
            }
        }
        if (count == 0) {
            max.append(out + " ");

        }

        return;
    }
    for (int i = 0; i < length; ++i) {
        if (used[i]) {
            continue;
        }
        out.append(in[i]);
        used[i] = true;
        doPermute(in, out, used, length, level + 1, max);
        used[i] = false;
        out.setLength(out.length() - 1);
    }
}

由于我使用 StringBuffer，我的代码通过了包含正值的测试用例(第一个测试用例)，但在包含负值的测试用例(第二个测试用例)中失败了。

更新:-我用 Integer[] 替换了 stringbuffer 并做了一些更改。它对于长度为 8 或 9 的较小输入来说效果很好。如何使其能够快速地处理长度为 13 的较大输入15？

Answer 1

您是否尝试过使用整数数组来完成该过程？

Scanner sc = new Scanner(System.in);
String s = sc.nextLine(); //The numbers entered in string format separated by spaces
String ss = s.split(" "); //Numbers separated by space will be put as individual numbers in a String array but each number is still in string format
int l = ss.length, i = 0;
int[] n = new int[l]; //The integer array which will store the values
for(i = 0; i < l; i++)
{
    n[i] = Integer.parseInt(ss[i]);  //Has integers now instead of string numbers
}

可能会创建一些额外的数组，但重复调用 Character.getNumericValue() 函数也会降低效率。也可能会解决您的 StringBuffer 问题。

但是 SkillRack 无论如何都很烦人。