如何检查序列是否是交替的？

Question

我需要编写一个程序来读取整数序列，并确定序列是否是交替的。交替序列是指根据基数的变化，每一个数字都应该大于或小于它之前的数字的序列。例如，15 4 8 2 10是交替的.

我写了这个程序，但我不确定它是100%正确的。

import java.util.Scanner;

  public class alternating {

 public static void main(String[] args) {
    // TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
int cases = scan.nextInt();
for (int testcase = 0; testcase < cases; testcase++) {
    int n = scan.nextInt();
    int[] sequence = new int[n];
    for (int i = 0; i < sequence.length; i++)
        sequence[i] = scan.nextInt();
    if (alternating(sequence))
        System.out.println("alternating");
    else
        System.out.println("not alternating");
}

  }

  public static boolean alternating(int[] sequence) {
   for (int i = 0; i < sequence.length - 2; i++) {
    if (sequence[i] <= sequence[i + 1]) {
        if (sequence[i + 1] <= sequence[i + 2])
            return false;
    } else {
        if (sequence[i] >= sequence[i + 1])
            if (sequence[i + 1] >= sequence[i + 2])
                return false;

    }

}
return true;
     }

      }

Answer 1

对于少于3项的短序列，这是不正确的。该方法不正确地返回这些示例序列的true：

• 空序列
• 单例列表(一项)
• 具有两个相等项的序列

对于前两种情况，您甚至可能希望抛出IllegalArgumentException，因为可以说，在具有0或1项的列表中测试替换没有多大意义，但我认为返回false是合理的。

可以通过在方法开始时添加以下条件来做到这一点：

    if (sequence.length < 2) {
        return false;
    }
    if (sequence.length == 2) {
        return sequence[0] != sequence[1];
    }

但实际上，我会简化for循环的主体，如下所示：

    if (sequence.length < 2) {
        return false;
    }
    int prevCompare = Integer.compare(sequence[0], sequence[1]);
    if (prevCompare == 0) {
        return false;
    }
    for (int i = 1; i < sequence.length - 1; ++i) {
        int compare = Integer.compare(sequence[i], sequence[i + 1]);
        if (prevCompare != -compare) {
            return false;
        }
        prevCompare = compare;
    }
    return true;

为了验证实现，我建议添加一些单元测试，例如：

@Test
public void testEmptyList_Is_NotAlternating() {
    assertFalse(alternating(new int[0]));
}

@Test
public void testSingletonList_Is_NotAlternating() {
    assertFalse(alternating(new int[]{1}));
}

@Test
public void test2Items_Increasing_Is_Alternating() {
    assertTrue(alternating(new int[]{1, 2}));
}

@Test
public void test2Items_Decreasing_Is_Alternating() {
    assertTrue(alternating(new int[]{3, 2}));
}

@Test
public void test2Items_Same_Is_NotAlternating() {
    assertFalse(alternating(new int[]{3, 3}));
}

@Test
public void test3Items_Same_Is_NotAlternating() {
    assertFalse(alternating(new int[]{3, 3, 3}));
}

@Test
public void test4Items_Same_Is_NotAlternating() {
    assertFalse(alternating(new int[]{3, 3, 3, 3}));
}

@Test
public void test3Items_Increasing_Is_NotAlternating() {
    assertFalse(alternating(new int[]{3, 4, 5}));
}

@Test
public void test4Items_Increasing_Is_NotAlternating() {
    assertFalse(alternating(new int[]{3, 4, 5, 6}));
}

@Test
public void test3Items_Decreasing_Is_NotAlternating() {
    assertFalse(alternating(new int[]{43, 34, 25}));
}

@Test
public void test4Items_Decreasing_Is_NotAlternating() {
    assertFalse(alternating(new int[]{43, 34, 25, 16}));
}

@Test
public void test4Items_AlternatingThenMonotonic_Is_NotAlternating() {
    assertFalse(alternating(new int[]{43, 34, 35, 16, 16, 16}));
}

@Test
public void test4Items_Alternating_Is_Alternating() {
    assertTrue(alternating(new int[]{43, 34, 35, 16}));
}