力扣hot100

一、53. 最大子数组和

• 思路1：前缀和。
• 代码

  class Solution:
      def maxSubArray(self, nums: List[int]) -> int:
          if len(nums) == 1:
              return nums[0]
          preSum = [0] * (len(nums)+1)
          for idx, n in enumerate(nums):
              preSum[idx+1] = preSum[idx] + n
              
          res = -inf
          for idx, p in enumerate(preSum):
              for i in range(idx):
                  res = max(res, p-preSum[i])
          return res
  # 前缀和比较好写，但是上面复杂度太高，没法AK
  # 其实每次我们只需要减去最小的前缀和，维护一个最小的前缀和，就不需要多一层循环。优化如下
  class Solution:
      def maxSubArray(self, nums):
          if len(nums) == 1:
              return nums[0]
          res = -inf
          preSum = 0
          minPreSum = 0
          for n in nums:
              preSum += n
              res = max(res, preSum - minPreSum)
              minPreSum = min(minPreSum, preSum)
          return res
  

  • 思路2：dp
    • 定义dp[i]，表示以nums[i]j结尾的最大子数组和。当来到第i个位置，有两种可能
      1. 以dp[i] = nums[i]，单独成一个子数组
      2. dp[i] = dp[i-1] + nums[i]，这种情况需要dp[i-1] >＝0
    • 代码

      class Solution:
          def maxSubArray(self, nums):
              dp =[0] * len(nums)
              dp[0] = nums[0]
              for i in range(1, len(nums)):
                  dp[i] = max(dp[i-1], 0) + nums[i]
              return max(dp)
      

      二、56. 合并区间

      

      • 思路：先将intervals中的区间按起始排序。这样每个新来的区间就不用和已经确定好没要交集的区间比较了。
      • 代码

        class Solution:
            def merge(self, intervals: List[List[int]]) -> List[List[int]]:
                intervals.sort(key=lambda p:p[0])  
                res = []
                for p in intervals:
                    if res and p[0]  None:
                def reverse(i, j):
                    while i  
        

        • 代码2：使用python自带的reverse语法

              def rotate2(self, nums: List[int], k: int) -> None:
              	# python也有自带的reverse语法
              	n = len(nums)
              	k %= n
              	nums.reverse()
              	nums[:k] = reversed(nums[:k])
              	nums[k:] = reversed(nums[k:])
          

          四、238. 除自身以外数组的乘积

          

          • 思路：前后缀分解。维护一个pre[i]:表示0到i-1的乘积，suf[i]表示i+1到n-1的乘积。
          • 代码

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

            五、41. 缺失的第一个正数

            

            • 思路：将每个数字放到自己值对应的索引上
            • 代码：

              class Solution:
                  def firstMissingPositive(self, nums: List[int]) -> int:
                      n = len(nums)
                      for i in range(n):
                      	# 当前数字大小在列表范围内且没有放到对应的索引位置上。
                          while 1