Matrix Diagonal Sum Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe
Դասավորություն Matrix

Խնդիրի հայտարարություն

Matrix Diagonal Sum- ի խնդրում քառակուսի է matrix տրված է ամբողջ թվերի: Մենք պետք է հաշվարկենք բոլոր անկյունագծերում առկա բոլոր տարրերի հանրագումարը, այսինքն առաջնային, ինչպես նաև երկրորդական անկյունագծերի տարրերը: Յուրաքանչյուր տարր պետք է հաշվել միայն մեկ անգամ:

Օրինակ

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

Բացատրությունը.

Անկյունագծերի գումար ՝ 1 + 5 + 9 + 3 + 7 = 25
Ուշադրություն դարձրեք, որ տարրի գորգը [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.

Մոտեցում

Matrix Diagonal Sum 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-ով:

Այժմ տեսնենք երկրորդական անկյունագիծը: Առաջին շարքում առաջին տարրի ինդեքսը i = 0 է, j = n-1: Հաջորդ տարրը (i + 1.j-1) կետում է: Նմանապես վերջին տարրը գտնվում է (n-1,0) -ում:
Այսպիսով, մենք կարող ենք այս անկյունագծի վրայով կրկնել հետևյալ կերպ.

1. Նախաձեռնեք i = 0 և j = n-1:
2. Գործարկել մի օղակ մինչ ես = 0
3. Ավելացնել ընթացիկ տարրը (եթե այն չի գտնվում առաջնային անկյունագծի վրա, այսինքն. I == j): I- ի ավելացում 1-ով և j նվազում 1-ով:

Վերջապես վերադարձեք գումարը և՛ գործողությունից հետո:

Իրականացման

C ++ ծրագիր Matrix Diagonal Sum Leetcode լուծման համար

#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

Java ծրագիր Matrix Diagonal Sum Leetcode լուծման համար

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 լուծման համար

Timeամանակի բարդություն

ՎՐԱ) : Այստեղ N- ը N ^ 2 տարրեր ունեցող քառակուսի մատրիցայի չափն է: Քանի որ մենք անցնում ենք միայն անկյունագծային տարրերի վրայով, ժամանակի բարդությունը հավասար կլինի անկյունագծերում առկա տարրերի քանակին (2 * N), այսինքն ՝ O (N):

Տիեզերական բարդություն 

O (1): Այստեղ տարածության բարդությունը կայուն է, քանի որ մենք ոչ մի լրացուցիչ հիշողություն չենք օգտագործում: