递归分割数组

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()功能是如何工作的。当下一个子阵列只有一个或只有零时，我们停止分割。这里是代码：

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.下面我假设您的算法总是产生您想要的结果。

恐怕这种算法的有效优化高度依赖于检查条件的作用。在这个微不足道的情况下，当问题坍缩成一个简单的数学问题时，它总能回答真实的问题，这个问题可以有一个通用的非递归解决方案。稍微复杂一些，但仍然可以有效解决的情况是条件只会检查数组的形状，也就是说，检查（1,5,1,4）将返回与检查（3,7,5,8）相同的结果。

最复杂的当然是一个通用的解决方案，其中检查条件可以是任何东西。在这种情况下，优化你的强力解决方案并没有太多的工作可做，但我想到的一件事就是给你添加一个内存算法。你可以使用java.awt。Rectangle类（或创建自己的类），它将保存子数组的维度，然后使用java.util.HashMap存储furure引用的divide-method的执行结果，如果再次调用该方法具有相同的参数。这将防止重复工作，将propaply发生。

所以你定义haspmap在你类的静态变量：

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

然后添加以下代码分裂法的开头：

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; 

这应该会为您带来性能提升r算法。如果检查条件足够简单，那么可以更有效地进行相同的优化，以回到我以前的工作。例如，如果您的检查条件仅检查数组的形状，则只需将其宽度和高度作为地图的关键点，这将缩小地图的大小并将其中的正面点击次数增加多倍。