java - 递归划分数组

Question

我需要获得一些所有可能的方法来将数组划分为小的子数组。我们可以将数组垂直和水平划分。我的算法效果很好，但是时间复杂度太差了。你能看看如何改进它吗？

参数

nStart - 子数组的第一行

nEnd - 子数组的最后一行

mStart, mEnd - 用于第二维(列)。

check() - 检查结束条件的函数

return - 划分数组的不同方式的数量。我们在函数检查返回 true 时除法。

public static long divide(int nStart, int nEnd, int mStart, int mEnd) {
    long result = 0;

    for(int i = 1; i < nEnd - nStart; i++) {
        if(check(nStart, nStart + i, mStart, mEnd) && check(nStart + i, nEnd, mStart, mEnd))
            result += divide(nStart, nStart + i, mStart, mEnd) * divide(nStart + i, nEnd, mStart, mEnd);
    }

    for(int i = 1; i < mEnd - mStart; i++) {
        if(check(nStart, nEnd, mStart, mStart + i) && check(nStart, nEnd, mStart + i, mEnd)) 
            result += divide(nStart, nEnd, mStart, mStart + i) * divide(nStart, nEnd, mStart + i, mEnd);
    }

    return (result == 0 ? 1 : result) % 1000000000; 
}

示例

输入

2 2 10 01

输出 2

输入

3 2 101 010

输出 5

我认为您需要了解 check() 函数的工作原理。当下一个子数组只有 1 或只有 0 时，我们停止划分。这是代码:

public static boolean check(int nStart, int nEnd, int mStart, int mEnd) {
    if((nEnd - nStart) + (mEnd - mStart) == 2) 
        return false;
    for(int i = mStart; i < mEnd; i++) {
        for(int j = nStart; j < nEnd; j++) {
            if(bar[i][j] != bar[mStart][nStart])
                return true;
        }
    }
    return false;
}

Answer 1

通过查看您的代码，我可以看到在递归的每个步骤中，您将二维数组分成两个数组，并进行一次水平或垂直切割。然后验证这两个部分是否满足检查方法定义的某些条件，如果满足，则将这两个部分放入递归中。当不能再继续递归时，你返回1。下面我假设你的算法总是产生你想要的结果。

恐怕此算法的有效优化在很大程度上取决于检查条件的作用。在微不足道的情况下，当问题分解为一个可能具有一般非递归解决方案的简单数学问题时，它总是会返回 true。有点复杂，但仍然可以有效解决的情况是条件只检查数组的形状，这意味着例如check(1,5,1,4) 将返回与 check(3,7,5,8) 相同的结果。

最复杂的当然是通用解决方案，其中检查条件可以是任何内容。在这种情况下，优化您的蛮力解决方案的方法不多，但我想到的一件事是为您的算法添加内存。您可以使用 java.awt.Rectangle 类(或创建您自己的类)来保存子数组的维度，然后使用 java.util.HashMap 来存储 furure 的 divide 方法的执行结果引用，如果使用相同的参数再次调用该方法。这将防止可能发生的重复工作。

因此您在类中将 haspmap 定义为静态变量:

static HashMap<Rectangle,Long> map = new HashMap<Rectangle,Long>();

然后在 divide-method 的开头添加以下代码:

Rectangle r = new Rectangle(nStart,mStart,nEnd,mEnd);
Long storedRes = map.get(r);
if (storedRes != null) {
    return storedRes;
}

然后您将方法的结尾更改为以下形式:

result = (result == 0 ? 1 : result) % 1000000000;
map.put(r, result);
return result;

这应该会提升您的算法的性能。

回到我之前的想法，如果检查条件足够简单，同样的优化可以更有效地完成。例如，如果您的检查条件只检查数组的形状，您只需要将其宽度和高度作为 map 的键，这将减小 map 的大小并成倍增加其中的正命中数.