从特定方向的矩阵中提取所有对角线的列表 [英] Extracting a list of all diagonals from a matrix in a specific direction

问题描述

我正在尝试从矩阵中提取特定方向(例如右下)的所有对角线.

I'm trying to extract from a matrix all the diagonals in a certain direction, for example down-right.

对于以下矩阵:

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.

The language I'm using is 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() );
}

添加到特里的输出单词是

output words added to the trie are

[ "SLU" "UAS" "GSE" ]

期望的字符串存储在trie中(顺序无关紧要)

expected strings stored in the trie (order doesn't matter )

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

推荐答案

这是一个有趣的问题.

很容易陷入嵌套循环中.

It's easy to get tangled up in nested loops.

我注意到如果将单词组合成一个字符串，就会出现一种模式.

I noticed if I put the words together into one string, a pattern emerged.

以OP的示例为例，三个单词"SUGAR"，"GLASS"，"MOUSE"被串联在一起成为SUGARGLASSMOUSE.

Taking the OP's example, the three words "SUGAR", "GLASS", "MOUSE" are concatenated together into SUGARGLASSMOUSE.

这是我需要从串联字符串中获取的字符的从零开始的字符位置.我已经将它们排成一排，以便您可以更轻松地看到图案.

Here are the zero based character positions of the characters that I need to get from the concatenated string. I've lined them up so you can more easily see the pattern.

          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个字母组成.

See the pattern yet? I have 3 indexes that consist of 5 iterations. I have 3 words that consist of 5 letters.

对角词的数量为letters + words - 1.我们减去1是因为字符位置0中的第一个字母仅使用一次.

The number of diagonal words is letters + words - 1. We subtract 1 because the first letter in character position 0 is only used once.

这是我运行的测试的结果.

Here are the results from a test I ran.

[ "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();
    }

}

这篇关于从特定方向的矩阵中提取所有对角线的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！