算法题刷题笔记-数组

1. 最大子数组和 (LC53)

1
2
3
4
5
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] += max(nums[i - 1], 0)
        return max(nums)
  • 类似前缀和解法，也可以说是动归
  • 保持连续的一段子数组正增长。
  • 第i项等于第i-1项与第i项的和。一旦出现负数，则说明出现了负增长，旧子数组的累加停止，重新开始累加。

2. 合并区间 (LC56)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])

        merged = []
        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

3. 轮转数组（LC189）

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        temp = nums.copy()
        for i in range(n):
            nums[(i+k)%n] = temp[i]
        return nums
  • 自己实现使用了浅拷贝，把nums数组拷贝一份出来设为temp，然后直接赋值到对应的原数组地址
  • 第i项右移k位即为复制到(i+k)%n的位置上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 %= n
        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)
  • 看了灵神思路，大概是先反转整个数组，再反转前k项，再反转后n-k项。

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

  • 题干要求不能用除法，o(n)内解决
  • 没思路参考了灵神思路：算出i左侧所有数乘积，再算出i右侧所有数乘积，就可以算出answer
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution:
        def productExceptSelf(self, nums: List[int]) -> List[int]:
            length = len(nums)
            
            # L 和 R 分别表示左右两侧的乘积列表
            L, R, answer = [0]*length, [0]*length, [0]*length
            
            # L[i] 为索引 i 左侧所有元素的乘积
            # 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
            L[0] = 1
            for i in range(1, length):
                L[i] = nums[i - 1] * L[i - 1]
            
            # R[i] 为索引 i 右侧所有元素的乘积
            # 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
            R[length - 1] = 1
            for i in reversed(range(length - 1)):
                R[i] = nums[i + 1] * R[i + 1]

            # 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
            for i in range(length):
                answer[i] = L[i] * R[i]
            
            return answer