Leetcode 54: Спираль Матрицы


Постановка задачи

Даны матрицы из M х n элементов (M строк, N столбцов), вернуть все элементы матрицы по спирали заказа. Например, Даны следующие матрицы:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Вы должны вернуться [1,2,3,6,9,8,7,4,5].

Мое введение алгоритма

Это алгоритм среднего уровня по Leetcode.com. Я занимаюсь более десяти раз с марта 2017 года до января. 2018. Я написал алгоритм в кратком интервью пять раз, а также смотрела пять сверстниками, работать по алгоритму. Я испытал боль, чтобы написать цикл for внутри-четыре раза цикл, я написал код с ошибкой в печати дважды одну строку матрицы, дублирующие выход на последнюю строку и первый столбец. И также я смотрел несколько раз коллеги на борьбу с таким количеством багов. В целом это алгоритм с большое удовольствие играть.

Как писать без ошибок решение в кратком интервью?

Первый раз у меня было пробное интервью на другом глумиться платформы интервью на январь. 23, 2018, и это анонимные.

Интервьюер спросил меня, если я могу написать ответ только через одну петлю вместо четырех циклов for внутри цикла while, в то время как два цикла for для прохода по строке, либо сверху или снизу; два цикла for для итерации по последней колонке или первый столбец.

Я работал на алгоритм более чем в 10 раз на макет интервью, но я никогда не выйти завершили идею, основанную на ограниченное время, забота и багги для петель. Никто из моих коллег вышла идея и писал подобные идеи, и мне оставалось только дискуссию с одним коллегиального раньше. В качестве интервьюера или интервьюируемого, я думал о четыре петли также проблематично.

Один раз я пожаловалась коллеге в макет интервью, когда я работал на четыре цикла этой проблемы спиральной матрицы. Я сказала коллеге, что мне нравится использовать дополнительный массив, чтобы отметить визит, так что мои четыре цикла for всегда можете пойти от 0 до строк - 1 или 0 в седла - 1. Код потребуется дополнительное время, чтобы перебирать элементы, но, безусловно, не стоит забывать, чтобы определить начальное и конечное положение. Совет коллеги не быть хакером в макет интервью, вы всегда должны следовать подсказка или совет интервьюера. Это единственный раз, когда я сделал очень близко к этой новой идее.

Это полезно пересмотреть все предыдущие практики посредством блогов код. Вот один из блогов о практике по спирали матрицы алгоритм.

Анализ алгоритма

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

Я также хотел бы практиковать такой подход, когда я задаю вопрос на этом сайте.

Вот некоторые ключевые слова для алгоритма матрицы по спирали.

Направление - есть четыре направления. Изменить направление, в случае необходимости, в порядке по часовой стрелке, начиная с левого верхнего угла (0,0).
Выбор - оставаться внутри массива
Визит - посещение каждого элемента в массиве только один раз. Не посещать более одного раза.
Приказ - выполняйте приказ по часовой стрелке, начиная с (0,0).

Быстрое решение, с читаемым кодом

Я писала решением C# и использовать дополнительное пространство, чтобы объявить массив, чтобы отметить элемент в матрице, посещает или не. Чтобы изменить направление, если текущая строка и столбец из Матрицы или границы его посещают до. Я написал решение после пробных интервью, я не мог поверить, что мне нужно так много намеков в кратком интервью после стольких практика, один намек на четыре направления, одним намеком, используя дополнительный массив для посещенных массива.

Здесь решением c#.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MatrixSpiralPrint
{
    class Program
    {
        /// <summary>
        /// Leetcode Spiral Matrix
        /// https://leetcode.com/problems/spiral-matrix/description/
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            var spiral = MatrixSpiralPrint(new int[,] { { 1, 2, 3 }, { 8, 9, 4 }, { 7, 6, 5 } });
            Debug.Assert(String.Join(",", spiral).CompareTo("123456789") == 0);
        }

        /// <summary>
        /// Navigate the direction automatically by checking boudary and checking 
        /// the status of element visited status. 
        /// Only one loop, perfect idea to fit in mock interview or interview 
        /// 20 minutes setting         
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        public static int[] MatrixSpiralPrint(int[,] array)
        {
            if (array == null || array.GetLength(0) == 0 || array.GetLength(1) == 0)
            {
                return new int[0];
            }

            int rows    = array.GetLength(0);
            int columns = array.GetLength(1);

            var visited = new int[rows, columns];
            int index = 0;
            int totalNumbers = rows * columns;

            var fourDirections = new List<int[]>();

            fourDirections.Add(new int[] { 0, 1 });     // left to right - top row
            fourDirections.Add(new int[] { 1, 0 });     // top to down   - last column
            fourDirections.Add(new int[] { 0, -1 });    // right to left - bottom row
            fourDirections.Add(new int[] { -1, 0 });    // bottom up     - first row

            int direction = 0;
            int row = 0;
            int col = 0;

            var spiral = new int[totalNumbers];

            while (index < totalNumbers)
            {
                var current = array[row, col];

                spiral[index++] = current;

                visited[row, col] = 1; // mark visit

                var nextRow = row + fourDirections[direction][0];
                var nextCol = col + fourDirections[direction][1];

                var isOutArrayBoundary = nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= columns;

                if (isOutArrayBoundary || visited[nextRow, nextCol] == 1) // change the direction
                {
                    direction = (direction + 1) % 4; // map to 0 to 3                    
                }

                row += fourDirections[direction][0];
                col += fourDirections[direction][1];
            }

            return spiral;
        }
    }
}


Комментарии
1 ответ

Зачем использовать целое число для включения/выключения статус?

Значения в visited равны либо 0, либо 1.
А boolean матрица будет естественным выбором для этой цели.

Вы действительно нуждаетесь в дополнительной памяти?

С помощью visited массив реализация несколько проще.
Другой способ, без дополнительного хранения будет отслеживать количество шагов, которые нужно сделать в текущем направлении.
Подумайте о правильных ценностях и наблюдать картину:


  • Топ: columns

  • Справа: rows - 1

  • Внизу: columns - 1

  • Слева: rows - 2

  • Топ: columns - 2

  • Справа: rows - 3

  • Внизу: columns - 3

  • Слева: rows - 4

  • ...

В принципе, чередуя столбец и строку графы, уменьшается на 1 при каждом изменении направления. Когда на следующий число шагов равно 0, пора прекращать.
Немного сложнее написать, но с использованием постоянного дополнительного хранения.

Обработка особых случаев

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

Случае null значение array не смысла ввода.
Если это случится, это выглядит подозрительно, как неисправность абонента.
Лучше было бы сигналом, что есть проблема, выдавая явное исключение.

Именования

fourDirections содержит 4 направлениям.
Не название коллекции, ее размер.
Просто directions было бы лучше.

2
ответ дан 30 января 2018 в 09:01 Источник Поделиться