在特定方向

Question

我試圖從矩陣中提取所有的對角線在一定的方向，例如下右從提取矩陣對角線的所有的列表。

對於以下矩陣：

A B C D 
E F G H 
I L M N 

預期的結果應該是

[ [A F M], [B G N], [C H], [D], [E L], [I] ] 

一般的做法是值得歡迎的。

我使用的語言是Java。

謝謝！

編輯

String[] grid = {"SUGAR", 
       "GLASS", 
       "MOUSE"}; 

for(int k = 0; k < grid.length; k++) 
{ 
    StringBuffer buffer = new StringBuffer(); 

    for(int i = 0; i < grid.length 
       && i+k < grid[0].length(); i++) 
    { 
     buffer.append(grid[i].charAt(i+k)); 
    } 

    trie.addWord(buffer.toString()); 
} 

輸出字加入到線索是

[ "SLU" "UAS" "GSE" ] 

存儲在特里（順序並不重要）

預計串

[ "SLU" "UAS" "GSE" "GO" "M" "AS" "R"] 

Answer 1

這是一個有趣的問題要解決。

這很容易在嵌套循環得到糾結了。

我注意到如果我把這些單詞放在一個字符串中，就會出現一個模式。

以OP的例子爲例，「SUGAR」，「GLASS」，「MOUSE」這三個單詞連接在一起成爲SUGARGLASSMOUSE。

這裏是我需要從串聯字符串中獲得的字符的基於零的字符位置。我把它們排列起來，這樣你就可以更容易地看到圖案。

  10  M 
    5 11  GO 
0 6 12  SLU 
1 7 13  UAS 
2 8 14  GSE 
3 9   AS 
4    R 

看到模式了嗎？我有3個由5次迭代組成的索引。我有3個字由5個字母組成。

對角字的數量是letters + words - 1。我們減1，因爲字符位置0中的第一個字母只用了一次。

這是我跑過的測試的結果。

[ "SUGAR" "GLASS" "MOUSE" "STATE" "PUPIL" "TESTS" ] 
[ "T" "PE" "SUS" "MTPT" "GOAIS" "SLUTL" "UASE" "GSE" "AS" "R" ] 

[ "SUGAR" "GLASS" "MOUSE" ] 
[ "M" "GO" "SLU" "UAS" "GSE" "AS" "R" ] 

而這裏的代碼：

import java.util.ArrayList; 
import java.util.List; 

public class Matrix { 

    public static final int DOWN_RIGHT = 1; 
    public static final int DOWN_LEFT = 2; 
    public static final int UP_RIGHT = 4; 
    public static final int UP_LEFT = 8; 

    public String[] getMatrixDiagonal(String[] grid, int direction) { 
     StringBuilder builder = new StringBuilder(); 
     for (String s : grid) { 
      builder.append(s); 
     } 
     String matrixString = builder.toString(); 

     int wordLength = grid[0].length(); 
     int numberOfWords = grid.length; 
     List<String> list = new ArrayList<String>(); 


     if (wordLength > 0) { 
      int[] indexes = new int[numberOfWords]; 

      if (direction == DOWN_RIGHT) { 
       indexes[0] = matrixString.length() - wordLength; 
       for (int i = 1; i < numberOfWords; i++) { 
        indexes[i] = indexes[i - 1] - wordLength; 
       } 

       int wordCount = numberOfWords + wordLength - 1; 

       for (int i = 0; i < wordCount; i++) { 
        builder.delete(0, builder.length()); 
        for (int j = 0; (j <= i) && (j < numberOfWords); j++) { 
         if (indexes[j] < wordLength * (wordCount - i)) { 
          char c = matrixString.charAt(indexes[j]); 
          builder.append(c); 
          indexes[j]++; 
         } 
        } 
        String s = builder.reverse().toString(); 
        list.add(s); 
       } 
      } 

      if (direction == DOWN_LEFT) { 
       // Exercise for original poster 
      } 

      if (direction == UP_RIGHT) { 
       // Exercise for original poster 
      } 

      if (direction == UP_LEFT) { 
       // Exercise for original poster 
       // Same as DOWN_RIGHT with the reverse() removed 
      } 
     } 

     return list.toArray(new String[list.size()]); 
    } 

    public static void main(String[] args) { 
     String[] grid1 = { "SUGAR", "GLASS", "MOUSE", "STATE", "PUPIL", "TESTS" }; 
     String[] grid2 = { "SUGAR", "GLASS", "MOUSE" }; 

     Matrix matrix = new Matrix(); 
     String[] output = matrix.getMatrixDiagonal(grid1, DOWN_RIGHT); 
     System.out.println(createStringLine(grid1)); 
     System.out.println(createStringLine(output)); 

     output = matrix.getMatrixDiagonal(grid2, DOWN_RIGHT); 
     System.out.println(createStringLine(grid2)); 
     System.out.println(createStringLine(output)); 
    } 

    private static String createStringLine(String[] values) { 
     StringBuilder builder = new StringBuilder(); 
     builder.append("[ "); 

     for (String s : values) { 
      builder.append("\""); 
      builder.append(s); 
      builder.append("\" "); 
     } 

     builder.append("]"); 

     return builder.toString(); 
    } 

} 

Answer 2

你可以使用2維數組代表您的矩陣，

的char [] []矩陣=的char [] []

然後你可以使用for循環迭代透徹，並提取出把你想要的，你的算法的輸入是其對角線你想要的方向。

For Ex;一個可能的輸入會被降權

根據你要如何通過循環的初始條件和終止條件迭代決定可能的輸入。

開始與最後一列第一行字符

R = 0，C = coulmn_count -1;

終止條件將是first_column最後一行索引處的字符。

R = ROW_COUNT -1，C = 0;

在最後一行或最後一列讀取字符時，每個迭代的子循環的終止

Answer 3

如果數據以表格的形式，你可以只掃描矩陣了第一個欄，然後在左第一行。

final String[M][N] mtx = { ... }; 

public List<List<String>> diagonalize() { 
    final List<List<String>> diags = new ArrayList<>(); 
    for (int row = M - 1; row > 1; --row) { 
     diags.add(getDiagonal(row, 0)); 
    } 
    for (int col = 0; col < N; ++col) { 
     diags.add(getDiagonal(0, col)); 
    } 
    return diags; 
} 

private List<String> getDiagonal(int x, int y) { 
    final List<String> diag = new ArrayList<>(); 
    while (x < M && y < N) { 
     diag.add(mtx[x++][y++]); 
    } 
    return diag; 
} 

Answer 4

String[] grid = {"SUGAR", 
      "GLASS", 
      "MOUSE"}; 
    System.out.println("Result: " + Arrays.toString(diagonals(grid))); 

public static String[] diagonals(String[] grid) { 
    int nrows = grid.length; 
    int ncols = grid[0].length(); 
    int nwords = ncols + nrows - 1; 
    String[] words = new String[nwords]; 
    int iword = 0; 
    for (int col = 0; col < ncols; ++col) { 
     int n = Math.min(nrows, ncols - col); 
     char[] word = new char[n]; 
     for (int i = 0; i < n; ++i) { 
      word[i] = grid[i].charAt(col + i); 
     } 
     words[iword] = new String(word); 
     ++iword; 
    } 
    for (int row = 1; row < nrows; ++row) { 
     int n = Math.min(ncols, nrows - row); 
     char[] word = new char[n]; 
     for (int i = 0; i < n; ++i) { 
      word[i] = grid[row + i].charAt(i); 
     } 
     words[iword] = new String(word); 
     ++iword; 
    } 
    assert iword == nwords; 
    return words; 
} 

Result: [SLU, UAS, GSE, AS, R, GO, M] 

先用在列的第一個元素的循環。然後在行上循環跳過第0行。 兩個循環中的代碼都非常對稱。 沒什麼太難的。假定所有字符串具有相同的長度。

作爲一個循環：

public static String[] diagonals(String[] grid) { 
    int nrows = grid.length; 
    int ncols = grid[0].length(); 
    int nwords = ncols + nrows - 1; 
    String[] words = new String[nwords]; 

    // Position of first letter in word: 
    int row = 0; 
    int col = ncols - 1; 

    for (int iword = 0; iword < nwords; ++iword) { 
     int n = Math.min(nrows - row, ncols - col); 
     char[] word = new char[n]; 
     for (int i = 0; i < n; ++i) { 
      word[i] = grid[row + i].charAt(col + i); 
     } 
     words[iword] = new String(word); 

     if (col > 0) { 
      --col; 
     } else { 
      ++row; 
     } 
    } 
    return words; 
} 

的word聲明可以在循環外提出。簡單地走（左邊和上邊）。