找到最长的连续交替序列

Question

假设我们有一个数组 {1, 1, 2, 3, 6, 5, 5, 4, 6}

找到数组中最长的连续 odd/even 或 even/odd 子序列。

答案是 5：{1, 2, 3, 6, 5}

我的思路是求两个子序列

起始号码为奇数
起始号码为偶数

return两者的最大值

我写的代码找到最长的子序列，但不连续

public static int longestAlternativeSequence(int[] a, int n) {
    int maxOdd = 0; //Max subsequence starting with odd Number
    int maxEven = 0; //Max subsequence starting with even Number
    int odd = 0;
    int even = 0;
    
    for (int i = 0; i < n; i++) {
        if (odd == 0) { // first number has to be odd
            if (a[i] % 2 == 1) {
                odd = 1;
                maxOdd++;
            }
        }
        
        else {
            if (a[i] % 2 == 0) {
                odd = 0;
                maxOdd++;
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (even == 0) { //first number has to be even
            if (a[i] % 2 == 0) {
                even = 1;
                maxEven++;
            }
        }
        else {
            if (a[i] % 2 == 1) {
                even = 1;
                maxEven++;
            }
        }
    }
    return Math.max(maxOdd, maxEven);
}
public static void main(String[] args) {
    int a[] = {1, 1, 2, 3, 6, 5, 5, 4, 6};
    int n = a.length; 
    System.out.println(longestOddEven(a, n)); //returns 6
}

Answer 1

我测试了几个案例，希望这对你有用：

public static int longestAlternativeSequence(int[] a, int n){
    if (n == 0) return 0;

    boolean isOdd = a[0] % 2 == 1;
    int tempCount = 1;
    int res = 0;

    for (int i = 1; i < n; ++i){
        if ((isOdd && a[i] % 2 == 0) || (!isOdd && a[i] % 2 == 1)){
            ++tempCount;
            isOdd = a[i] % 2 == 1;
        }else{
            res = Math.max(tempCount, res);
            tempCount = 1;
        }
    }

    res = Math.max(tempCount, res);
    return res;
}

基本上我们这里有的是跟踪以前号码的状态（奇数或偶数）并将其与当前号码进行比较。如果情况属实，我们将继续使用临时计数器进行计数。如果不是，那么我们检查tempCount是否大于res，并重置tempCount。

如果数组为空，则 return 为零，否则它将 return 至少为一个，因为无论如何单个 odd 或 even 数字都符合这种情况。

最后，如果正确答案以数组的最后一个元素结束，那么最后一次检查无法到达 else 子句，这就是我们需要在循环后更新 res 的原因。

Answer 2

纯属娱乐。不喜欢就无视吧

static final Pattern ZERO_ONE_SEQUENCE = Pattern.compile("1?(01)*0?");

static int[] longestOddEvenSubsequence(int[] input) {
    String binaryString = Arrays.stream(input)
        .mapToObj(intValue -> Integer.toString(intValue & 1))
        .collect(Collectors.joining());
    return ZERO_ONE_SEQUENCE.matcher(binaryString).results()
        .map(m -> Arrays.copyOfRange(input, m.start(), m.end()))
        .max(Comparator.comparing(intArray -> intArray.length))
        .get();
}

和

System.out.println(Arrays.toString(
    longestOddEvenSubsequence(new int[] {1, 1, 2, 3, 6, 5, 5, 4, 6})));
// -> [1, 2, 3, 6, 5]

Answer 3

这里这个怎么样？它使用 recursion 和 memoization。这是一种不同的方法，对于这项任务来说可能有点矫枉过正，但它或多或少与 for-loop-solution 相同。这实际上取决于您想用它做什么，以及您以后是否想进一步扩展它。

我还在下面添加了一些测试用例，包括负整数。

public static int maxEvenOddContinousSequence(int[] a) {
    final int numElements = a.length;
    int result;
    if (numElements == 0) {
        result = 0;
    } else if (numElements == 1) {
        result = 1;
    } else {
        result = findEvenOddContinousSubsequence(a, numElements, 0, a[0] % 2 == 0, 0, 0);
    }
    return result;
}

private static int findEvenOddContinousSubsequence(int[] a, int numElements, int index, boolean isEven, int currentLongestSequence, int longestSequence) {
    if (index < numElements) {
        final int currentElement = Math.abs(a[index]);
        final int currentElementMod2 = currentElement % 2;
        if (currentElementMod2 == (isEven ? 0 : 1)) {
            return findEvenOddContinousSubsequence(a, numElements, ++index, !isEven, ++currentLongestSequence, longestSequence);
        } else {
            return findEvenOddContinousSubsequence(a, numElements, index, currentElementMod2 == 0, 0, Math.max(currentLongestSequence, longestSequence));
        }
    }
    return Math.max(currentLongestSequence, longestSequence);
}

public static void main(String[] args) {
    int a[] = {};
    int b[] = {1};
    int c[] = {1, 2};
    int d[] = {1, 1, 2, 3, 6, 5};
    int e[] = {1, 1, 3, 3, 6, 5, 2, 5, 2, 4, 6};
    int f[] = {0, -1, -3, -6, -5, -2};
    System.out.println("A:" + maxEvenOddContinousSequence(a)); // expected: 0 => []
    System.out.println("B:" + maxEvenOddContinousSequence(b)); // expected: 1 => [1]
    System.out.println("C:" + maxEvenOddContinousSequence(c)); // expected: 2 => [1, 2]
    System.out.println("D:" + maxEvenOddContinousSequence(d)); // expected: 5 => [1, 2, 3, 6, 5]
    System.out.println("E:" + maxEvenOddContinousSequence(e)); // expected: 6 => [3, 6, 5, 2, 5, 2]
    System.out.println("F:" + maxEvenOddContinousSequence(f)); // expected: 4 => [-3, -6, -5, -2]
}

输出： A:0 B:1 C:2 D:5 E:6 F:4

Answer 4

此函数将return 启动所需间隔的倒数第二个索引。它基于检查当前和以前的简单想法。请注意，i <= arr.length 条件，因为它处理间隔运行到结束的情况。此案例已在 if.

中检查

static int[] contAlternating(int[] arr) {
            if (arr == null || arr.length == 0)
                return null;
            if (arr.length == 1)
                return new int[] { 0, 1 };
            int lastStart = 0;
            int maxStart = 0;
            int maxEnd = 1;
            for (int i = 1; i <= arr.length; i++) {
                if ((i < arr.length)
                        && ((arr[i] % 2 == 0 && arr[i - 1] % 2 == 1) || (arr[i] % 2 == 1 && arr[i - 1] % 2 == 0))) {
                    continue;
                }
                if (i - lastStart > maxEnd - maxStart) {
                    maxStart = lastStart;
                    maxEnd = i;
                }
                lastStart = i;
            }
            return new int[] { maxStart, maxEnd };
        }

找到最长的连续交替序列

Find the longest contiguous alternating sequence

java

arrays

algorithm

subsequence