Matrix Diagonal Sum Leetcode Solution ແກ້ໄຂບັນຫາ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe
Array ມາຕຣິກເບື້ອງ

ຖະແຫຼງການບັນຫາ

ໃນ Matrix Diagonal Sum ມີບັນຫາຮຽບຮ້ອຍ matrix ຂອງຕົວເລກແມ່ນໃຫ້. ພວກເຮົາຕ້ອງຄິດໄລ່ຜົນລວມຂອງທຸກໆອົງປະກອບທີ່ ນຳ ສະ ເໜີ ຢູ່ເສັ້ນຂວາງຂອງມັນ. ແຕ່ລະອົງປະກອບຄວນຈະຖືກນັບພຽງຄັ້ງດຽວ.

ຍົກຕົວຢ່າງ

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

ຄໍາອະທິບາຍ:

ແຜນວາດການສະແດງຜົນ: 1 + 5 + 9 + 3 + 7 = 25
ສັງເກດວ່າ mat 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.

ວິທີການ

Matrix Diagonal Sum Leetcode Solution ແກ້ໄຂບັນຫາ

ໃນຕາຕະລາງສີ່ຫລ່ຽມທີ່ໃຫ້ໄວ້ພວກເຮົາພຽງແຕ່ເພີ່ມສ່ວນປະກອບຂອງເສັ້ນຂວາງແລະສົ່ງຄືນຜົນລວມຂອງມັນ.
ສາມາດເຮັດໃຫ້ເບິ່ງສິ່ງທີ່ຈະເປັນຮູບແບບການຊີ້ບອກໃນຕາຕະລາງ ສຳ ລັບອົງປະກອບຂອງເສັ້ນຂວາງ. ຫນ້າທໍາອິດຖ້າພວກເຮົາເຫັນໃນເສັ້ນຂວາງ, ອົງປະກອບທໍາອິດຂອງມັນແມ່ນຢູ່ໃນດັດຊະນີ i = 0, j = 0 ແລະອົງປະກອບຕໍ່ໄປແມ່ນຢູ່ (i + 1, j + 1). ອົງປະກອບສຸດທ້າຍທີ່ຄ້າຍຄືກັນນີ້ຈະຢູ່ໃນດັດຊະນີ (n-1, n-1) ບ່ອນທີ່ n ແມ່ນຄວາມກວ້າງຂອງຕາຕະລາງສີ່ຫລ່ຽມທີ່ໄດ້ຮັບ. ຕົວຊີ້ບອກທັງ ໝົດ ໃນເສັ້ນຂວາງນີ້ມີ i = j.
ດັ່ງນັ້ນພວກເຮົາສາມາດປັບປ່ຽນເສັ້ນຂວາງໃນວົງຈອນດັ່ງຕໍ່ໄປນີ້:

1. ເບື້ອງຕົ້ນ i = 0 ແລະ j = 0.
2. ດໍາເນີນການ loop ໃນຂະນະທີ່ i
3. ຕື່ມອົງປະກອບປັດຈຸບັນ. ການເພີ່ມຂື້ນ i ແລະ j ທັງສອງໂດຍ 1.

ດຽວນີ້ສາມາດເບິ່ງເຫັນເສັ້ນຂວາງສອງ. ດັດຊະນີຂອງອົງປະກອບ ທຳ ອິດໃນແຖວ ທຳ ອິດແມ່ນ i = 0, j = n-1. ອົງປະກອບຕໍ່ໄປແມ່ນຢູ່ (i + 1.j-1). ອົງປະກອບສຸດທ້າຍທີ່ຄ້າຍຄືກັນແມ່ນຢູ່ທີ່ (n-1,0).
ດັ່ງນັ້ນພວກເຮົາສາມາດປັບປ່ຽນເສັ້ນຂວາງໃນວົງຈອນດັ່ງຕໍ່ໄປນີ້:

1. ຂໍ້ລິເລີ່ມ i = 0 ແລະ j = n-1.
2. ດໍາເນີນການ loop ໃນຂະນະທີ່ 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

Java Program ສຳ ລັບ Matrix Diagonal Sum Leetcode Solution

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 Solution

ຄວາມສັບສົນເວລາ

O (N): ນີ້ N ແມ່ນຂະ ໜາດ ຂອງຕາຕະລາງສີ່ຫຼ່ຽມມົນມີ N ^ 2 ອົງປະກອບ. ໃນຂະນະທີ່ພວກເຮົາ ກຳ ລັງເດີນທາງໄປທັງສອງອົງປະກອບທາງຂວາງ, ຄວາມສັບສົນເວລາຈະເທົ່າກັບ ຈຳ ນວນຂອງອົງປະກອບທີ່ສະແດງຢູ່ເສັ້ນຂວາງ (2 * N), ເຊັ່ນ: O (N).

ຄວາມສັບສົນໃນອະວະກາດ 

O (1): ທີ່ນີ້ຄວາມສັບສົນໃນພື້ນທີ່ແມ່ນຄົງທີ່ຍ້ອນວ່າພວກເຮົາບໍ່ໄດ້ໃຊ້ ໜ່ວຍ ຄວາມ ຈຳ ພິເສດໃດໆ.