【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))