04-数组

总结

题目总结

1-53-最大子数组和

leetcode-53

计算数组中，最大的连续子数组和

贪心累加求和法

遍历数组，累加求和。
- 之前和 > 0：则保留，之前和 + 当前数
- 之前和 <= 0：则不需要，之前和 = 当前数字

DP递推求和法

dp[i]：以数字i结尾的最大子数组和
递推公式：dp[i] = max(dp[i-1]+nums[i], nums[i])
初始化dp[0]，递推计算，取最值。

2-056-合并区间

题目

给定多个区间列表，合并相邻区间，返回合并后的区间列表。

排序合并法

按照左侧位置，从小到大排序。
遍历每个区间，判断是否和上一个区间相交。
- 如果不相交：直接放入。
- 如果相交：则合并，取[min_start, max_end]，更新上一个区间。

3-189-轮转数组

题目

给定数组nums，和轮转步数k。让数组整体向右轮转k步

python直接切片法

0:k 位置：倒数后k个数，nums[-k:]
k~ 位置：0到倒数第k个数(不含倒k)，nums[:-k]

整体翻转再左右各翻转

先整体翻转，再左边翻转、右边翻转
实现一个翻转函数

4-238-除了自身以外数组的乘积

题目

给定数组nums，计算除了自身以外 其他所有元素的乘积。

左右侧乘积前缀法

左侧乘积前缀 * 右侧乘积前缀，初始化为1，从左到右累乘、从右到左类乘
res[i] = left[i] * right[i]

5-041-缺失的第一个正数

题目

给定数组nums，寻找缺失的最小正整数。

核心

答案在[1,n]和n+1这个n+1个数字中间。
设长度为n的数组，对原数组元素，如果值在[1,n]之间，则按hash放到目标位置上去。
最后检查数组：如果某个位置有空缺 或者 位置全部填满，则找到缺失的最小正整数。

按位置放置新数组方法

设置新数组，把对应元素，按照大小放到位置上。

原地交换Hash位置判断法

不设置新数组，做原地交换，原数组就为hash，放到目标位置上。
循环交换条件：数字在1-n之间、不在目标位置、和目标位置数字不同(避免重复)

python 切片技巧

示例数组 a = [0, 1, 2, 3, 4, 5]

倒数索引

示例

a[-1]： 倒数第1个数字，5，等同于正向的a[0]
a[-2]： 倒数第2个数字，4
a[-3]： 倒数第3个数字，3

含义

所有的负数索引，-n就是倒数第n个数；不像正向索引有0，a[1] 是顺数第2个数。
-1 则为倒数第一个，不存在 倒数第0个。

前后普通切片

a[:3]：前3个数字，不包括a[3]，[0, 1, 2]
a[3:]：从a[3]开始到末尾的所有数字，包括a[3]，[3, 4, 5]
a[-3:]：从倒数第3个数字开始到末尾 的所有数字，包括a[-3]，[3, 4, 5]
a[:-3]：从开始到倒数第3个数字的所有数字，不包括a[-3]，[0, 1, 2]

带结束位置的切片

a[-3:-1]：从倒数第3个数字到倒数第1个数字，不包括a[-1]，[3, 4]

带步长的切片

示例

a[::-1]：步长为1，从尾向前走，省略了 start和end
- 倒着走：5,4,3,2,1,0
a[::1]：步长为1，从前向后走，省略了 start和end
- 正着走：0,1,2,3,4,5
a[::2]：步长为2，从前往后走
- 正着走：0,2,4
a[::-2]：步长为2，从后往前走
- 倒着走：5,3,1

步数为负

步长-1：从尾向前走，步长为1
步长-2：从尾向前走，步长为2

步长为正

步长1：从前向后走，步长为1
步长2：从前向后走，步长为2

题目

1-053-最大子数组和

leetcode-53

输入：数组nums
输出：最大的连续子数组和

相似题

贪心累加求和法

遍历数组， 计算当前连续和
- 之前和 > 0：则保留，之前和 + 当前数
- 之前和 <= 0：则不需要，之前和 = 当前数字

python

def maxSubArray_greedy(self, nums: List[int]) -> int:
    """ 贪心算法，累计求和，如果之前和<=0，则不需要了，仅保留当前数字；如果之前和>0，则累加。
    """
    if not nums:
        return 0
    current_sum = nums[0]  
    max_sum = nums[0]

    for i in range(1, len(nums)):
        if current_sum > 0:
            current_sum += nums[i]  
        else:
            current_sum = nums[i]  
        max_sum = max(current_sum, max_sum)
    return max_sum

前缀和求最大子数组和

数学公式思想

前缀和 $s [i]$ ：数组0-i 的 求和

s [i] = pre [i] = \sum_{j = 0}^{i} nums [j]

子数组j~i的求和
$s [i] - s [j - 1]$
?~i的最大子数组和：到i时，减去 之前出现过的最小前缀和，即以i结尾的最大子数组和。
$s [i] - min_{0 \leq j \leq i - 1} s [j - 1]$

实现代码

定义变量：最小前缀和、累积求和、最大子数组和
遍历数组，依次计算每个位置数字的信息
- 计算以i结尾的前缀和：s[i]
- 计算以i结尾的最大子数组和：current_sum - min_prefix
- 更新全局最大子数组和、全局最小前缀

python

def maxSubArray_prefix_sum(self, nums: List[int]) -> int:
    """ 使用前缀和来计算。
    s[i]: 0-i的求和。
    j-i的子数组和：s[i] - s[j-1]
    以i结尾，最大子数组和：减去最小的s[j-1]即可。
    """
    if not nums:
        return 0

    # 最小出现的前缀和
    min_prefix = 0
    # 累计求和
    current_sum = 0
    # 最终结果，最大子数组和
    max_subsum = nums[0]

    for i in range(len(nums)):
        # s[i]，当前前缀和
        current_sum += nums[i]  

        # 以i结尾的，最大子数组和。s[i] - 最小前缀
        current_max_subsum = current_sum - min_prefix  

        # 更新最大子数组和
        max_subsum = max(max_subsum, current_max_subsum)

        # 更新最小前缀
        min_prefix = min(min_prefix, current_sum)  
    return max_subsum

DP求最大子数组和

核心思路

dp[i]：以数字i结尾的最大子数组和
公式：dp[i] = max(dp[i-1]+nums[i], nums[i])

实现步骤

初始化dp数组和dp[0]，递推计算dp数组，取最值。

利用过去的状态来推导现在的状态，无后效性

python

def maxSubArray_dp(self, nums: List[int]) -> int:
    """
    dp[i]：以数字i结尾，最大连续子数组和
    dp[i] = max(dp[i-1]+nums[i], nums[i])
    """
    if not nums:
        return 0

    # dp[i] 初始化
    dp = [0] * len(nums)
    dp[0] = nums[0]  

    # dp[i] 递推计算
    for i in range(1, len(nums)):
        dp[i] = max(dp[i-1]+nums[i], nums[i])  

    # 取最大值
    max_sum = max(dp)  
    return max_sum

2-056-合并区间

leetcode-056

输入：数组区间列表，即有多个区间，不同区间可能有交集重复。
输出：合并相同区间，输出合并后的区间列表。

示例

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]

排序再合并区间方法

排序再合并区间

核心思想

先按左端点对所有区间做升序排序。
遍历每个区间
- 判断当前区间和上一个区间 是否重叠
- 如果有，则合并；如果无重叠，则放进新区间列表。

区间相交合并

相交：cur_start <= last_end
合并取大区间：[min_start，max_end]

python

def merge_sortmerge(self, intervals: List[List[int]]) -> List[List[int]]:
    """
    先对区间，按照左端点，对其做排序。
    然后遍历每个区间，如果当前区间和上一个区间有重叠，则更新上一个区间的右端点即可。
    """
    if not intervals:
        return []

    sort_intervals = sorted(intervals, key=lambda d: d[0])  

    merged = []
    for interval in sort_intervals:
        if not merged:
            # 当前合并列表为空，直接存入第一个
            merged.append(interval) 
            continue
        # 当前区间和上一个区间
        cur_start, cur_end = interval
        last_start, last_end = merged[-1]
        if cur_start > last_end:  
            # 不相交
            merged.append(interval)
        else:
            min_start = min(last_start, cur_start)  
            max_end = max(last_end, cur_end)  
            merged[-1][0], merged[-1][1] = min_start, max_end
    return merged

3-189-轮转数组

leetcode-189

输入：给定数组nums，轮转个数k，每个数向右轮转k个位置。
输出：轮转后的nums

示例

[0, 1, 2, 3, 4]，k = 2
[3, 4, 0, 1, 2]

注意

k可能超过数组长度，需先取余：k = k % len(nums)

python直接切片法

直接利用python做切片

精简版思想

0:k 位置：倒数后k个数，nums[-k:]
k~ 位置：0到倒数第k个数(不含倒k)，nums[:-k]
nums[:] = nums[-k:] + nums[:-k]

朴素复杂版思想

前k个位置：为后k个数
- nums[:k] = nums[-k:]
后n-k个位置：为前n-k个数
- j = n-k
- nums[-j:] = nums[:j]

python

def rotate_pythonclip(self, nums: List[int], k: int) -> None:
    """直接使用python clip 左原地旋转
    """

    if not nums:
        return nums

    # 0:k 位置：倒数后k个数，nums[-k:]
    # k:~ 位置：0到倒数第k个数(不含倒k)，nums[:-k]
    k = k % len(nums)  
    nums[:] = nums[-k:] + nums[:-k]  
    return nums

整体翻转再左右各翻转

核心思路

先整体翻转
再左边翻转、右边翻转
需实现一个翻转函数 reverse(l, r)

示例 0, 1, 2, 3, 4, k = 2

整体翻转：4, 3, 2, 1, 0
左边0-k翻转：3, 4, 2, 1, 0
右边k-尾翻转：3, 4, 0, 1, 2

python

def rotete_3times(self, nums: List[int], k: int) -> None:
    """ 先全部翻转，再翻转左边部分，再翻转右边部分
    """
    if not nums or k < 0:
        return

    k = k % len(nums)
    n = len(nums)

    # 定义翻转函数，指定翻转区间翻转
    def reverse(l: int, r: int):
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]  
            l += 1
            r -= 1

    # 三次翻转：先整体翻转，再翻转左边和右边。
    reverse(0, n-1)  
    reverse(0, k-1)  
    reverse(k, n-1) 
    return

4-238-除了自身以外数组的乘积

leetcode-238

输入：nums数组，计算除自身以外 其他所有元素的乘积
输出：乘积数组

注意

不能使用除法，只能使用乘法。

左右侧乘积前缀法

核心思想

不含当前位置的前缀乘积：最左和最右位置 乘积均为1
左侧乘积前缀数组：依次计算
- left[i] = left[i-1] * nums[i-1]
右侧乘积后缀数组：依次计算
- right[i] = right[i+1] * nums[i+1]
再依次计算各位置上的乘积

注意点

因为乘积，前缀数组元素需要初始化为1。

python

def productExceptSelf(self, nums: List[int]) -> List[int]:
    """ 
    左侧乘积前缀 * 右侧乘积前缀，初始化为1，从左到右累乘、从右到左类乘
    res[i] = left[i] * right[i]
    """
    if not nums:
        return []

    n = len(nums)

    # 1. 初始化左右乘积前缀数组，初始化为1
    left = [1] * n  
    right = [1] * n  
    res = [1] * n

    # 2. 计算左侧前缀数组
    for i in range(n):
        if i == 0:
            # 最左侧是没有前缀的
            left[i] = 1
        else:
            # 迭代计算前缀
            left[i] = left[i-1] * nums[i-1]  

    # 3. 计算右侧前缀数组
    for i in range(n-1, -1, -1):
        if i == n-1:
            # 最右侧，没有前缀
            right[i] = 1
        else:
            right[i] = right[i+1] * nums[i+1]  

    # 4. 计算每个位置上除自身的乘积
    for i in range(n):
        res[i] = left[i] * right[i]  

    return res

5-041-缺失的第一个正数

leetcode-041

输入：数组nums
输出：找出nums中未出现的 最小正整数。

特点

数组长度为n，答案在[1~n]和n+1 这n+1个数中间。

示例

[1, 2, 0]：3是最小
[3, 4, -1, 1]：2是最小
[8 9, 11, 6]：1是最小

原地交换Hash位置判断法

核心思路

答案在[1~n]和n+1 这n+1个数中间
遍历数组：把各数字，按照从小到大，放到应该放置的位置上去。
最后检查：哪个位置有空缺或者位置全部被填满，来确定哪个为缺失的最小元素。

难点

考虑位置已存在
需做循环交换，条件如下
- nums[i]合法 且 不在目标位置上
- 目标位置数字和当前数字不同：避免重复

python

def firstMissingPositive_selfhashexchange(self, nums: List[int]) -> int:
    """ 
    1. 答案在[1-n]和n+1 这n个数之间
    2. 把这些nums数组，按照位置，把它放到该放的位置上去，最后再判断哪个位置上有缺失，则是该数字
    """
    if not nums:
        return 1

    n = len(nums)

    # 按照1-n去放置nums数组，元素放到固定位置上
    for i in range(n):
        # nums[i] 需要放到nums[i]-1位置上，元素位置做交换
        # 此处需要持续做交换，直到位置i已放置合适数字或不合适数字
        # 此处需要考虑重复问题，目标位置已经是该元素了
        while nums[i] != i+1 and 1 <= nums[i] <= n and nums[nums[i]-1] != nums[i]:  
            new_pos = nums[i] - 1
            nums[i], nums[new_pos] = nums[new_pos], nums[i]  

    res = -1
    # 遍历，检查每个位置，是否有空缺
    for i in range(n):
        if i+1 != nums[i]:
            res = i+1
            break
    if res == -1:  
        # 说明没有空缺，每个位置都填满
        res = n+1
    return res

按位置放置新数组方法(不做原地交换)

笔记

答案在[1,n]和n+1这个n+1个数字中间
单独开一个数组，把原数组每个位置的值，如果值合法(1-n)，按Hash位置放到新数组中
最后再去做检查：看哪个位置空缺 或者 位置全部填满，则找到缺失的最小正整数。

python

def firstMissingPositive_extra_hash_array(self, nums: List[int]) -> int:
    """
    1. 答案在[1,n]和n+1 这个n+1个数字中间
    2. 单独开一个数组，把原数组每个位置的值，如果值合法(1-n)，按照从小到大放到新数组中
    3. 最后再去做检查，看哪个位置空缺 或者 位置全部填满
    """
    if not nums:
        return 1

    # 1. 初始化新数组
    n = len(nums)
    order_nums = [-1] * n  

    # 2. 遍历原数组，把数字放到对应位置上
    for i in range(n):
        if 1<= nums[i] <= n:
            order_nums[nums[i]-1] = nums[i]  

    # 3. 检查哪个位置为空
    res = -1
    for i in range(n):
        if order_nums[i] != i+1:
            res = i+1
            break

    # 4. 如果所有位置都被填满
    if res == -1:  
        res = n+1
    return res

总结 ​

题目总结 ​

python 切片技巧 ​

题目 ​

1-053-最大子数组和 ​

贪心累加求和法 ​

前缀和求最大子数组和 ​

DP求最大子数组和 ​

2-056-合并区间 ​

排序再合并区间方法 ​

3-189-轮转数组 ​

python直接切片法 ​

整体翻转再左右各翻转 ​

4-238-除了自身以外数组的乘积 ​

左右侧乘积前缀法 ​

5-041-缺失的第一个正数 ​

原地交换Hash位置判断法 ​

按位置放置新数组方法(不做原地交换) ​

总结

题目总结

python 切片技巧

题目

1-053-最大子数组和

贪心累加求和法

前缀和求最大子数组和

DP求最大子数组和

2-056-合并区间

排序再合并区间方法

3-189-轮转数组

python直接切片法

整体翻转再左右各翻转

4-238-除了自身以外数组的乘积

左右侧乘积前缀法

5-041-缺失的第一个正数

原地交换Hash位置判断法

按位置放置新数组方法(不做原地交换)