검 지 오 프 터 19 번 문제 (js)

3941 단어 《 검 지 offer 》
제1 9 문제 시계 방향 인쇄 행렬
제목 설명
행렬 을 입력 하고 외 향 에서 시계 방향 으로 순서대로 모든 숫자 를 출력 한다. 예 를 들 어 다음 과 같은 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 을 빼 야 합 니 다.그러면 오른쪽 에서 왼쪽으로:
  • 1 바퀴: i = 0;시작 위 치 는 matrix [row - 1] [column - 2] 입 니 다. 왜 - 2 입 니까? 앞 에 있 는 그 수 는 이미 지난 라운드 에 옮 겨 다 녔 기 때 문 입 니 다. 좋 습 니 다.
  • 두 번 째 바퀴: i = 1;시작 위 치 는 matrix [row - 1 - i] [column - 2 - 1]
  • n 번 째 권: i = n - 1;시작 위 치 는 matrix [row - 1 - (n - 1)] [column - 2 - n]
  • 다른 변 의 경우 도 마찬가지다. 이미 위 에 널 려 있 는 수 를 빼 고 동그라미 와 의 관 계 를 결합 하면 답 을 얻 을 수 있다 는 것 이다.
    Q3:row-1-i != i 와 column - 1 - i! =무슨 뜻
    사고방식 과 마찬가지 로 행렬 이 한 줄 또는 한 줄 밖 에 없 는 상황 을 고려 해 야 한다. 그렇지 않 으 면 평행 한 변 중 재수 (예 를 들 어 왼쪽 에서 오른쪽으로 이미 읽 었 고 오른쪽 에서 왼쪽으로 반복 읽 을 수 있다) 가 나타난다.한 줄 만 있 을 때, 즉 위 와 아래 가 겹 치고, 원 수 i 에 따라 위 는 i 이 고, 아래 는 row - 1 - i 이 며, 한 열의 상황 은 동일 하 다.
    잘 돌아 가... 몇 번 더 생각 했 으 면 좋 겠 다, 큐.

    좋은 웹페이지 즐겨찾기