江山集团网站建设,变更icp备案网站信息查询,dedecms 一键更新网站,wordpress文章详情页给你一个正方形矩阵 mat#xff0c;请你返回矩阵对角线元素的和。
请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。 示例 1#xff1a; 输入#xff1a;mat [[1,2,3],[4,5,6],[7,8,9]]
输出#xff1a;25
解释#xff1a;对角线的和为#xff…
给你一个正方形矩阵 mat请你返回矩阵对角线元素的和。
请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。 示例 1 输入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].length1 n 1001 mat[i][j] 100
通过次数
63.3K
提交次数
75.9K
通过率
83.3%
一、信息
1.给一个正方型矩阵mat
2.返回矩阵对角线元素的和
二、分析
条件1和条件2告诉我此次的目的
问题1该如何求和呢
根据我的思考步骤
第一步 观察在矩阵中对角线元素的下标特征
通过观察我发现主对角线上数组元素的下标都满足ij
副对角线都满足n-100n-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.hint 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: 25return 0;
}
### C 语言实现
#include vector
#include iostreamint diagonalSum(std::vectorstd::vectorint 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::vectorstd::vectorint mat1 {{1,2,3}, {4,5,6}, {7,8,9}};std::cout diagonalSum(mat1) std::endl; // Output: 25return 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) 处于对角线上则一定满足下列条件之一
iji jij ijn−1i j n - 1ijn−1 根据上述结论我们可以遍历整个矩阵如果当前坐标 (i,j)(i, j)(i,j) 满足 iji jij 或者 ijn−1i j n - 1ijn−1 则表示该位置一定在对角线上则把当前的数字加入到答案之中。
class Solution {
public:int diagonalSum(vectorvectorint 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(vectorvectorint 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. **问题解决技能的培养**整体来说解决这种问题可以帮助我们培养分析问题和找到有效解决方案的技能。
