Skip to content

Commit efe1beb

Browse files
daachengdaacheng
committed
更新md
更新md
1 parent 165cc33 commit efe1beb

6 files changed

Lines changed: 206 additions & 2 deletions

File tree

‎leetcode_array/main.md‎

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -37,5 +37,8 @@
3737
35. [寻找数组的中心索引](寻找数组的中心索引.md)
3838
36. [至少是其他数字两倍的最大数](至少是其他数字两倍的最大数.md)
3939
37. [托普利茨矩阵](托普利茨矩阵.md)
40-
38. [ 较大分组的位置]( 较大分组的位置.md)
41-
39. [ 翻转图像]( 翻转图像.md)
40+
38. [较大分组的位置](较大分组的位置.md)
41+
39. [翻转图像](翻转图像.md)
42+
40. [矩阵中的幻方](矩阵中的幻方.md)
43+
41. [转置矩阵](转置矩阵.md)
44+
42. [单调数列](单调数列.md)

‎leetcode_array/单调数列.md‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
如果数组是单调递增或单调递减的，那么它是单调的。
2+
如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。 如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。
3+
当给定的数组 A 是单调数组时返回 true，否则返回 false。
4+
示例：
5+
```python
6+
输入：[1,2,2,3]
7+
输出：true
8+
9+
输入：[1,3,2]
10+
输出：false
11+
```
12+
13+
#### 分析：
14+
* 如果数组是单调的，那一定是有序的(正序或者倒序)
15+
* 排序后进行比较就可以了
16+
17+
代码：
18+
```python
19+
def isMonotonic(A):
20+
if A == sorted(A) or A == sorted(A, reverse=True):
21+
return True
22+
return False
23+
```
24+
#### 方法二：
25+
```python
26+
# all()函数用于判断给定的可迭代参数iterable中的所有元素是否都为TRUE
27+
def isMonotonic(A):
28+
return all([A[i] <= A[i+1] for i in range(len(A)-1)]) \
29+
or all([A[i] >= A[i+1] for i in range(len(A)-1)])
30+
```

‎leetcode_array/按奇偶排序数组.md‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。
2+
你可以返回满足此条件的任何数组作为答案。
3+
示例：
4+
```python
5+
输入：[3,1,2,4]
6+
输出：[2,4,3,1]
7+
输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。
8+
```
9+
10+
#### 分析：单指针
11+
原地修改数组，遍历数组，当遇到第一个偶数时，就把这个偶数放在数组第一个位置，当遇到第二个偶数，就把这个偶数放在数组第二个位置。
12+
13+
```python
14+
def sortArrayByParity(A):
15+
i = 0
16+
for index, item in enumerate(A):
17+
if item%2 == 0:
18+
A[i], A[index] = item, A[i]
19+
i += 1
20+
return A
21+
```

‎leetcode_array/矩阵中的幻方.md‎

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。
2+
给定一个由整数组成的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。
3+
示例：
4+
5+
```python
6+
输入: [[4,3,8,4],
7+
[9,5,1,9],
8+
[2,7,6,2]]
9+
输出: 1
10+
解释:
11+
下面的子矩阵是一个 3 x 3 的幻方：
12+
438
13+
951
14+
276
15+
而这一个不是：
16+
384
17+
519
18+
762
19+
总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。
20+
```
21+
22+
#### 分析：
23+
* 找出所有3*3的矩阵
24+
* 判断是否有重复
25+
* 判断是否在1-9之间
26+
* 判断和是否相等
27+
28+
#### 方法一：最笨的方法
29+
```python
30+
def numMagicSquaresInside(grid):
31+
rows = len(grid)
32+
columns = len(grid[0])
33+
if rows < 3 or columns < 3:
34+
return 0
35+
36+
all_list_3_3 = []
37+
for r in range(0, rows-2):
38+
for c in range(0, columns-2):
39+
# 判断有没有重复的
40+
if len(set(grid[r][c:c + 3] + grid[r+1][c:c+3] + grid[r+2][c:c+3])) != 9:
41+
continue
42+
# 判断元素在1-9之间
43+
is_can = True
44+
for i in range(0, 3):
45+
if not (1 <= grid[r][c:c + 3][i] <= 9 and
46+
1 <= grid[r+1][c:c + 3][i] <= 9 and
47+
1 <= grid[r+2][c:c + 3][i] <= 9):
48+
is_can = False
49+
break
50+
if is_can:
51+
list_3_3 = []
52+
list_3_3.append(grid[r][c:c+3])
53+
list_3_3.append(grid[r+1][c:c+3])
54+
list_3_3.append(grid[r+2][c:c+3])
55+
all_list_3_3.append(list_3_3)
56+
count = 0
57+
for list_3_3 in all_list_3_3:
58+
if sum(list_3_3[0]) == sum(list_3_3[1]) == sum(list_3_3[2]):
59+
col_sum_1 = list_3_3[0][0] + list_3_3[1][0] + list_3_3[2][0]
60+
col_sum_2 = list_3_3[0][1] + list_3_3[1][1] + list_3_3[2][1]
61+
col_sum_3 = list_3_3[0][2] + list_3_3[1][2] + list_3_3[2][2]
62+
if col_sum_1 == col_sum_2 == col_sum_3:
63+
diag_sum_1 = list_3_3[0][0] + list_3_3[1][1] + list_3_3[2][2]
64+
diag_sum_2 = list_3_3[0][2] + list_3_3[1][1] + list_3_3[2][0]
65+
if diag_sum_1 == diag_sum_2:
66+
count += 1
67+
68+
return count
69+
```
70+
71+
#### 方法二：分析规律
72+
```python
73+
# 网格的总和是 45，因为网格必须是 1 到 9 不同的数字。
74+
# 每一列和行加起来必须是 15，乘以 3 则是网格的总和。
75+
# 对角线的和也必须是 15，题目中说了对角线与列，行的和相同。
76+
# 将四条穿过中心的线的 12 个值相加（即一行一列两条对角线），
77+
# 这四条线加起来等于 60；而整个网格加起来为 45。
78+
# 则中心等于 （60-45）/3 = 5
79+
def numMagicSquaresInside(grid):
80+
rows = len(grid)
81+
columns = len(grid[0])
82+
if rows < 3 or columns < 3:
83+
return 0
84+
85+
def magic(a, b, c, d, e, f, g, h, i):
86+
if (sorted([a, b, c, d, e, f, g, h, i]) == list(range(1, 10))
87+
and
88+
(a + b + c == d + e + f == g + h + i == a + d + g == b + e + h == c + f + i == a + e + i == c + e + g == 15)):
89+
return True
90+
91+
count = 0
92+
for r in range(0, rows-2):
93+
for c in range(0, columns-2):
94+
if grid[r+1][c+1] != 5:
95+
# 中心元素必须是5
96+
continue
97+
if magic(grid[r][c], grid[r][c + 1], grid[r][c + 2],
98+
grid[r + 1][c], grid[r + 1][c + 1], grid[r + 1][c + 2],
99+
grid[r + 2][c], grid[r + 2][c + 1], grid[r + 2][c + 2]):
100+
count += 1
101+
return count
102+
```

‎leetcode_array/翻转图像.md‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。
2+
水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。
3+
反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。
4+
示例：
5+
```python
6+
输入: [[1,1,0],[1,0,1],[0,0,0]]
7+
输出: [[1,0,0],[0,1,0],[1,1,1]]
8+
解释: 首先翻转每一行: [[0,1,1],[1,0,1],[0,0,0]]；
9+
然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]
10+
```
11+
#### 代码：简单粗暴，时间复杂度 O(M∗N)，空间复杂度O(M∗N)
12+
```python
13+
def flipAndInvertImage(A):
14+
res = []
15+
for row in A:
16+
# 水平翻转
17+
row.reverse()
18+
# 0 1替换
19+
new_row = [0 if item else 1 for item in row]
20+
res.append(new_row)
21+
return res
22+
```

‎leetcode_array/转置矩阵.md‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
给定一个矩阵 A， 返回 A 的转置矩阵。
2+
矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。
3+
示例：
4+
```python
5+
输入：[[1,2,3],[4,5,6]]
6+
输出：[[1,4],[2,5],[3,6]]
7+
```
8+
#### 分析：
9+
M\*N矩阵转置后 为N\*M
10+
11+
代码：
12+
```python
13+
def transpose(A):
14+
if not A:
15+
return []
16+
rows = len(A)
17+
columns = len(A[0])
18+
19+
# 构建一个空的转置矩阵
20+
res = [[0 for __ in range(rows)] for _ in range(columns)]
21+
22+
for r in range(rows):
23+
for c in range(columns):
24+
res[c][r] = A[r][c]
25+
return res
26+
```

0 commit comments

Comments
 (0)