Skip to content

Commit 87ad8b3

Browse files
daachengdaacheng
committed
更新md
更新md
1 parent 9d943c3 commit 87ad8b3

File tree

5 files changed

+219
-0
lines changed

5 files changed

+219
-0
lines changed

‎leetcode_array/main.md‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,3 +24,7 @@
2424
22. [斐波那契数](斐波那契数.md)
2525
23. [数组中的K-diff数对（逆向思维）](数组中的K-diff数对.md)
2626
24. [数组拆分I](数组拆分I.md)
27+
25. [重塑矩阵](重塑矩阵.md)
28+
26. [最短无序连续子数组](最短无序连续子数组.md)
29+
27. [种花问题](种花问题.md)
30+
28. [三个数的最大乘积](三个数的最大乘积.md)

‎leetcode_array/三个数的最大乘积.md‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
2+
示例：
3+
```python
4+
输入: [1,2,3]
5+
输出: 6
6+
```
7+
#### 方法一：排序
8+
对数组进行升序排序后：
9+
如果没有负数或者只有一个负数，那一定是最后三位数相乘最大
10+
如果有两个以上负数，考虑负负得正，需要比较最后三个数的乘积，与前两个数的乘积*最后一位正数
11+
12+
```python
13+
def maximumProduct(nums):
14+
if len(nums) == 3:
15+
return nums[0] * nums[1] * nums[2]
16+
nums.sort()
17+
max_1 = nums[-1] * nums[-2] * nums[-3]
18+
max_2 = nums[0] * nums[1] * nums[-1]
19+
20+
return max(max_1, max_2)
21+
```
22+
#### 方法二：
23+
通过方法一分析可以看出，实际上只需要找到最小的两个数，和最大的三个数，就可以了。
24+
```python
25+
def maximumProduct(nums):
26+
max_1, max_2, max_3 = float('-inf'), float('-inf'), float('-inf')
27+
min_1, min_2 = float('inf'), float('inf')
28+
for item in nums:
29+
if item <= min_1:
30+
# 注意赋值顺序
31+
min_2 = min_1
32+
min_1 = item
33+
elif min_1 < item < min_2:
34+
min_2 = item
35+
36+
if item >= max_1:
37+
max_3 = max_2
38+
max_2 = max_1
39+
max_1 = item
40+
elif item >= max_2:
41+
max_3 = max_2
42+
max_2 = item
43+
elif item > max_3:
44+
max_3 = item
45+
mult_1 = max_1 * max_2 * max_3
46+
mult_2 = min_1 * min_2 * max_1
47+
return max(mult_1, mult_2)
48+
```

‎leetcode_array/最短无序连续子数组.md‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
2+
你找到的子数组应是最短的，请输出它的长度。
3+
示例：
4+
```python
5+
输入: [2, 6, 4, 8, 10, 9, 15]
6+
输出: 5
7+
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
8+
```
9+
#### 解析：
10+
* 对原数组进行排序
11+
* 排序后的数组与原数组进行比较
12+
13+
```python
14+
[2, 6, 4, 8, 10, 9, 15]
15+
[2, 4, 6, 8, 9, 10, 15]
16+
对比即可发现最短无序数组
17+
```
18+
代码
19+
```python
20+
class Solution:
21+
def findUnsortedSubarray(self, nums: List[int]) -> int:
22+
nums_ = nums.copy()
23+
nums.sort()
24+
start, end = 0, 0
25+
flag = False
26+
for index, item in enumerate(nums_):
27+
if item != nums[index]:
28+
if not flag:
29+
start = index
30+
flag = True
31+
else:
32+
end = index + 1
33+
return end - start
34+
```

‎leetcode_array/种花问题.md‎

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
2+
给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。
3+
示例：
4+
```python
5+
输入: flowerbed = [1,0,0,0,1], n = 1
6+
输出: True
7+
输入: flowerbed = [1,0,0,0,1], n = 2
8+
输出: False
9+
```
10+
#### 方法一：
11+
遍历数组，如果一个元素是0，并且它的左右两个元素都是0，那就可以种花，并把该位置改为1，特殊情况，数组第一个元素，与数组最后一个元素，特殊处理。
12+
```python
13+
def canPlaceFlowers(flowerbed, n):
14+
length = len(flowerbed)
15+
count = 0
16+
if length == 1 and flowerbed[0] == 0:
17+
count += 1
18+
else:
19+
for i in range(0, length):
20+
if i == 0:
21+
# 最左边
22+
if flowerbed[i] == 0 and flowerbed[i+1] == 0:
23+
count += 1
24+
flowerbed[i] = 1
25+
elif i == len(flowerbed)-1:
26+
# 最右边
27+
if flowerbed[i] == 0 and flowerbed[i-1] == 0:
28+
count += 1
29+
flowerbed[i] = 1
30+
else:
31+
# 中间
32+
if flowerbed[i] == 0 and flowerbed[i-1] == 0 and flowerbed[i+1] == 0:
33+
count += 1
34+
flowerbed[i] = 1
35+
if count >= n:
36+
return True
37+
return False
38+
```
39+
#### 优化：执行过程中，如果count已经大于n了，直接返回结果
40+
```python
41+
def canPlaceFlowers(flowerbed, n):
42+
length = len(flowerbed)
43+
count = 0
44+
if length == 1 and flowerbed[0] == 0:
45+
count += 1
46+
if count >= n:
47+
return True
48+
else:
49+
for i in range(0, length):
50+
if i == 0:
51+
# 最左边
52+
if flowerbed[i] == 0 and flowerbed[i+1] == 0:
53+
count += 1
54+
flowerbed[i] = 1
55+
elif i == len(flowerbed)-1:
56+
# 最右边
57+
if flowerbed[i] == 0 and flowerbed[i-1] == 0:
58+
count += 1
59+
flowerbed[i] = 1
60+
else:
61+
# 中间
62+
if flowerbed[i] == 0 and flowerbed[i-1] == 0 and flowerbed[i+1] == 0:
63+
count += 1
64+
flowerbed[i] = 1
65+
if count >= n:
66+
return True
67+
return False
68+
```

‎leetcode_array/重塑矩阵.md‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。
2+
重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
3+
如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
4+
示例：
5+
```python
6+
输入:
7+
nums =
8+
[[1,2],
9+
[3,4]]
10+
r = 1, c = 4
11+
输出:
12+
[[1,2,3,4]]
13+
解释:
14+
行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。
15+
16+
输入:
17+
nums =
18+
[[1,2],
19+
[3,4]]
20+
r = 2, c = 4
21+
输出:
22+
[[1,2],
23+
[3,4]]
24+
解释:
25+
没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
26+
```
27+
#### 把原数组中的元素平铺，然后等分，构建成新的矩阵。
28+
```python
29+
def matrixReshape(nums, r, c):
30+
r_ = len(nums)
31+
c_ = len(nums[0])
32+
if r_*c_ != r*c:
33+
# 总元素个数不相等，无法转换
34+
return nums
35+
# 平铺
36+
tmp_nums = []
37+
for row in nums:
38+
tmp_nums += row
39+
# 重新构建
40+
res = []
41+
for i in range(0, len(tmp_nums), c):
42+
res.append(tmp_nums[i:i+c])
43+
return res
44+
```
45+
#### 遍历，逐个填充
46+
```python
47+
def matrixReshape(nums, r, c):
48+
r_ = len(nums)
49+
c_ = len(nums[0])
50+
if r_*c_ != r*c:
51+
return nums
52+
53+
res = []
54+
tmp_row = []
55+
count = 0
56+
for row in nums:
57+
for item in row:
58+
tmp_row.append(item)
59+
count += 1
60+
if count == c:
61+
res.append(tmp_row)
62+
tmp_row = []
63+
count = 0
64+
return res
65+
```

0 commit comments

Comments
 (0)