LeetCode题解498. 对角线遍历

给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。

 

示例:

输入:

[

[ 1, 2, 3 ],

[ 4, 5, 6 ],

[ 7, 8, 9 ]

]

输出: [1,2,4,7,5,3,6,8,9]

解释:

 

说明:

给定矩阵中的元素总数不会超过 100000 。

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/diagonal-traverse

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解:## Python Solution

对于

1 2 3
4 5 6
7 8 9

我们不考虑换方向,假设题目不要求我们变换方向,对于上图我们的遍历结果就是:

1
2 4
3 5 7
6 8
9

这种做法比较简单,我们只要找出每一次需要遍历的起始元素,然后不断找到左下角,直到越界即可。

然后我们回到题目的要求,题目要求我们不断变换次序,那么一种简单的做法就是对于偶数次遍历我们都进行一次反转即可。如上:

1 (reverse)
2 4
7 5 3 (reverse)
6 8
9 (reverse)

## Code

```python
#
# @lc app=leetcode.cn id=498 lang=python3
#
# [498] 对角线遍历
#

# @lc code=start

class Solution:
# 1 2 3
# 4 5 6
# 7 8 9
def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
direction = 'UP'
m = len(matrix)
if m == 0:
return []
n = len(matrix[0])
temp = []
res = []
for j in range(n):
i = 0
direction = 'DOWN' if direction == 'UP' else 'UP'
while i = 0:
temp.append(matrix[i][j])
i += 1
j -= 1
if direction == 'DOWN':
temp.reverse()
res += temp
temp = []
for i in range(1, m):
j = n - 1
direction = 'DOWN' if direction == 'UP' else 'UP'
while i = 0:
temp.append(matrix[i][j])
i += 1
j -= 1
if direction == 'DOWN':
temp.reverse()
res += temp
temp = []
return res

# @lc code=end
```

LeetCode题解计算机为什么是基于二进制的?

可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制

LeetCode题解深度优先遍历和回溯的关系?

深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。

LeetCode题解盲人买袜子。

他们都各自买了两对黑袜和两对白袜,八对袜子的布质、大小完全相同,而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢?题解:暴力破解, 把袜子都拆开 一人一只 哈哈

LeetCode题解分鸡块

外卖鸡块分别有 4,6,12 块, 每 固定块数不能分开装, 用户给一个数字, 要求返回满足用户订单(可以等于也可以大于)的最少的盒数的组合

LeetCode题解10个小球,随机分到12个盒子里,求恰好10个盒子都为空的概率。

10个小球,随机分到12个盒子里,求恰好10个盒子都为空的概率。要求用程序模拟十万次,暴力求出该概率来自:字节跳动 算法工程师一面的第一题 (3月30日,60分钟,牛客网视频面)https://www.nowcoder.com/discuss/395924