【数据结构与算法】之数组系列-20240117

---

一、167. 两数之和 II - 输入有序数组

中等

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。

示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

与力扣（1. 两数之和）代码相似，只是在返回的索引中加1

def func1(nums, target):
    left = 0
    right = len(nums)-1
    while left < right:
        if nums[left] + nums[right] == target:
            return [left+1, right+1]
        elif nums[left] + nums[right] > target:
            right -= 1
        else:
            left += 1
    return [-1, -1]


nums =[-1,0]
target = -1
print(func1(nums=nums, target=target))

二、164. 最大间距

中等
给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。
您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

示例 1:

输入: nums = [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:

输入: nums = [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。

思路：从第二个数遍历，与前一个数据相减得到的值与res进行比较，取最大值。遍历过程中不断更新res的值

def func164(nums):
    if len(nums)<2:
        return 0
    res=0
    for i in range(1,len(nums)):
        ret=nums[i]-nums[i-1]
        res=max(ret,res)
    return res
nums = [3,6,9,1]
print(func164(nums))

三、128. 最长连续序列

中等

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

def test3(nums):
    res = 0  # 记录最长连续序列的长度
    num_set = set(nums)  # 记录nums中的所有数值
    for num in num_set:
        # 如果当前的数是一个连续序列的起点，统计这个连续序列的长度
        if (num - 1) not in num_set:
            seq_len = 1  # 连续序列的长度，初始为1
            while (num + 1) in num_set:
                seq_len += 1
                num += 1  # 不断查找连续序列，指导num的下一个数不存在数组中
            res = max(res, seq_len)
    return res


nums = [100, 4, 200, 1, 3, 2]
print(test3(nums))

四、122. 买卖股票的最佳时机 II

中等

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。

示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。

示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。

示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        tmp = prices[i] - prices[i - 1]
        if tmp > 0:
            profit += tmp
    return profit

五、78. 子集

中等
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：

输入：nums = [0]
输出：[[],[0]]

class Solution:
    def subsets(self, nums):
        res = []
        tmp = []

        def dfs(i):
            if i >= len(nums):
                res.append(tmp.copy())
                return
            # add
            tmp.append(nums[i])
            dfs(i + 1)

            # not add
            tmp.pop(-1)
            dfs(i + 1)

        dfs(0)
        return res


ss = Solution()
nums = [1, 2, 2]
print(ss.subsets(nums))

六、75. 颜色分类

中等

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

# todo 快速排序的时间复杂度为 O(n^2)
def quickSort(nums):
    n = len(nums)
    if n <= 1:
        return nums
    pivot = nums[0]
    left = []
    right = []
    for i in range(1, n):
        if nums[i] > pivot:
            right.append(nums[i])
        else:
            left.append(nums[i])
    return quickSort(left) + [pivot] + quickSort(right)


nums = [2, 0, 2, 1, 1, 0]
res = quickSort(nums)
print(res)

---