Повернуть матрицу N ч N на 90 градусов по часовой стрелке


Учитывая проблемы с "Крекинг кодирования интервью"

Дано изображение представляет собой матрицу, где каждому пикселю изображение 4 байта, написать метод, чтобы повернуть изображение на 90 градусов по часовой стрелке.

Для простоты я предположил, что матрицу строк на моем примере так

[["a", "a", "a", "a"],
["b", "b", "b", "b"],
["c", "c", "c", "c"],
["d", "d", "d", "d"]]

становится

[["d", "c", "b", "a"],
["d", "c", "b", "a"],
["d", "c", "b", "a"],
["d", "c", "b", "a"]]

Вот мое решение на JavaScript

var rotate = function(matrix) {
    // Copy the original matrix
    var origMatrix = matrix.slice();
    for(var i=0; i < matrix.length; i++) {
        // Map each row entry to its rotated value
        var row = matrix[i].map(function(x, j) {
            var k = (matrix.length - 1) - j;
            return origMatrix[k][i];
        });
        matrix[i] = row;
    }
    return matrix;
};


2664
3
задан 5 февраля 2018 в 11:02 Источник Поделиться
Комментарии
2 ответа

Ты в курсе?

Там действительно много не проблема и есть множество решений.

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

Эти очень простые тесты, как правило, просто чтобы увидеть, если вы можете писать код. Вы будете поражены, как много людей устроиться на работу они не в состоянии сделать.

Оценки код.

Глядя на ваш код как консервативным персоналом, заинтересованных в коде стиль написания, и до настоящего времени знания языка.

Это можно кода, у вас есть работа, но будет у вас в наблюдением на некоторое время..нужно еще и поймать на язык, как вы не используете на ES6 в полной мере.

Общие моменты


  • Вы должны использовать const для константы, и пусть для переменных область видимости блока.

  • Вы не использовали какие-либо функции стрелка.

  • Я бы вопрос почему вы создали функцию, используя выражение, а не оператор function, чтобы убедиться, что вы знаете разницу. (Вы должны играть безопасно использовать инструкции функции)

  • Также может быть, немного больше кода, но это не проблема.

  • Код логики.. я хотел спросить, почему ты выбрал дублировать массив, а не просто создать новую, как вы пошли.

Быстрый рерайт

Я предполагаю, что поворот на месте (исходный массив) с новой строки

function rotate(matrix) {          // function statement
const N = matrix.length - 1; // use a constant
// use arrow functions and nested map;
const result = matrix.map((row, i) =>
row.map((val, j) => matrix[N - j][i])
);
matrix.length = 0; // hold original array reference
matrix.push(...result); // Spread operator
return matrix;
}

Некоторые дополнительные

Проблема государств - "изображения" и "пиксель", который даст подсказку, что это может быть судить о производительности. Они скажут вам, если он был. Но если у вас есть похожие проблемы и производительность важна, то ее лучше использовать старый добрый for петли, избегая любых итераторов, которые используют обратные вызовы.

Также ориентированную на выполнение функции будет поменять на месте, а не создавать новые массивы. Если вам приходилось делать это в реальном времени с изображениями для современных дисплеев ваш код будет делать большие ГХ просмотров (сбор мусора).

Альтернатива

Другой способ это может быть сделано путем вращения 4 пикселя за раз может уменьшить накладные расходы памяти и времени обработки. Разрушения позволяет поменять 4 углов за один раз без необходимости создавать временные переменные.

Я бы никогда не рекомендуем вам предоставить следующие Если было четкое предписание, для исполнения, и думать за пределами коробки.



// Commented version 

// N*N is square
// pixels are rotated inplace
// 4 by 4 rotated in 4 iterations
// 5 by 5 rotated in 7 iterations
function rotatePixels(image) {
var x, y, x1, y1, edge;
// Solve by swapping 4 at a time in rings from the outside in
const N = image.length; // size of array
const N1 = N - 1; // position of end item
const N2 = N / 2; // Half way position

// x,y hold the a cell coordinate
x = y = 0;

// x,y hold the diagonally opposite cell
x1 = y1 = N1;

// length of current edge
edge = N1;

// while not at the center
while (y < N2) {
// for each item on the current edge
while (x < edge) { // rotate points at outer edge
// swap 4 corner items
// using array destructed assignment
[
image[x ][y1],
image[y1][x1],
image[x1][N1 - y1],
image[y ][x ]
] = [
image[y ][x ],
image[x ][y1],
image[y1][x1],
image[x1][N1 - y1]
];
x += 1; // move top pos forward one
x1 -= 1; // move bottom pos back one
}
y += 1; // diagonally into array
x = y; // x same as y
y1 = x1 = N1-x; // and diagonal opposite
edge -= 1; // shorten the end
}
return image;
}

// How I would present it

function rotatePixels(image) {
var x, y, x1, y1, edge;
const N = image.length;
const N1 = N - 1;
const N2 = N / 2;
x = y = 0;
edge = x1 = y1 = N1;
while (y < N2) {
while (x < edge) {
[image[x][y1], image[y1][x1], image[x1][N1-y1], image[y][x]] =
[image[y][x] , image[x ][y1], image[y1][x1] , image[x1][N1-y1]];
x += 1;
x1 -= 1;
}
x = y += 1;
y1 = x1 = N1-x;
edge -= 1;
}
return image;
}

// At time of writing I was unsure as to the performance of the swap using destructuring
// Turns out it is very bad
// The next version is a more conventional swap and runs 3 time faster than the above version
// and 8 times faster than the conventional solution at top of answer

function rotatePixels(image) {
var x, y, x1, y1, edge;
const N = image.length;
const N1 = N - 1;
const N2 = N / 2;
x = y = 0;
edge = x1 = y1 = N1;
while (y < N2) {
while (x < edge) {
const a = image[y][x];
image[y][x] = image[x1][N1-y1];
image[x1][N1-y1] = image[y1][x1];
image[y1][x1] = image[x][y1];
image[x][y1] = a;
x += 1;
x1 -= 1;
}
x = y += 1;
y1 = x1 = N1-x;
edge -= 1;
}
return image;
}




5
ответ дан 5 февраля 2018 в 03:02 Источник Поделиться

Клонирование матрицы

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

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

Сопоставление значений

Ваш .map - это немного странно. Вы используете его на один массив, но тогда вы даже не используете значение и просто использовать индекс для доступа к другому массиву. Это также можно сделать проще. Энной строки столбца N-й входной. Таким образом, используя .map на входе и получаю правильное значение из каждой строки даст вам новую строку (вы должны обратить его тоже).

var row = matrix.map(function(e) {
return e[i]
}).reverse();

ЕС6

Множество новых функций было введено в ЕС6, который был доработан в 2015 году. Вы должны использовать их сейчас. Это означает, используя let вместо varи Стрела функций, которые отлично подходят для коротких inline функцию, как показано выше.

Окончательный код

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

function rotate(matrix) {
let result = [];
for(let i = 0; i < matrix[0].length; i++) {
let row = matrix.map(e => e[i]).reverse();
result.push(row);
}
return result;
};

3
ответ дан 5 февраля 2018 в 03:02 Источник Поделиться