java - 仅使用一维数组顺时针遍历字符串

Question

我已经实现了一个函数 TraverseStringClockwise，它采用逗号分隔的整数字符串、宽度和高度，并通过使用 2D 字符数组按顺时针顺序遍历返回一个新字符串。我正在尝试使用一维数组执行相同的操作，但我遇到了问题。

例子:

Str=”1,2,3,4,5,6,7,8,9,10,11,12”;Width=3;Height=4;Returnstr=”1,2,3,6, 9,12,11,10,7,4,5,8”

任何指示/帮助？

这是代码

公共(public)类 TraverseStringClockwise {

// Build 2-dimensional matrix representing h * w
public static String[][] buildMatrix(String[] s, int width, int height)
{
    String[][] matrix = new String[height][width];
    int charPos = 0;
    for(int i = 0; i < height; i++)
    {
        for(int j = 0; j < width; j++)
        {
            matrix[i][j] = s[charPos++];
        }
    }
    return matrix;
}

public static String traverseStringClockwise(String s, int width, int height)
{
    // invalid if width or height are zero or there aren't enough elems in String to fill the matrix
    if(s == null || width == 0 || height == 0 || (s.split(",").length != width * height) )
    {
        return null;
    }
    String[][] matrix = buildMatrix(s.split(","), width, height); // O(n) where n = w*h
    Cursor cursor = new Cursor(width, height);
    StringBuilder sb = new StringBuilder();
    while(!cursor.isWalkComplete()) // // O(n) where n = w*h
    {
        cursor.walk();
        sb.append(matrix[cursor.colPos][cursor.rowPos]);
        if(!cursor.isWalkComplete())
        {
            sb.append(",");
        }
    }
    return (sb.length() > 1) ? sb.toString() : null;
}


/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    String input = "1,2,3,4,5,6,7,8,9,10,11,12";
    int width = 3, height = 4;
    String[][] block = buildMatrix(input.split(","), 3, 4);
    System.out.println("INPUT = " + input);
    System.out.println("OUTPUT = " + walkStringClockwise(input, width, height));
}

Answer 1

如果您已经拥有在二维数组中按顺时针顺序遍历数组的代码，则可以使用标准技巧将此代码转换为仅使用一维数组，方法是将二维数组线性化为一维数组。一种方法是将二维数组存储为行优先顺序的一维数组。例如，给定这个二维数组:

 1  2  3
 4  5  6
 7  8  9
10 11 12

您会将其编码为一维数组

 1 2 3 4 5 6 7 8 9 10 11 12

也就是说，您先布置第一行的所有元素，然后布置第二行的所有元素，然后布置第三行的所有元素，依此类推。

这种方法的优点是，如果给你一个原始二维数组的索引(行，列)，你可以高效地找到一维数组中的匹配位置。要了解如何执行此操作，请注意您在原始数组中采取的每个水平步骤对应于一维数组中的水平步骤，而您在原始数组中采取的每个垂直步骤对应于跳过一维数组中的一行元素.总的来说，这个公式是二维数组中 (row, col) 处的元素可以在一维数组中的位置 row * width + col 找到。

鉴于此，您可以尝试重写代码以仅使用一维数组，将您使用二维数组的所有实例替换为相应的代码以访问一维数组中的适当元素，如上所述。

希望这对您有所帮助!