검 지 오 프 터 19 번 문제 (js)
3941 단어 《 검 지 offer 》
제목 설명
행렬 을 입력 하고 외 향 에서 시계 방향 으로 순서대로 모든 숫자 를 출력 한다. 예 를 들 어 다음 과 같은 4 X 4 행렬 을 입력 하면 1, 2, 3, 8, 12, 16, 15, 14, 13, 9, 9, 10, 6, 7, 11, 10.
사고의 방향.
시계 방향 으로 인쇄 하 는 것 은 바로 이 순서 입 니 다. 왼쪽 에서 오른쪽으로 → 위 에서 아래로 → 오른쪽 에서 왼쪽으로 → 아래 에서 위로, 그리고 다음 라운드 의 이 순 서 를 이 어 가 는 것 입 니 다.모든 쪽 에는 출발점 과 종점 이 있 고 모든 라운드 의 같은 변 의 출발점 과 종점 은 규칙 적 이다.우 리 는 네 개의 변수 로 그들의 위 치 를 제어 한다.
function printMatrix(matrix)
{
// write code here
//
var row = matrix.length;
var column = matrix[0].length;
if (row === 0 || column === 0) return false;
var newMatrix = [];
//
var top = left = 0, right = column - 1, bottom = row - 1;
while (top <= bottom && left <= right ){
//
for (var i = left; i <= right; i++) {
newMatrix.push(matrix[top][i]);
}
// , top+1
for (var i = top + 1; i <= bottom; i++) {
newMatrix.push(matrix[i][right]);
}
// , ,
if (top != bottom) {
for (var i = right - 1; i >= left; i--) {
newMatrix.push(matrix[bottom][i]);
}
}
// 、 ,
if (left != right) {
for (var i = bottom - 1; i > top; i--) {
newMatrix.push(matrix[i][top]);
}
}
// ,
top++; left++; right--; bottom--;
}
return newMatrix;
}
실행 시간: 13ms, 메모리 사용량: 5344 k
사고방식
생각 과 차이 가 많 지 않 은 생각 이지 만 네 개의 통제 위 치 를 사용 하지 않 고 권 수 에 따라 출발점 을 정한다.
function printMatrix(matrix)
{
// write code here
var row = matrix.length;
var column = matrix[0].length;
if (row === 0 || column === 0) return false;
var newMatrix = [],i,j;
//
var circle = Math.floor(((row <= column ? row : column) - 1 ) / 2 )+ 1;
for (i = 0; i < circle; i++) {
//
for (j = i; j < column - i; j++) {
newMatrix.push(matrix[i][j]);
}
//
for (j = i+1; j < row-i; j++) {
newMatrix.push(matrix[j][column-1-i]);
}
//
for (j = column-2-i; (j >= i)&&(row-1-i != i); j--) {
newMatrix.push(matrix[row-1-i][j]);
}
//
for (j = row-2-i; (j > i)&&(column-1-i != i); j--) {
newMatrix.push(matrix[j][i]);
}
}
return newMatrix;
}
실행 시간: 12ms, 메모리 사용량: 5420 k
Q1: 권 수의 계산
- 2 \* 2:1 ; 2 / 2 = 1
- 3 \* 3:2 ; 3 / 2 = 1.5
- 4 \* 4:2 ; 4 / 2 = 2
- 5 \* 5:3 ; 5 / 2 = 2.5
- 6 \* 6:3 ; 6 / 2 = 3
- ...
즉, 2, 3 을 아래로 빼 면 같은 정수 (4, 5, 6, 7 동 리) 를 얻 을 수 있 지만, 원 수가 같은 것 은 3, 4 이다. 그러면 우 리 는 3, 4 를 빼 고 다시 아래로 빼 면 같은 정 수 를 얻 을 수 있다. 이 정 수 는 그들의 원 수 와 1 차이 가 나 기 때문에 다시 넣 어야 한다.행렬 이 일정한 행렬 이 같 지 않 기 때문에 우 리 는 둘 사이 의 작은 값 을 얻어 계산한다.그러면 원 수 는 Math. floor ((row < = column? row: column) - 1) / 2) + 1 입 니 다.
Q2: 오른쪽 에서 왼쪽으로 왜 j = column - 2 - i
row 는 줄 수 이 고 column 은 열 수 이기 때문에 오른쪽 아래 의 그 값 은 matrix [row - 1] [column - 1] 입 니 다. 1 을 빼 야 합 니 다.그러면 오른쪽 에서 왼쪽으로:
Q3:row-1-i != i 와 column - 1 - i! =무슨 뜻
사고방식 과 마찬가지 로 행렬 이 한 줄 또는 한 줄 밖 에 없 는 상황 을 고려 해 야 한다. 그렇지 않 으 면 평행 한 변 중 재수 (예 를 들 어 왼쪽 에서 오른쪽으로 이미 읽 었 고 오른쪽 에서 왼쪽으로 반복 읽 을 수 있다) 가 나타난다.한 줄 만 있 을 때, 즉 위 와 아래 가 겹 치고, 원 수 i 에 따라 위 는 i 이 고, 아래 는 row - 1 - i 이 며, 한 열의 상황 은 동일 하 다.
잘 돌아 가... 몇 번 더 생각 했 으 면 좋 겠 다, 큐.