前言说明
算法学习,日常刷题记录。
题目连接
题目内容
给你一个正方形矩阵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].length
1 <= n <= 100
1 <= mat[i][j] <= 100
分析过程
正方形矩阵长度为1时:
正方形矩阵长度为1正方形矩阵长度为2时:
正方形矩阵长度为2正方形矩阵长度为3时:
正方形矩阵长度为3正方形矩阵长度为4时:
正方形矩阵长度为4正方形矩阵长度为5时:
正方形矩阵长度为5正方形矩阵长度为6时:
正方形矩阵长度为6由此可以推导出,对于正方形矩阵的首行和末行,只需要取首列元素和末列元素。
对于正方形矩阵的其他行,有的行取两个列的元素,有的行只取一个列的元素。
当正方形矩阵的长度为奇数时,中间行只取一个列的元素,其他情况的行都是取两个列的元素。
当行需要取两个列的元素时,第一个元素的下标和行的下标一致,第二个元素的下标刚好是以列长度的中间数作为镜子的对称下标,可以通过这一行的末列下标减去第一个元素的下标得到第二个元素的下标。
所以思路就是,遍历正方形矩阵的每一行,每一行取出符合条件的元素,元素相加得出矩阵对角线元素的和。
解答代码
class Solution {
public int diagonalSum(int[][] mat) {
// 定义总和
int sum = 0;
// 定义正方形矩阵长度
int length = mat.length;
// 遍历正方形矩阵的行
for (int i = 0; i < length; ++i) {
if (i == 0 || i == length - 1) {
// 首行和末行,取首列和末列
if (length > 1) {
// 若长度大于1,首列和末列不是同一列
sum += mat[i][0];
sum += mat[i][length - 1];
} else {
// 若长度小于等于1,首列和末列是同一列
sum += mat[i][0];
}
} else {
// 非首行和末行,取和行相同下标的列,以及以列长度中间数作为分隔,此列对面的列
if (length % 2 != 0 && length / 2 == i) {
// 若是中间行,这种列只有一个,行长度为奇数的才有中间行
sum += mat[i][length / 2];
} else {
// 若不是中间行,这种列有两个,两列刚好对称
sum += mat[i][i];
sum += mat[i][length - 1 - i];
}
}
}
return sum;
}
}
提交结果
时间击败100%的用户,空间击败96.48%的用户。
运行结果原文链接
公众号:纯洁编程说(chunjie_tech)
网友评论