在java中使用递归函数实现四叉树，用于计算压缩数字

Question

我面对"java.lang.StackOverflowError"；，同时执行递归方法。

基本上，我正在解决四元压缩算法的问题。

问题是

在Solution类中，有一个solution方法，然后您将获得int[][] arr

返回int[] answer，放入0和1的编号

所有元素都是0或1

这个输入数据是二维数组，您必须进行四叉树压缩

如果一个四边形中的元素相同，请合并这些元素。那么，你当然只数1

example 1)
1100
1000
1001
1111
11|00
10|00
--+--
10|01
11|11
11|0
10|
--+--
10|01
11|11

第三个不能再进行四元压缩

(如果有更多，它将被压缩得更像这样。(在此处输入图像描述

0的数字是4，1是9。因此，返回int[] arr = [4,9]。

下面是我的代码。我想做的是，每当有不同的元素时，我都会使用递归来拆分arr。但如果所有元素都相同，则传递for循环，然后使dupl arr的元素为true，除了一个元素。

我不知道stackoverflow是在哪里长大的。

class Solution {
int[][] arr;
boolean[][] dupl;
public int[] solution(int[][] arr) {
this.arr = arr;
this.dupl = new boolean[arr.length][arr[0].length];
int[] answer = new int[2];
recurse(0, arr.length, 0, arr.length);

for(int i = 0; i < dupl.length; i++) {
for(int j = 0; j < dupl[0].length; j++) {
if(dupl[i][j] == true) continue;
if(arr[i][j] == 0) ++answer[0];
else if(arr[i][j] == 1) ++answer[1];
}
}

return answer;
}

private void recurse(int rowStart, int rowEnd, int colStart, int colEnd) {
if(rowStart == rowEnd || colStart == colEnd) return;

int target = arr[rowStart][colStart];
for(int r = rowStart; r < rowEnd; ++r) {
for(int c = colStart; c < colEnd; ++c) {
if(target != arr[r][c]) {
recurse(rowStart, rowEnd/2, colStart, colEnd/2);
recurse(rowStart, rowEnd/2, colEnd/2, colEnd);
recurse(rowEnd/2, rowEnd, colStart, colEnd/2);
recurse(rowEnd/2, rowEnd, colEnd/2, colEnd);
break;
}
target = arr[r][c];
}
}

for(int r = rowStart; r < rowEnd; ++r) {
for(int c = colStart; c < colEnd; ++c) {
dupl[r][c] = true;
}
}
dupl[rowStart][colStart]=false;
}
}

以下是测试用例

input = [[1, 1, 0, 0], [1, 0, 0, 0], [1, 0, 0, 1], [1, 1, 1, 1]]
output = [4, 9]
input = [[1, 1, 1, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 1, 1, 1, 1], [0, 1, 0, 0, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 0, 0, 1], [0, 0, 0, 0, 1, 1, 1, 1]]
output = [10, 15]

Answer 1

我认为这是一种Divide and Conquer problem

所以，下面的部分是错误的，因为在除法时，你必须从上一个开始和结束之间的中心(平均数(开始

recurse(rowStart, rowEnd/2, colStart, colEnd/2);将是recurse(rowStart, (rowStart+rowEnd)/2, colStart, (colStart+colEnd)/2);

recurse(rowStart, rowEnd/2, colStart, colEnd/2);
recurse(rowStart, rowEnd/2, colEnd/2, colEnd);
recurse(rowEnd/2, rowEnd, colStart, colEnd/2);
recurse(rowEnd/2, rowEnd, colEnd/2, colEnd);

答案是：

class Solution {
int[][] arr;
boolean[][] dupl;
public int[] solution(int[][] arr) {
this.arr = arr;
this.dupl = new boolean[arr.length][arr[0].length];
int[] answer = new int[2];
recurse(0, arr.length, 0, arr.length);

for(int i = 0; i < dupl.length; i++) {
for(int j = 0; j < dupl[0].length; j++) {
if(dupl[i][j] == true) continue;
if(arr[i][j] == 0) ++answer[0];
else if(arr[i][j] == 1) ++answer[1];
}
}
return answer;
}

private void recurse(int rowStart, int rowEnd, int colStart, int colEnd) {

int target = arr[rowStart][colStart];
for(int r = rowStart; r < rowEnd; ++r) {
for(int c = colStart; c < colEnd; ++c) {
if(target != arr[r][c]) {
recurse(rowStart, (rowStart+rowEnd)/2, colStart, (colStart+colEnd)/2);
recurse(rowStart, (rowStart+rowEnd)/2, (colStart+colEnd)/2, colEnd);
recurse((rowStart+rowEnd)/2, rowEnd, colStart, (colStart+colEnd)/2);
recurse((rowStart+rowEnd)/2, rowEnd, (colStart+colEnd)/2, colEnd);
return;
}
target = arr[r][c];
}
}

for(int r = rowStart; r < rowEnd; ++r) {
for(int c = colStart; c < colEnd; ++c) {
dupl[r][c] = true;
}
}
dupl[rowStart][colStart]=false;
}
}