对角线穿过阵列

Question

我有一个任意大小的大数组.这是一个方阵.我试图掌握如何沿着对角线遍历它/而不是\(我已经知道该怎么做).到目前为止,我有以下代码:

char[][] array = new char[500][500];
//array full of random letters
String arrayLine = "";
for (int y = 0; y < array.length; y++) {
    for (int x = 0; x < array.length; x++) {
        for (???) {
            arrayLine = arrayLine + array[???][???];
        }
    }
    System.out.println(arrayLine);
}

我有三个循环,因为这是我做另一个对角线的方式:

for (int y = 0; y < array.length; y++) {
    for (int x = 0; x < array.length; x++) {
        for (int z = 0; z < array.length-y-x; z++) {
            arrayLine = arrayLine + array[y+z][x+z];
        }
    }
    System.out.println(arrayLine);
}

在我的尝试中,我继续超越边界并获得ElementOutOfBounds异常.假设数组如下(3x3而不是500x500):

A B C
D E F
G H I

我想打印出以下字符串:

A
BD
CEG
FH
I

之前的SO问题与整数数组有类似的问题,解决方案基于数组元素的总和.但我正在使用字符,所以我想不出一种方法来获得它.

Answer 1

想想细胞的坐标:

. 0 1 2
0 A B C
1 D E F
2 G H I

对于任何对角线,所有元素都有一些共同点:元素坐标的总和是常数.以下是常量:

0 = 0+0 (A)
1 = 1+0 (B) = 0+1 (D)
2 = 2+0 (C) = 1+1 (E) = 0+2 (G)
3 = 2+1 (F) = 1+2 (H)
4 = 2+2 (I)

最小常数是最小坐标和,0.最大常数是最大坐标和.由于每个坐标分量都可以达到array.length - 1,因此最大常数为2 * (array.length - 1).

所以要做的就是迭代常量.对于每个常量,迭代其坐标总和为常量的元素.这可能是最简单的方法:

for (int k = 0; k <= 2 * (array.length - 1); ++k) {
    for (int y = 0; y < array.length; ++y) {
        int x = k - y;
        if (x < 0 || x >= array.length) {
            // Coordinates are out of bounds; skip.
        } else {
            System.out.print(array[y][x]);
        }
    }
    System.out.println();
}

然而,这将最终迭代许多越界坐标,因为它总是迭代所有可能的y坐标,即使只有一个对角线包含所有可能的y坐标.让我们改变y循环,使它只访问y当前所需的坐标k.

越界坐标的一个条件是x < 0.替换定义x并解决:

x < 0
k - y < 0
k < y
y > k

所以,何时y > k,x将是负面的.因此我们只想循环y <= k.

越界坐标的另一个条件是x >= array.length.解决:

x >= array.length
k - y >= array.length
k - array.length >= y
y <= k - array.length

那么什么时候y <= k - array.length,x会太大了.因此,我们希望从y0 开始,或者k - array.length + 1以较大者为准.

for (int k = 0; k <= 2 * (array.length - 1); ++k) {
    int yMin = Math.max(0, k - array.length + 1);
    int yMax = Math.min(array.length - 1, k);
    for (int y = yMin; y <= yMax; ++y) {
        int x = k - y;
        System.out.print(array[y][x]);
    }
    System.out.println();
}

注意:我只证明了这个代码是正确的.我没有测试过.