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

Question

我一直在尝试创建一个简单的函数来检查数组是否与另一个数组反转相同。

例如，比较 [0, 1, 2] 和 [2, 1, 0] 将返回 true，但比较 [0, 1, 2]< /code> 和 [2, 1, 1] 将返回 false。

我还尝试使用分而治之的方法，递归地使用函数。

这是我编写的代码，但它没有按预期工作，在应该返回 true 时返回 false：

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

解决方案中有几个问题：

• 基本案例在其中存在逻辑缺陷。返回值代表比较a [start] == b [end]时的结果。这不是验证一个 array 的正确方法是另一个反向复制。让我们考虑两个数组 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和结束减少来调用该方法通过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> start等于end，它不会使感觉），我们需要调整end索引：

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

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