ម៉ាទ្រីសឌុយតេលាហ្សែនស៊ែរសឹបផ្លេយ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ កម្មវិធី Adob ​​e
អារេ ម៉ាទ្រីស

សេចក្តីថ្លែងការណ៍បញ្ហា។

នៅក្នុងម៉ាទ្រីសអង្កត់ទ្រូងមានបញ្ហាការ៉េ ម៉ាទ្រីស នៃចំនួនគត់ត្រូវបានផ្តល់ឱ្យ។ យើងត្រូវគណនាផលបូកនៃធាតុទាំងអស់ដែលមាននៅអង្កត់ទ្រូងរបស់វាពោលគឺធាតុនៅអង្កត់ទ្រូងបឋមក៏ដូចជាអង្កត់ទ្រូងបន្ទាប់បន្សំ។ ធាតុនីមួយៗគួរតែត្រូវបានរាប់បញ្ចូលតែម្តង។

ឧទាហរណ៍

mat = [[1,2,3],
       [4,5,6],
       [7,8,9]]
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. ដំណើរការរង្វិលជុំខណៈពេលដែលខ្ញុំ
3. បន្ថែមធាតុបច្ចុប្បន្ន។ បង្កើន I និង j ទាំងពីរដោយ ១ ។

ឥឡូវនេះអនុញ្ញាតឱ្យមើលឃើញសម្រាប់អង្កត់ទ្រូងអនុវិទ្យាល័យ។ សន្ទស្សន៍នៃធាតុទីមួយនៅក្នុងជួរទីមួយគឺ i = 0, j = n-1 ។ ធាតុបន្ទាប់គឺនៅ (i + 1.j-1) ។ ស្រដៀងគ្នានេះដែរធាតុចុងក្រោយគឺនៅ (n-1,0) ។
ដូច្នេះយើងអាចនិយាយអំពីអង្កត់ទ្រូងនេះតាមរង្វាស់ដូចខាងក្រោមៈ

1. គំនិតផ្តួចផ្តើម I = 0 និង j = n-1 ។
2. ដំណើរការរង្វិលជុំខណៈពេលដែលខ្ញុំ = ០ ។
3. បន្ថែមធាតុបច្ចុប្បន្ន (ប្រសិនបើវាមិនកុហកលើអង្កត់ទ្រូងបឋមពោលគឺ i == ច) ។ បង្កើន I ដោយ 1 និងការថយចុះ j ដោយ 1 ។

ទីបំផុតត្រឡប់ផលបូកបន្ទាប់ពីប្រតិបត្តិការទាំងពីរ។

ការអនុវត្តន៍

កម្មវិធី 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

ជ្វាកម្មវិធីសំរាប់ដំណោះស្រាយម៉ាទ្រីសឌុយតេស៊ែរ 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

ការវិភាគស្មុគស្មាញសម្រាប់ដំណោះស្រាយម៉ាទ្រីសឌុយទែរស៊ែរ Leetcode

ស្មុគស្មាញពេលវេលា

O (N)៖ នៅទីនេះ N គឺជាទំហំនៃម៉ាទ្រីសការ៉េដែលមានធាតុ N ^ ២ ។ នៅពេលយើងកំពុងឆ្លងកាត់ធាតុអង្កត់ទ្រូងទាំងពីរភាពស្មុគស្មាញពេលវេលានឹងស្មើនឹងចំនួនធាតុដែលមាននៅអង្កត់ទ្រូង (២ * អិន) ពោលគឺអូ (អិន) ។

ភាពស្មុគស្មាញនៃលំហ 

O (១)៖ នៅទីនេះភាពស្មុគស្មាញនៃលំហគឺថេរដូចដែលយើងមិនបានប្រើការចងចាំបន្ថែមទេ។