【Leetcode】数组 Array

1、leetcode53:最大子序和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

1
2
3
4
5
6
7
def maxSubArray(nums):
# 遇见负值就从自己重新开始累加
for i in range(1, len(nums)):
nums[i]= nums[i] + max(nums[i-1], 0)
return max(nums)

print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))

2、leetcode26:删除排序数组中的重复项

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def removeDuplicates(nums):
# 如果数组为空, 则返回0
if not nums:
return 0
# i为不同元素的数组的长度
i = 1
for j in range(1, len(nums)):
# nums[j]的元素不等于nums[i - 1], 则进行copy, 并且i自增
if nums[j] != nums[i - 1]:
nums[i] = nums[j]
i += 1
return i

print(removeDuplicates([1,1,2]))
print(removeDuplicates([1,1,2,2]))
print(removeDuplicates([0,0,1,1,1,2,2,3,3,4]))

3、leetcode118:杨辉三角

给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。

示例:
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def generate(numRows):
res = []
for i in range(numRows):
if i == 0:
res.append([1])
else:
last_layer = res[i-1][:]
last_layer.append(0)
last_layer.insert(0,0)
cur_layer = [last_layer[j] + last_layer[j+1] for j in range(i+1)]
res.append(cur_layer)
return res

print(generate(7))

4、leetcode561:数组拆分 I

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从1 到 n 的 min(ai, bi) 总和最大。

示例:
输入: [1,4,3,2]
输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).

1
2
3
4
5
6
def arrayPairSum(nums):
# 要想配对后的利益最大化,那一定是最大的和第二大的配对, 最小的和第二小的进行配对, 这样就可以保证奇数位的数能最大化.
# 所以进行一次排序后取奇数位的数求和即可
return sum(sorted(nums)[::2])

print(arrayPairSum([1,4,3,2]))

5、leetcode121:买卖股票的最佳时机

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。

示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。

示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

1
2
3
4
5
6
7
8
9
def maxProfit(prices):
min_price = float('inf')
max_profit = 0
for i in range(len(prices)):
min_price = min(prices[i], min_price)
max_profit = max(max_profit, prices[i]-min_price)
return max_profit

print(maxProfit([7,1,5,3,6,4]))

6、leetcode88:合并两个有序数组

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。
说明:初始化 nums1 和 nums2 的元素数量分别为 m 和 n。你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。

示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

1
2
3
4
5
6
def merge(nums1, m, nums2, n):
nums1[m:m+n] = nums2 # 将nums2合并到nums1中
nums1.sort() # 直接使用内置排序方法sort
return nums1

print(merge([1,2,3,0,0,0],3,[2,4,5],3))

7、leetcode167:两数之和 II - 输入有序数组

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
说明:返回的下标值(index1 和 index2)不是从零开始的。

1
2
3
4
5
6
7
8
9
10
11
12
13
def twoSum(numbers, target):
l = 0
r = len(numbers) - 1
while l < r:
if numbers[l] + numbers[r] == target:
return [l + 1, r + 1]
elif numbers[l] + numbers[r] < target:
l += 1
else:
r -= 1
return []

print(twoSum([2, 7, 11, 15], 9))

8、leetcode27:移除元素

给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。

1
2
3
4
5
6
7
8
def removeElement(nums, val):
j=len(nums)
for i in range(j-1,-1,-1):
if nums[i]==val:
nums.pop(i)
return len(nums)

print(removeElement([0,1,2,2,3,0,4,2], 2))