【Leetcode】top 100 普通数组

53 最大子数组和

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

思路：两层for循环直接模拟，易错点在最小值的初始化；

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        outl= nums[0]
        for length in range(1,len(nums)+1):
            outs, summ = 0, 0
            for start in range(len(nums)):
                if start < length: summ += nums[start]
                else: summ = summ+nums[start]-nums[start-length]
                outs = max(outs, summ)
            outl = max(outl, outs)
        return outl

#巨长案例会超过时间限制，通过201/210案例

官方思路：动态规划

dp[i]表示以下标为i的元素结尾的子组合的最大值

以 nums = [5,4,-1,7,8] 为例：

dp[2]的子组合：[5,4,-1][4,-1],[-1] dp[2]=8

dp[3]的子组合：[5,4,-1,7][4,-1,7][-1,7][7] dp[3]=15

规律：dp[i]=dp[i-1]+nums[i] when dp[i-1]>0

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp, out = 0, -10**4-1
        for i in range(len(nums)):
            dp = dp + nums[i] if dp > 0 else nums[i]
            out = max(out, dp)
        return out

56 合并空间

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

思路：对所有区间按起点值排序后，当前区间的起点值大于前一区间的终点值 且 当前区间的终点值小于后一区间的起点值时，区间不重叠，记录当前区间；(第一个/最后一个区间特殊处理)

当区间重叠时，重叠起点为当前区间的起点值，而重叠终点则需要动态维护；如[1,10][2,11]和[1,10][2,9]，直至找到下一个区间的起始值大于重叠终点；
class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        length = len(intervals)
        if length==1:return intervals

        out = []
        intervals.sort(key=lambda x:x[0])
        if intervals[1][0] > intervals[0][1]:                   #第一区间特殊处理
            out.append(intervals[0]) 
        
        i = 1
        while i < length:
            if intervals[i][0] <= intervals[i-1][1]:             #和前一区间重叠
                start = intervals[i-1][0]
                end = intervals[i-1][1]
                while i < length:
                    if intervals[i][0] > end:break
                    end = max(end, intervals[i][1])
                    i += 1
                out.append([start, end])
            else:
                if i == length-1:out.append(intervals[i])         #不和后一区间重叠或位于最后
                else:
                    if intervals[i][1] < intervals[i+1][0]: out.append(intervals[i]) 
                i += 1
        return out
简化代码：当前区间的起点值大于前一段区间的最大终点值，存下前一段区间，然后更新start更新为当前区间的起点值，end更新为当前区间的终点值（由于start<=end，所以当前区间的终点值自然大于前一段区间的最大终点值，可以和动态维护一段区间的最大终点值操作合并）
class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        
        intervals.sort(key=lambda x:x[0])
        start, end, out = intervals[0][0], intervals[0][1], []

        for i in range(len(intervals)):
            if intervals[i][0] > end:
                out.append([start, end])
                start = intervals[i][0]
            end = max(end, intervals[i][1])
        out.append([start, end])
        return out

189 轮转数组

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

思路：三次翻转 (之前做过

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        #三次翻转：全翻+两次相对翻
        #[7,6,5,4,3,2,1]     [4,3,2,1,5,6,7]
        #[5,6,7,4,3,2,1]     [4,3,2,1,7,6,5]
        #[5,6,7,1,2,3,4]     [5,6,7,1,2,3,4]
        k = k % len(nums)
        nums[:] = nums[::-1]
        nums[:k] = nums[:k][::-1]
        nums[k:] = nums[k:][::-1]
        return nums

列表翻转用切片

nums = [1,2,3,4,5,6,7]    k = 3

1.nums[:k].reverse()  #[1,2,3]
2.numss = nums[:k]
  numss.reverse()     #[3,2,1]

238 除自身以外数组的乘积

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

思路一：前后缀 （之前做过

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        prefix, postfix = [1], 1
        for i in range(1, len(nums)):
            prefix.append(prefix[i-1]*nums[i-1])
        for i in range(len(nums)-1, -1,-1):
            prefix[i] = postfix*prefix[i]
            postfix = postfix * nums[i]
        return prefix

思路二：双指针

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """   
        out = [1]*len(nums)
        prefix, postfix = 1, 1
        for i in range(len(nums)):
            out[i] = out[i] * prefix
            out[-i-1] = out[-i-1] * postfix
            prefix, postfix = prefix*nums[i], postfix*nums[-i-1]
        return out

不想处理边界情况的关键就在于先求乘积结果再更新前后缀；

41 缺失的第一个正数

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

按[1,2,3...的顺序找出第一个没出现在数组中的值；

方法一：排序，从第一个大于0的数开始判断；时间复杂度O(NlogN)

方法二：计数，返回第一个计数值为0的数；空间复杂度O(N)

方法三：集合 set自动去重，查找也很快空间复杂度O(N)

均不满足题目要求：时间复杂度为 O(n) 并且只使用常数级别额外空间；

方法四：原地哈希 一次遍历nums，对零、负数和大于len(nums)的数不操作，只要保证将k放在k-1的位置上，更新位置后再一次遍历，当nums[k-1]!=k时，找到缺失的k
class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        while i < len(nums):
            if nums[i]<=0 or nums[i]>len(nums):i+=1   #越界值不处理
            else:
                # if nums[i] == i+1:i+=1              #当前值正确不处理
                # [1,1]会卡死在当前值错误里反复交换
                # nums[i] 存错的没关系，但要保证nums[nums[i]-1]正确
                if nums[nums[i]-1] == nums[i]:i+=1   #要交换的位置上已经有正确元素了
                else:
                    nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]      #把k放到nums[k-1]
        i = 0
        while i < len(nums):
            if nums[i] != i+1: return i+1
            i+=1
        return i+1