力扣100题-普通数组

1.最大子数组和

• 描述：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

  子数组是数组中的一个连续部分

思路一：

• 动态规划，dp[i]表示以i为结尾的连续数组的最大和。当dp[i-1]<=0时，dp[i] = nums[i],else dp[i] = dp[i-1]+nums[i]。由于dp[i]只根据dp[i-1]即可得出可以用一个变量pre来表示，节约空间
• 代码：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        pre = nums[0]
        ans = nums[0] # n >= 1才可以这样写
        for i in range(1, n):
            if pre <= 0:
                pre = nums[i]
            else:
                pre = pre+nums[i]
            ans = max(ans, pre) 
        return ans

思路二：

• 前缀和。求连续数组的和的最大值，很容易想到前缀和，那么问题就转化为股票出卖时间那道贪心题，边遍历边更新前缀和数组，存储最小的前缀和数组，然后取它们的差，在这个过程中不断更新答案
• 代码：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        pre_sum = pre_min_sum = 0
        ans = - inf
        for x in nums:
            pre_sum += x # 更新当前的前缀和
            ans = max(ans, pre_sum - pre_min_sum)
            pre_min_sum = min(pre_min_sum, pre_sum) # 更新最小的前缀和
        return ans

2.合并区间

• 描述：以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

思路一：

• 思路很清晰，按左端点进行排序，当当前的左端点在前一个的右端点的前面，就说明可以尝试进行合并，反之，直接作为一个新的区间加入到答案中
• 代码：

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x:x[0]) # 按左端点进行升序排序
        ans = [intervals[0]] # 特殊处理第一个区间，也可以放到for里，加个判断即可
        n = len(intervals)
        for i in range(1, n):
            if intervals[i][0] <= ans[-1][1]:
                ans[-1][1] = max(ans[-1][1], intervals[i][1])
            else:
                ans.append(intervals[i])
        return ans

3.轮转数组

• 描述：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

思路一：

• 通过三次翻转数组可以实现不增加额外空间的情况下实现轮转数组，很巧妙！

• 代码

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(i: int, j: int) -> None: # 手写翻转数组
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1
        n = len(nums)
        k = k % n
        reverse(0, n-1)
        reverse(0, k-1)
        reverse(k, n-1)

4.除自身以外的数组乘积

• 描述：给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

  题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

  请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

思路一：

• 关键在于不能使用除法，那么就通过位置i的前缀和后缀数组相乘来得到答案。注意左右边界的处理。时间复杂度为O[N],空间复杂度为O[N]

• 代码：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pre = [1] * n
        suf = [1] * n 
        # 前缀数组和后缀数组的初始化
        for i in range(1, n):
            pre[i] = pre[i-1] * nums[i-1]
        for i in range(n-2, -1, -1):
            suf[i] = suf[i+1] * nums[i+1]
        ans = list()
        for i in range(n):
            ans.append(pre[i] * suf[i])
        return ans

思路二：

• 在思路一的基础上优化空间，其中的前缀数组可以隐藏进最后的遍历中，减少了空间的浪费
• 代码：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        suf = [1] * n 
        for i in range(n-2, -1, -1):
            suf[i] = suf[i+1] * nums[i+1]
        ans = list()
        pre = 1
        for i in range(n):
            ans.append(pre * suf[i])
            pre *= nums[i]
        return ans

5.缺失的第一个正数

• 描述：给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

  请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

思路一：

• 找没出现过的数可以想到哈希，但是要结合常数级别的额外空间可以想到原地哈希。有题目可知答案的范围为[1,N+1]，那么先对负数进行处理，把他们转化为n+1,再遍历数组，若当前的数<=n,就把它的减一作为下标的nums[i-1]修改为-nums[i-1],用负数来标记整个数出现过。那么最后只需要遍历数组，第一个正数就是答案了，或者就是n+1。非常妙的在原地实现了哈希表
• 代码：

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n): # 预处理负数
            if nums[i] <= 0:
                nums[i] = n + 1
        for i in range(n):
            c = abs(nums[i])
            if c <= n:
                nums[c - 1]  = -abs(nums[c - 1]) # 关键语句
        for i in range(n):
            if nums[i] > 0:
                return i + 1
        return n + 1