න්‍යාස විකර්ණ එකතුව ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇෙබෝ
අරා නියමයන්

ගැටළු ප්රකාශය

Matrix diagonal Sum ගැටලුවේදී වර්ගයක් අනුකෘතියයි පූර්ණ සංඛ්‍යා ලබා දී ඇත. එහි විකර්ණවල ඇති සියලුම මූලද්‍රව්‍යයන්ගේ එකතුව එනම් ප්‍රාථමික විකර්ණ මෙන්ම ද්විතියික විකර්ණවල එකතුව ගණනය කළ යුතුය. සෑම අංගයක්ම ගණනය කළ යුත්තේ එක් වරක් පමණි.

උදාහරණයක්

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.

ප්රවේශය

න්‍යාස විකර්ණ එකතුව ලීට්කෝඩ් විසඳුම

ලබා දී ඇති වර්ග අනුකෘතියේ දී අපට කළ යුත්තේ විකර්ණ මූලද්‍රව්‍ය එකතු කර එහි එකතුව ආපසු ලබා දීම ය.
විකර්ණ මූලද්‍රව්‍ය සඳහා අනුකෘතියේ දර්ශක රටාව කුමක් දැයි බලමු. පළමුව අපි ප්‍රාථමික විකර්ණයෙහි දුටුවහොත්, එහි පළමු මූලද්‍රව්‍යය දර්ශකය i = 0, j = 0 සහ ඊළඟ මූලද්‍රව්‍යය (i + 1, j + 1) මත වේ. එලෙසම අවසාන මූලද්‍රව්‍යය දර්ශකයේ (n-1, n-1) ඇති අතර n යනු දී ඇති වර්ග අනුකෘතියේ පළල වේ. මෙම විකර්ණයේ ඇති සියලුම දර්ශකවල i = j ඇත.
එබැවින් අපට මෙම විකර්ණය හරහා ලූපයකින් පහත පරිදි දැක්විය හැකිය:

1. i = 0 සහ j = 0 ආරම්භ කරන්න.
2. i අතර ලූපයක් ධාවනය කරන්න
3. වත්මන් මූලද්රව්යය එකතු කරන්න. I සහ j යන දෙකම 1 කින් වැඩි කිරීම.

දැන් ද්විතියික විකර්ණය සඳහා බලමු. පළමු පේළියේ පළමු මූලද්‍රව්‍යයේ දර්ශකය i = 0, j = n-1 වේ. ඊළඟ අංගය (i + 1.j-1) වේ. එලෙසම අවසාන මූලද්‍රව්‍යය (n-1,0) වේ.
එබැවින් අපට මෙම විකර්ණය හරහා ලූපයෙන් නැවත කියවිය හැකිය:

1. i = 0 සහ j = n-1 ආරම්භ කරන්න.
2. i අතර ලූපයක් ධාවනය කරන්න = 0.
3. වත්මන් මූලද්‍රව්‍යය එක් කරන්න (එය ප්‍රාථමික විකර්ණය මත නොපවතී නම්, එනම් i == j). I 1 කින් වැඩි කිරීම සහ j 1 කින් අඩු කිරීම.

මෙහෙයුමෙන් පසුව මුදල ආපසු එවන්න.

ක්රියාත්මක කිරීම

C ++ වැඩසටහන Matrix Diagonal Sum Leetcode Solution සඳහා

#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

මැට්‍රික්ස් විකර්ණ එකතුව ලීට්කෝඩ් විසඳුම සඳහා ජාවා වැඩසටහන

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

අනුකෘති විකර්ණ එකතුව ලීට්කෝඩ් විසඳුම සඳහා සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත) : මෙහි N යනු N ^ 2 මූලද්‍රව්‍ය සහිත වර්ග අනුකෘතියේ ප්‍රමාණයයි. අප විකර්ණ මූලද්‍රව්‍ය දෙකටම ගමන් කරන බැවින්, කාල සංකීර්ණත්වය විකර්ණ (2 * N), එනම් O (N) හි ඇති මූලද්‍රව්‍ය ගණනට සමාන වේ.

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (1): අප කිසිදු අමතර මතකයක් භාවිතා නොකරන බැවින් මෙහි අවකාශයේ සංකීර්ණතාව නියත ය.