二维数组包含其他二维数组 [英] 2d Array contains other 2d Array

问题描述

有什么可以为发现一个2-D阵列包含任何其他2-D阵列的最佳解决方案？
例如：

What can be the best solution for finding that a 2-D array contains any other 2-D array? For example:

char a[][]={{'a','b'}, {'b','a'}}
char b[][]={{'a','b'}, {'b','a'}, {'a','b'}, {'a','b'}, {'a','b'}, {'b','a'}}

那么答案应该是2，因为B包含了2次。

Then answer should be 2 because b contains a 2 times.

推荐答案

我在这里写蛮力解决方案：

I am writing a Brute Force solution here:

理念：

在开始矩阵内要找到另一个2维数组的左上角（0,0）。

Start at the top left corner(0,0) of matrix inside which you want to find another 2 d array.

按行匹配更小的矩阵行大矩阵的条目，如果所有行的所有条目匹配，那么二维数组已经找到。如果任何行中的任何条目不匹配，然后去下一个二维子阵。

Match the entries of bigger matrix with smaller matrix row by row and if all entries of all rows match,then the 2d array has been found. If any entry of any row does not match,then go for the next 2d subarray.

接下来的2D子阵从（0,1）开始。

The next 2d subarray will start from (0,1).

我们做到这一点，直到没有更多的子阵列留给检查。

We do this until no more subarrays are left to check for.

class Twodarray
{
 public static void main(String []args)
 {
  char a[][]={{'a','b'}, {'b','a'}};
  char b[][]={{'a','b','c'}, {'b','a','d'}, {'a','b','a'}, {'a','b','b'}, {'a','b','a'}, {'b','a','a'}};
  int c=number_of_2d_arrays(b,a);
  System.out.println(c);
 }
  public static int number_of_2d_arrays(char [][]arr1,char [][]arr2)
    {
     int i=0,j=0,c=0;
     while(true)
     {
      int row=i,col=j;      
      if(arr2.length>arr1.length-row)
      {
       break;
      }
      else if(arr2[0].length>arr1[0].length-col&&col==0)
      {break;}
      else if(arr2[0].length>arr1[0].length-col)
      {++i;j=0;}
      else
      {
       boolean matches=true;
       for(int a=0;a<arr2.length;++a)
       {col=j;
        for(int b=0;b<arr2[0].length;++b)
        {         
         if(arr1[row][col++]!=arr2[a][b])
         {matches=false;break;}
        }    

        if(!matches)
         break;
        ++row;
       }       
       if(matches)
        {++c;}
       ++j;
      }
     }
    return c;
    }
}

这篇关于二维数组包含其他二维数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！