使用分而治之检查一个数组是否等于另一个数组向后

Question

我一直在尝试制作一个简单的函数来检查 array 是否与另一个 array reversed.

例如，比较 [0, 1, 2] 和 [2, 1, 0] 会 return true，但是比较 [0, 1, 2] 和 [2, 1, 1] 会 return false.

我也在尝试分治法，递归使用函数

这是我编写的代码，但它没有按预期工作，returning false 应该 return true:

public class ReverseCheck {

    // Check if an array is the reverse of another array
    // Use divide and conquer
    public static boolean isReverse(int[] a, int[] b) {
        if (a.length != b.length) {
            return false;
        }
        return isReverse(a, b, 0, a.length - 1);
    }

    private static boolean isReverse(int[] a, int[] b, int start, int end) {
        if (start == end) {
            return a[start] == b[end];
        }
        int mid = (start + end) / 2;
        return isReverse(a, b, start, mid) && isReverse(a, b, mid + 1, end);
    }

    public static void main (String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6};
        int[] b = {6, 5, 4, 3, 2, 1};
        int[] c = {1, 2, 3, 4, 5, 6, 7};
        int[] d = {6, 5, 5, 3, 2, 1};
        System.out.println(isReverse(a, b)); // Should return true, returns false
        System.out.println(isReverse(a, c)); // Should return false, returns false
        System.out.println(isReverse(a, d)); // Should return false, returns false
    }

}

Answer 1

您的解决方案中存在几个问题：

基本案例在逻辑上存在缺陷。 return 值表示索引相等时比较a[start] == b[end] 的结果。这不是验证一个 array 是否是另一个的 reversed copy 的正确方法。让我们考虑 两个数组 a = [1, 2, 3] 和 b = [3, 2, 1]。我们必须检查 a[0] == b[2]、a[1] == b[1] 和 a[2] == b[0]。如您所见，索引相等的情况 仅发生一次 并且仅当长度为奇数时，如果长度为偶数一对元素将不同。
第二个问题是您采用的总体方法。对于这个问题，我们必须检查所有的值对。分而治之的方法在这里是没有用的，因为我们不能减少操作量，在最坏的情况下每对值都需要比较。

我建议通过回溯解决这个问题，方法是在每次方法调用时将两个数组的索引简单地移动 1， 而不使用除法并征服，因为我们无法从中受益。

首先，让我们修正递归的基本情况。

递归应在两种情况下终止：当对中的值不匹配并且已达到最后一个有效索引时。

第一种情况的条件，当对应于当前索引的值不相等时，将看起来是：

if (a[start] != b[end]) return false;

第二部分可能会这样写：

if (start == a.length - 1) return a[start] == b[end];

或

if (start == a.length - 1) return true;

两者的含义几乎相同——我们已经成功地比较了所有的值对（或者正在比较最后一对值）。第一个版本稍微好一点，省了一个方法调用。

在递归情况中，我们只是通过传递 start 递增 1 和 end 递减来调用方法1.

private static boolean isReverse(int[] a, int[] b, int start, int end) {
    if (start == a.length - 1) {
        return a[start] == b[end];
    }
    if (a[start] != b[end]) {
        return false;
    }

    return isReverse(a, b, start + 1, end - 1);
}

main()

public static void main(String[] args) {
    int[] a = {1, 2, 3, 4, 5, 6};
    int[] b = {6, 5, 4, 3, 2, 1};
    int[] c = {1, 2, 3, 4, 5, 6, 7};
    int[] d = {6, 5, 5, 3, 2, 1};
    System.out.println(isReverse(a, b)); // Should return true, returns false
    System.out.println(isReverse(a, c)); // Should return false, returns false
    System.out.println(isReverse(a, d)); // Should return false, returns false
}

输出

true
false
false

修复初始分而治之版本

如我之前所说，问题出在 基本情况 中。而不是比较相同位置的元素 a[start] == b[end] （当 start 等于 end 时就没有意义了），我们需要调整 end 索引：

    if (start == end) {
        return a[start] == b[(b.length - 1) - end];
    }

这是唯一需要应用于问题中列出的原始代码的更改。

使用分而治之检查一个数组是否等于另一个数组向后

Checking whether an Array equals another Array Backwards using divide and conquer

java

arrays

algorithm

recursion

divide-and-conquer

修复初始分而治之版本