当前位置:网站首页>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();
}
}
边栏推荐
- Juul, the American e-cigarette giant, suffered a disaster, and all products were forced off the shelves
- canvas 绘制图片
- uniapp 开发微信公众号,下拉框默认选中列表第一个
- port 22: Connection refused
- MySQL data advanced
- Indexeddb local storage, homepage optimization
- Basic operations on binary tree
- indexedDB本地存储,首页优化
- dedecms模板文件讲解以及首页标签替换
- 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
猜你喜欢
随机推荐
numpy.logical_and()
2022-06-23:给定一个非负数组,任意选择数字,使累加和最大且为7的倍数,返回最大累加和。 n比较大,10的5次方。 来自美团。3.26笔试。
卷妹带你学jdbc---2天冲刺Day1
Phpstrom code formatting settings
canvas无限扫描js特效代码
简单的价格表样式代码
canvas 绘制图片
解决Deprecated: Methods with the same name as their class will not be constructors in报错方案
Desktop software development framework reward
Dragging El table sortablejs
Three ways to use applicationcontextinitializer
操作符详解
web网站开发,图片懒加载
消息队列的作用
Cookie encryption 4 RPC method determines cookie encryption
How to standardize data center infrastructure management process
上升的气泡canvas破碎动画js特效
小程序学习之获取用户信息(getUserProfile and getUserInfo)
CVPR 2022 Oral | 英伟达提出自适应token的高效视觉Transformer网络A-ViT,不重要的token可以提前停止计算
GeoGebra 实例 时钟