행렬 대각 합 Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 어도비 벽돌
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 매트릭스조회수 106

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

Matrix Diagonal Sum 문제에서 정사각형 매트릭스 정수가 주어집니다. 우리는 대각선에 존재하는 모든 요소의 합을 계산해야합니다. 즉, XNUMX 차 대각선과 XNUMX 차 대각선에있는 요소입니다. 각 요소는 한 번만 계산되어야합니다.

mat = [[1,2,3],
       [4,5,6],
       [7,8,9]]
25

설명 :

대각선 합계 : 1 + 5 + 9 + 3 + 7 = 25
mat [1] [1] = 5 요소는 한 번만 계산됩니다.

mat = [[1,1,1,1],
       [1,1,1,1],
       [1,1,1,1],
       [1,1,1,1]]
8

설명 :

Diagonals sum: (1+1+1+1)+(1+1+1+1)=8.

접근

행렬 대각 합 Leetcode 솔루션

주어진 정사각형 행렬에서 우리는 대각선 요소를 더하고 그 합계를 반환해야합니다.
대각선 요소에 대한 행렬의 인덱스 패턴이 무엇인지 살펴 보겠습니다. 먼저 주 대각선에서 보면 첫 번째 요소는 인덱스 i = 0, j = 0에 있고 다음 요소는 (i + 1, j + 1)에 있습니다. 마찬가지로 마지막 요소는 인덱스 (n-1, n-1)에 있으며 여기서 n은 주어진 정사각형 행렬의 너비입니다. 이 대각선의 모든 지수는 i = j입니다.
따라서 다음과 같이 루프에서이 대각선을 반복 할 수 있습니다.

1. i = 0 및 j = 0을 초기화합니다.
2. 나는 동안 루프를 실행
3. 현재 요소를 추가합니다. i와 j를 모두 1 씩 증가시킵니다.

이제 0 차 대각선을 살펴 보겠습니다. 첫 번째 행의 첫 번째 요소 인덱스는 i = 1, j = n-1입니다. 다음 요소는 (i + 1.j-1,0)에 있습니다. 마찬가지로 마지막 요소는 (n-XNUMX)에 있습니다.
따라서 루프에서이 대각선을 다음과 같이 반복 할 수 있습니다.

1. i = 0 및 j = n-1을 초기화합니다.
2. 나는 동안 루프를 실행 = 0.
3. 현재 요소를 추가합니다 (1 차 대각선에 있지 않은 경우, 즉 i == j). i를 1 씩 증가시키고 j를 XNUMX만큼 감소시킵니다.

마지막으로 두 작업 후 합계를 반환합니다.

실시

Matrix Diagonal Sum Leetcode 솔루션을위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

int diagonalSum(vector<vector<int>>& mat) 
{
    int n=mat.size();

    int sum=0;
    int i=0,j=0;

    while(i<n)
    {
        sum+=mat[i][j];
        i++;
        j++;
    }

    i=0;
    j=n-1;

    while(i<n)
    {
        if(i!=j)   sum+=mat[i][j];
        i++;
        j--;
    }

    return sum;
}

int main() 
{
    vector<vector<int>> mat={
            {1,2,3},
            {4,5,6},
            {7,8,9}  
    };
   
    cout<<diagonalSum(mat)<<endl;

  return 0; 
}
25

Matrix Diagonal Sum Leetcode 솔루션을위한 Java 프로그램

import java.lang.*;

class Rextester
{  
    public static int diagonalSum(int[][] mat) 
    {
        int n=mat.length;
        
        int sum=0;
        int i=0,j=0;
        
        while(i<n)
        {
            sum+=mat[i][j];
            i++;
            j++;
        }
        
        i=0;
        j=n-1;
        
        while(i<n)
        {
          if(i!=j)   sum+=mat[i][j];
            
            i++;
            j--;
        }
        
        return sum;
        
    }
    
    public static void main(String args[])
    {
       int[][] mat={
            {1,2,3},
            {4,5,6},
            {7,8,9}  
        };
    
       System.out.println(diagonalSum(mat));
   
    }
}
25

Matrix Diagonal Sum Leetcode 솔루션에 대한 복잡성 분석

시간 복잡성

의 위에) : 여기서 N은 N ^ 2 개의 요소를 갖는 정사각형 행렬의 크기입니다. 우리는 두 대각선 요소에서만 순회하므로 시간 복잡도는 대각선에있는 요소의 수 (2 * N), 즉 O (N)와 같습니다.

공간 복잡성 

O (1) : 여기서 공간 복잡성은 추가 메모리를 사용하지 않기 때문에 일정합니다.

균열 시스템 설계 인터뷰
Translate »
1