Leetcode 1572.矩阵对角线元素之和

这篇具有很好参考价值的文章主要介绍了Leetcode 1572.矩阵对角线元素之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Leetcode 1572.矩阵对角线元素之和,【Letcode】每日一题,算法,leetcode,C++,java

给你一个正方形矩阵 mat,请你返回矩阵对角线元素的和。

请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。

示例  1:

Leetcode 1572.矩阵对角线元素之和,【Letcode】每日一题,算法,leetcode,C++,java

输入:mat = [[1,2,3],
            [4,5,6],
            [7,8,9]]
输出:25
解释:对角线的和为:1 + 5 + 9 + 3 + 7 = 25
请注意,元素 mat[1][1] = 5 只会被计算一次。

示例  2:

输入:mat = [[1,1,1,1],
            [1,1,1,1],
            [1,1,1,1],
            [1,1,1,1]]
输出:8

示例 3:

输入:mat = [[5]]
输出:5

提示:

  • n == mat.length == mat[i].length
  • 1 <= n <= 100
  • 1 <= mat[i][j] <= 100

通过次数

63.3K

提交次数

75.9K

通过率

83.3%

一、信息

1.给一个正方型矩阵mat

2.返回矩阵对角线元素的和

二、分析

条件1和条件2:告诉我此次的目的

问题1:该如何求和呢

根据我的思考步骤

第一步 观察在矩阵中对角线元素的下标特征

通过观察我发现主对角线上数组元素的下标都满足i=j

副对角线都满足(n-1,0)(0,n-1)即关于主对角线对称,我觉得我该回去修一下线性代数了。

第二步 我们通过for循环实现累加,if选择语句结构来筛选。

问题出现1:对了题目并没有说矩阵是几×几的矩阵所以还得测算矩阵的大小

问题出现该如何测算矩阵的大小

已知测算矩阵长度的是length函数。

答案:

Leetcode答案:

int n = mat.size(), sum = 0;

问题出现2:根据题目我们不难发现不仅我们要计算该二维数组的大小还要开辟动态的空间,这在C++该怎么办呢?

很简答其实用vector即可,如果不记得可以看文章(知识不足的地方)

不知道陷入了停滞

我的答案:

我的答案:

首先我们可以分析这个问题如下:

1. **思考过程**:
   - 我们需要计算主对角线和副对角线上的元素和。主对角线上的元素位置是`mat[i][i]`,副对角线上的元素位置是`mat[i][n-1-i]`。
   - 如果矩阵的尺寸是奇数,则中心元素会被计算两次,我们需要减去一次。
   
2. **分析过程**:
   - 我们可以通过一个循环从 0 到 n-1 来遍历所有的行(或列),然后计算对角线元素的和。
   - 如果 n 是奇数,我们减去一次`mat[n/2][n/2]`。

现在我们可以将这个逻辑实现为 C、C++ 和 Java 程序:

### C 语言实现

#include <stdio.h>

int diagonalSum(int** mat, int matSize, int* matColSize){
    int sum = 0;
    for(int i = 0; i < matSize; i++){
        sum += mat[i][i] + mat[i][matSize - 1 - i];
    }
    if(matSize % 2 == 1){
        sum -= mat[matSize / 2][matSize / 2];
    }
    return sum;
}

int main() {
    int mat1[3][3] = {{1,2,3}, {4,5,6}, {7,8,9}};
    int* mat1_ptr[3] = {mat1[0], mat1[1], mat1[2]};
    printf("%d\n", diagonalSum(mat1_ptr, 3, NULL)); // Output: 25
    return 0;
}

### C++ 语言实现

#include <vector>
#include <iostream>

int diagonalSum(std::vector<std::vector<int>>& mat) {
    int sum = 0;
    int n = mat.size();
    for(int i = 0; i < n; i++) {
        sum += mat[i][i] + mat[i][n - 1 - i];
    }
    if(n % 2 == 1) {
        sum -= mat[n / 2][n / 2];
    }
    return sum;
}

int main() {
    std::vector<std::vector<int>> mat1 = {{1,2,3}, {4,5,6}, {7,8,9}};
    std::cout << diagonalSum(mat1) << std::endl; // Output: 25
    return 0;
}

### Java 语言实现

public class Main {
    public static int diagonalSum(int[][] mat) {
        int sum = 0;
        int n = mat.length;
        for(int i = 0; i < n; i++) {
            sum += mat[i][i] + mat[i][n - 1 - i];
        }
        if(n % 2 == 1) {
            sum -= mat[n / 2][n / 2];
        }
        return sum;
    }

    public static void main(String[] args) {
        int[][] mat1 = {{1,2,3}, {4,5,6}, {7,8,9}};
        System.out.println(diagonalSum(mat1)); // Output: 25
    }
}

每种语言的实现都遵循了我们的原始分析和设计,结合了相应语言的特性和语法来实现目标功能。

Leetcode题解:

方法一:遍历矩阵 思路与算法

我们知道矩阵中某个位置 (i,j)(i,j)(i,j) 处于对角线上,则一定满足下列条件之一:

i=ji = ji=j;
i+j=n−1i + j = n - 1i+j=n−1;
根据上述结论,我们可以遍历整个矩阵,如果当前坐标 (i,j)(i, j)(i,j) 满足 i=ji = ji=j 或者 i+j=n−1i + j = n - 1i+j=n−1 则表示该位置一定在对角线上,则把当前的数字加入到答案之中。

class Solution {
public:
    int diagonalSum(vector<vector<int>>& mat) {
        int n = mat.size(), sum = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j || i + j == n - 1) {
                    sum += mat[i][j];
                }
            }
        }
        return sum;
    }
};

C:

int diagonalSum(int** mat, int matSize, int* matColSize) {
    int n = matSize, sum = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j || i + j == n - 1) {
                sum += mat[i][j];
            }
        }
    }
    return sum;
}

JAVA:

class Solution {
    public int diagonalSum(int[][] mat) {
        int n = mat.length, sum = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j || i + j == n - 1) {
                    sum += mat[i][j];
                }
            }
        }
        return sum;
    }
}

 

方法二:枚举对角线元素 思路与算法

逐行遍历,记当前的行号为 iii,则当前行中处于对角线的元素为: 坐标 (i,i)(i, i)(i,i) 和坐标 (i,n−i−1)(i, n - i - 1)(i,n−i−1),因此我们把 (i,i)(i, i)(i,i) 与 (i,n−i−1)(i, n - i - 1)(i,n−i−1) 处的数字加入到答案中。 如果 nnn 是奇数的话,则主对角线与副对角线存在交点 (⌊n2⌋,⌊n2⌋)(\lfloor \dfrac{n}{2} \rfloor,\lfloor \dfrac{n}{2} \rfloor)(⌊ 
2
n

 ⌋,⌊ 
2
n

 ⌋),该点会被计算两次。所以当 nnn 为奇数的时候,需要减掉交点处的值。

C++: 

class Solution {
public:
    int diagonalSum(vector<vector<int>>& mat) {
        int n = mat.size(), sum = 0, mid = n / 2;
        for (int i = 0; i < n; ++i) {
            sum += mat[i][i] + mat[i][n - 1 - i];
        }
        return sum - mat[mid][mid] * (n & 1);
    }
};

总结:

从这道题目中,我们可以学到以下几点:

1. **数组索引的应用**:该题目教会我们如何利用数组索引来找到主对角线和副对角线的元素。这对于深入理解数组索引和二维数组非常有帮助。

2. **循环的优化**:我们可以通过仔细设计循环来减少不必要的计算。例如,方法二比方法一更优,因为它避免了遍历整个数组,而是只关注于对角线元素。

3. **条件运算符的使用**:该题目展示了如何使用条件运算符(如`&`用于检测奇偶性)来简化代码和减少计算。

4. **复杂度分析**:通过比较两种方法,我们可以学习到如何通过减少循环次数和减少重复计算来降低算法的时间复杂度。

5. **编程语言的特性**:通过用多种编程语言(C, C++ 和 Java)来解这个问题,我们可以学习和比较不同语言中数组和循环结构的不同实现和语法。

6. **数学应用在编程中**:这个问题也是一个很好的例子,展示了数学(特别是线性代数)在编程和算法设计中的应用。

7. **代码测试与调试**:实现代码后,我们可以创建多种测试用例来验证代码的正确性和效率,从而提高我们的测试和调试技能。

8. **问题解决技能的培养**:整体来说,解决这种问题可以帮助我们培养分析问题和找到有效解决方案的技能。

Leetcode 1572.矩阵对角线元素之和,【Letcode】每日一题,算法,leetcode,C++,java文章来源地址https://www.toymoban.com/news/detail-695837.html

到了这里,关于Leetcode 1572.矩阵对角线元素之和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 1572. 矩阵对角线元素的和

    给你一个正方形矩阵 mat,请你返回矩阵对角线元素的和。 请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。 同时求对角线和副对角线上元素的和再减去重合的元素

    2024年02月13日
    浏览(40)
  • 【1572. 矩阵对角线元素的和】

    来源:力扣(LeetCode) 描述: 给你一个正方形矩阵 mat ,请你返回矩阵对角线元素的和。 请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。 示例 1: 示例 2: 示例 3: 提示: n == mat.length == mat[i].length 1 = n = 100 1 = mat[i][j] = 100 方法一:遍历矩阵 思路

    2024年02月12日
    浏览(39)
  • 【每日一题】1572. 矩阵对角线元素的和

    给你一个正方形矩阵 mat,请你返回矩阵对角线元素的和。 请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。 示例 1: 示例 2: 示例 3: 提示: n == mat.length == mat[i].length 1 = n = 100 1 = mat[i][j] = 100 思路:主对角线i=j,副对角线i+j=n-1。

    2024年02月13日
    浏览(52)
  • 【每日一题Day292】LC1572矩阵对角线元素的和 模拟

    思路 简单模拟,主对角线的元素横纵坐标相等,副对角线的元素横纵坐标相加为n-1,注意避免重复计算 实现 复杂度 时间复杂度: O ( log ⁡ n ) mathcal{O}(log n) O ( lo g n ) 空间复杂度: O ( 1 ) mathcal{O}(1) O ( 1 )

    2024年02月13日
    浏览(39)
  • 【力扣每日一题】1572. 矩阵对角线元素的和 & 8.11打卡

    1572. 矩阵对角线元素的和 难度: 简单 描述: 给你一个正方形矩阵 mat,请你返回矩阵对角线元素的和。 请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。 返回合并后的二叉树。 注意: 合并过程必须从两个树的根节点开始。 示例 1: 输入:mat = [

    2024年02月12日
    浏览(36)
  • C创建一个4x4的矩阵,显示该矩阵。求该矩阵的外围元素之和、主对角线元素之和以及副对角线元素之和。

            编写程序,创建一个4x4的矩阵,矩阵的值为{{1,2,4,5},{6,7,8,9},{10,11,12,13},{14,15,16,17}},显示该矩阵。求该矩阵的外围元素之和、主对角线元素之和以及副对角线元素之和。         求三类元素的和,可以定义3 个不同的和变量,在遍历数组元素的循环中通过三次条件

    2024年02月11日
    浏览(48)
  • 输入一个n×n的矩阵,分别计算该矩阵主对角线元素与副对角线元素之和。

    输入格式: 输入包含n + 1行: 第一行为一个正整数n(1 = n = 10)。 第二行到第n + 1行,每行有n个整数,邻近两数之间用一个空格隔开。 输出格式: 两数之间用一个空格隔开。 输入样例: 4 2 3 4 1 5 6 2 1 7 1 8 3 1 6 1 1 输出样例: 17 5

    2024年02月11日
    浏览(50)
  • 求一个3*3矩阵对角线元素之和

    #includestdio.h #includestring.h int main() {     int m, n, j, k,sum=0;     int a[10][10];     for (m = 0; m 3; m++)     {         for (n = 0; n 3; n++)         {             scanf(\\\"%d\\\", a[m][n]);         }     }     for (m = 0; m 3; m++)     {         for (n = 0; n 3; n++)         {          

    2024年02月03日
    浏览(46)
  • 【证明】矩阵特征值之和等于主对角线元素之和

    性质 1 设 n n n 阶矩阵 A = ( a i j ) boldsymbol{A} = (a_{ij}) A = ( a ij ​ ) 的特征值为 λ 1 , λ 2 , ⋯   , λ n lambda_1,lambda_2,cdots,lambda_n λ 1 ​ , λ 2 ​ , ⋯ , λ n ​ ,则 λ 1 + λ 2 + ⋯ + λ n = a 11 + a 22 + ⋯ + a n n lambda_1 + lambda_2 + cdots + lambda_n = a_{11} + a_{22} + cdots + a_{nn} λ 1 ​ + λ 2 ​

    2024年02月04日
    浏览(54)
  • C语言程序设计:求矩阵主对角线和副对角线元素之和

    题目内容: 求5行5列矩阵的主对角线和副对角线元素之和。 输入格式: \\\"%d\\\" 输出格式: \\\"sum=%d\\\" 输入样例: 1 2 3 4 3 2 3 4 1 6 3 4 5 6 7 4 2 6 7 8 1 6 7 8 9 输出样例: sum=37 时间限制:500ms内存限制:32000kb

    2024年02月13日
    浏览(62)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包