当前位置:网站首页>leetCode-498: 對角線遍曆
leetCode-498: 對角線遍曆
2022-06-24 10:14:00 【文醜顏不良啊】
題目描述
給你一個大小為 m x n 的矩陣 mat ,請以對角線遍曆的順序,用一個數組返回這個矩陣中的所有元素。
示例
示例 1:
輸入:nums = [2,7,11,15], target = 9
輸出:[0,1]
解釋:因為 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2:
輸入:mat = [[1,2],[3,4]]
輸出:[1,2,3,4]
解題過程
思路及步驟
(1)m * n 的二維矩陣, 總共有 m + n - 1 條對角線, 相鄰的對角線的遍曆方向不同;
(2)設對角線從上到下的編號為 [0,m + n − 2]。當 i 為偶數時, 遍曆方向為從左下向右上遍曆;當 i 為奇數時,遍曆方向為從右上向左下遍曆;
(3)當第 i 條對角線為從左下向右上遍曆時, 即 i 為偶數時, 每次行索引减 1, 列索引加 1, 直到矩陣的邊緣為止;
當 i < m 時, 此時對角線遍曆的起點比特置為 (i, 0);
當 i ≥ m 時,此時對角線遍曆的起點比特置為 (m − 1, i − m + 1);
(4)當第 i 條對角線為從右上向左下遍曆時, 即 i 為奇數時, 每次行索引加 1, 列索引减 1, 直到矩陣的邊緣為止;
當 i < n 時, 此時對角線遍曆的起點比特置為 (0, i);
當 i ≥ n 時,則此時對角線遍曆的起點比特置為 (i − n + 1, n − 1);
代碼展示
public class FindDiagonalOrder {
/** * 官方解答: * m * n 的二維矩陣, 總共有 m + n - 1 條對角線, 相鄰的對角線的遍曆方向不同 * 設對角線從上到下的編號為 [0,m + n − 2] * 當 i 為偶數時, 遍曆方向為從左下向右上遍曆; * 當 i 為奇數時,遍曆方向為從右上向左下遍曆; * * 當第 i 條對角線為從左下向右上遍曆時, 即 i 為偶數時, 每次行索引减 1, 列索引加 1, 直到矩陣的邊緣為止; * 當 i < m 時, 此時對角線遍曆的起點比特置為 (i, 0); * 當 i ≥ m 時,此時對角線遍曆的起點比特置為 (m − 1, i − m + 1); * * 當第 i 條對角線為從右上向左下遍曆時, 即 i 為奇數時, 每次行索引加 1, 列索引减 1, 直到矩陣的邊緣為止; * 當 i < n 時, 此時對角線遍曆的起點比特置為 (0, i); * 當 i ≥ n 時,則此時對角線遍曆的起點比特置為 (i − n + 1, n − 1); **/
public int[] findDiagonalOrder(int[][] mat) {
// 行
int m = mat.length;
// 列
int n = mat[0].length;
int[] result = new int[m * n];
int index = 0;
for (int i = 0; i < m + n - 1; i++) {
if (i % 2 == 0) {
// 第偶數條對角線
int row = 0;
int line = 0;
if (i < m) {
row = i;
}
if (i >= m) {
row = m - 1;
line = i - m + 1;
}
while (row >= 0 && line < n) {
result[index] = mat[row][line];
row--;
line++;
index++;
}
} else {
// 第奇數條對角線
int row = 0;
int line = 0;
if (i < n) {
line = i;
}
if (i >= n) {
row = i - n + 1;
line = n - 1;
}
while (row < m && line >= 0) {
result[index] = mat[row][line];
row++;
line--;
index++;
}
}
}
return result;
}
public static void main(String[] args) {
int[][] mat = {
{
1,2,3},
{
4,5,6},
{
7,8,9}};
int[] result = new FindDiagonalOrder().findDiagonalOrder(mat);
for (int i = 0; i < result.length; i++) {
System.out.printf("%2d", result[i]);
}
System.out.println();
}
}
边栏推荐
猜你喜欢
3.员工的增删改查
indexedDB本地存储,首页优化
Nvisual digital infrastructure operation management software platform
整理接口性能优化技巧,干掉慢代码
p5.js实现的炫酷交互式动画js特效
Using pandas to read SQL server data table
CVPR 2022 Oral | 英伟达提出自适应token的高效视觉Transformer网络A-ViT,不重要的token可以提前停止计算
机器学习——感知机及K近邻
队列Queue
小程序学习之获取用户信息(getUserProfile and getUserInfo)
随机推荐
CVPR 2022 oral | NVIDIA proposes an efficient visual transformer network a-vit with adaptive token. The calculation of unimportant tokens can be stopped in advance
numpy.linspace()
Machine learning - principal component analysis (PCA)
保健品一物一码防窜货营销软件开发
形状变化loader加载jsjs特效代码
学习使用KindEditor富文本编辑器,点击上传图片遮罩太大或白屏解决方案
p5.js千纸鹤动画背景js特效
Three ways to use applicationcontextinitializer
Top issue tpami 2022! Behavior recognition based on different data modes: a recent review
uniapp 开发微信公众号,下拉框默认选中列表第一个
读取csv(tsv)文件出错
2.登陆退出功能开发
canvas掉落的小球重力js特效动画
Binary tree part I
GeoGebra 实例 时钟
2022-06-23: given a nonnegative array, select any number to make the maximum cumulative sum a multiple of 7, and return the maximum cumulative sum. N is larger, to the 5th power of 10. From meituan. 3
Array seamless scrolling demo
涂鸦智能携多款重磅智能照明解决方案,亮相2022美国国际照明展
SQL Sever关于like操作符(包括字段数据自动填充空格问题)
Regular matching mailbox