Строка перемещения по часовой стрелке с использованием только 1D массива - PullRequest
Новая
       3

Строка перемещения по часовой стрелке с использованием только 1D массива

1 голос
/ 06 сентября 2011

Я реализовал функцию TraverseStringClockwise, которая принимает разделенную запятыми строку целых чисел, ширину и высоту и возвращает новую строку, проходя по часовой стрелке, используя 2D Char Array. Я пытаюсь сделать то же самое, используя массив 1D, но у меня возникают проблемы.

Пример:

Str =»1,2,3,4,5,6,7,8,9,10,11,12” ; ширина = 3; Высота = 4; Returnstr =» 1,2,3,6, 9,12,11,10,7,4,5,8”

Любые указатели / помощь?

вот код

открытый класс 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));
}

}

1 Ответ

2 голосов
/ 06 сентября 2011

Если у вас уже есть код для перемещения массива по часовой стрелке в двумерном массиве, вы можете использовать стандартный прием для преобразования этого кода в использование только одномерного массива путем линеаризации двумерного массива в одномерный массив.Один из способов сделать это - сохранить двумерный массив в виде одномерного массива в главном порядке строк.Например, для этого двумерного массива: 

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

Вы бы закодировали его как массив 1D 

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

То есть вы разложили все элементы первой строки, а затемвсе элементы второй строки, затем все элементы третьей строки и т. д.

Преимущество этого подхода состоит в том, что если вам задан индекс (строка, столбец) в исходный 2D-массив, выможет найти подходящую позицию в массиве 1D.Чтобы увидеть, как это сделать, обратите внимание, что каждый горизонтальный шаг, который вы делаете в исходном массиве, соответствует горизонтальному шагу в массиве 1D, в то время как каждый вертикальный шаг, который вы делаете в массиве originl, соответствует пропуску одной строки элементов в массиве 1D.,В целом, эта формула состоит в том, что элемент в (row, col) в массиве 2D можно найти в позиции row * width + col в массиве 1D.

Учитывая это, вы можете попробовать переписать свой код так, чтобы он простоиспользуйте одномерный массив, заменив все экземпляры, в которых вы использовали двумерный массив, соответствующим кодом для доступа к нужному элементу в одномерном массиве, как описано выше.

Надеюсь, это поможет!

...