用於在矩陣中搜索模式的算法或java代碼

Question

我有一個如下所示的4 * 5矩陣。

1 1 1 0 0 
1 0 0 0 1 
1 1 1 0 0 
0 0 0 1 1 

我期待在Java程序來獲得下列組的模式。

• 一組隨後的5個1。
• 一組隨後的2 1。
• 2組單個1。

而且上述任何一組都不應該相交。 這是Zycus infotech的一個採訪問題，我無法解決。任何能夠提出解決這個問題的邏輯的人都會很有幫助！

Answer 1

我打算假設您對數據的處理方式沒有限制，並對其進行組織。通過這個，我的意思是你不必在給定矩陣就緒的地方做任何事情，並且你可以使幫助數據結構來幫助你完成任務（正如我在答案中使用了一個額外的ArrayList）。

我們開始：

int[][] matrix = {{1,1,1,0,0},{1,0,0,0,1},{1,1,1,0,0},{0,0,0,1,1}}; 

對應於我們原有的結構：

1 1 1 0 0 
1 0 0 0 1 
1 1 1 0 0 
0 0 0 1 1 

所以，我們看到了蝙蝠的權利，爲了得到一組4 1的，我們的需要從第2行繞到第3行，然後得到一組5 1，我們需要從第4行繞回到第1行。這意味着我們基本上將這個矩陣視爲一個1的連續行和0以及矩陣結構使這種混淆。因此，我們可以這樣扁平化，使事情變得更簡單：

List<Integer> list = new ArrayList<Integer>(); 
    for (int i = 0; i < matrix.length; i++) { 
     for (int j = 0; j < matrix[i].length; j++) { 
      list.add(matrix[i][j]); 
     } 
    } 

，這給我們：

[1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1] 

，這看起來有點更好了！然而，我們仍然有這個列表的問題在一個週期中圍繞自己。現在，我們可以編寫代碼來說明這個列表是否包含可能的鄰接1，或者我們可以修改列表，以便我們知道100％，確保列表的開始和結束之間沒有相鄰的1。這意味着我們希望列表以0開始或結束，從而確保沒有鄰接關係。我們通過從列表開始到列表末尾的所有1的漂移小換位來實現這一點。

// keep track of how we're adjusting the list so we can calculate the proper start of adjacency 
    int adjustment = 0; 
    for (int i = 0; i < list.size(); i++) { 
     if (list.get(i) == 1) { 
      list.add(list.remove(i)); 
      i--; 
      adjustment++; 
     } else { 
      break; 
     } 
    } 

，現在我們有：

[0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1] 

，我們可以看到的是，現在很容易得到1層的期望的羣體的要求。

如果你只是想計數1的的鄰接：

int count = 0; 
    for (Integer a : list) { 
     if (a == 1) { 
      count++; 
     } else { 
      if (count > 0) { 
       System.out.println("Group of " + count + " adjacent 1's"); 
      } 
      count = 0; 
     } 
    } 
    if (count > 0) { 
     System.out.println("Group of " + count + " adjacent 1's"); 
    } 

如果您正在尋找1組5級相鄰1的，2組2個相鄰的1和1組1相鄰的1沒有交集，那麼我們可以這樣做：

for (int num : Arrays.asList(5, 2, 2, 1)) { 
     int count = 0; 
     int start = -1; 
     for (int i = 0; i < list.size(); i++) { 
      if (list.get(i) == 1) { 
       if (start == -1) { 
        start = i; 
       } 
       count++; 
      } else { 
       start = -1; 
       count = 0; 
      } 
      if (count == num) { 
       System.out.println("Group of " + num + " adjacent 1's starting at " + ((start + adjustment)/5) + "," + ((start + adjustment) % 5)); 
       for (int j = start; j < start + count; j++) { 
        list.set(j, 0); 
       } 
       break; 
      } 
     } 
    } 

其工作原理是通過尋找列表計算相鄰的，直到我們達到我們所期望的數量（起始於我們的人數最多（5）和向下較小的工作我們的方式），那麼我們輸出的開始然後從我們的清單中刪除那些相鄰的1（通過se讓他們到0）。這樣，我們不會再次無意中計算它們（滿足我們對組中沒有交集的限制）。一旦我們得到了所需的相鄰1的數量，我們也存儲了它的起始位置。然後我們根據我們從列表的開始到結束的次數來調整它，然後分割得到行號並使用模數來獲得列號。

我們得到作爲我們的結果是：

Group of 5 adjacent 1's starting at 3,3 
Group of 2 adjacent 1's starting at 1,4 
Group of 2 adjacent 1's starting at 2,1 
Group of 1 adjacent 1's starting at 1,0 

到目前爲止，我所做的假設矩陣將永遠在它至少一個0。如果沒有，您需要在我的循環之前在list.contains(0)上添加一個檢查，以將1從列表的前面移動到列表的後面。

---

把所有這一切彙集成一個代碼塊：

int[][] matrix = {{1,1,1,0,0},{1,0,0,0,1},{1,1,1,0,0},{0,0,0,1,1}}; 
    List<Integer> list = new ArrayList<Integer>(); 
    for (int i = 0; i < matrix.length; i++) { 
     for (int j = 0; j < matrix[i].length; j++) { 
      list.add(matrix[i][j]); 
     } 
    } 

    int adjustment = 0; 
    if (list.contains(0)) { 
     for (int i = 0; i < list.size(); i++) { 
      if (list.get(i) == 1) { 
       list.add(list.remove(i)); 
       i--; 
       adjustment++; 
      } else { 
       break; 
      } 
     } 
    } 

    int count = 0; 
    for (Integer a : list) { 
     if (a == 1) { 
      count++; 
     } else { 
      if (count > 0) { 
       System.out.println("Group of " + count + " adjacent 1's"); 
      } 
      count = 0; 
     } 
    } 
    if (count > 0) { 
     System.out.println("Group of " + count + " adjacent 1's"); 
    } 

    for (int num : Arrays.asList(5, 2, 2, 1)) { 
     int count2 = 0; 
     int start = -1; 
     for (int i = 0; i < list.size(); i++) { 
      if (list.get(i) == 1) { 
       if (start == -1) { 
        start = i; 
       } 
       count2++; 
      } else { 
       start = -1; 
       count2 = 0; 
      } 
      if (count2 == num) { 
       System.out.println("Group of " + num + " adjacent 1's starting at " + ((start + adjustment)/5) + "," + ((start + adjustment) % 5)); 
       for (int j = start; j < start + count2; j++) { 
        list.set(j, 0); 
       } 
       break; 
      } 
     } 
    }