杨辉三角

经典dp, 没什么好说的

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        dp = [[0] * i for i in range(1, numRows + 1)]

        for i in range(numRows):
            for j in range(len(dp[i])):
                if j == 0 or j == len(dp[i]) - 1:
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

        return dp

最大子数组和

初见像滑窗, 但是没有找到好的方法作为维护条件, 再看像前缀和, 直接动态维护当前最小前缀和做差就好

突然发现有点像选不选问题, 有最优特性, 重叠特性, 而且状态无后效性, 也可以枚举, 直接一维 dp

# 前缀和遍历
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = max(nums) # 这里注意初始化为最大的单个元素, 特判都是负数的情况
        min_pre = cur = 0
      
        for i in nums:
            cur += i
            # 这里注意先计算ans再计算min-pre, 不然会出现 0
            ans = max(ans, cur - min_pre)
            min_pre = min(cur, min_pre)

        return ans
# dp 写法
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cur = ans = nums[0]
      
        # cur 作为 dp[i], 状态转移方程为 dp[i] = max(i, dp[i - 1] + i), 也就是单独一个 i, 还是把 i 进入前一个数组
        for i in nums[1:]:
            cur = max(i, cur + i)
            ans = max(ans, cur)
          
        return ans
      

合并区间

难点在于, 如果直接暴力设置一个布尔数组判断区间重叠, 数据量会超时, 得寻找一个方便的合并方式

可以先按区间起始点排序, 这样重叠只会出现在相邻两个区间之间, 然后动态维护ans的最后一个区间就好

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key = lambda x: x[0])
        ans = []
        for i, j in intervals:
            # ans 为空或者尾元素比当前区间严格小, 直接添加
            if not ans or ans[-1][1] < i:
                ans.append([i, j])
            else:
                # 有重叠需判断是吞并还是合并
                ans[-1][1] = max(ans[-1][1], j)
      
        return ans

轮换数组

需注意, 没有任何地方有说明 k < n

# for 写法三次反转法 O(1) 空间复杂度, 我也不知道为什么我要脑抽硬写 for
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n
        mid = n - k
        for i in range(mid // 2):
            nums[i], nums[mid -  i - 1] = nums[mid - i - 1], nums[i]

        for i in range(k // 2):
            nums[mid + i], nums[n - i - 1] = nums[n - i - 1], nums[mid + i]

        for i in range(n // 2):
            nums[i], nums[n - i - 1] = nums[n - i - 1], nums[i]
          
# while 封装函数
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n
        mid = n - k

        def rev(l: int, r: int) -> None:
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]          
                l += 1
                r -= 1
          
        rev(0, mid - 1)
        rev(mid, n - 1)
        rev(0, n - 1)
# 直接切片法, 空间复杂度O(n), 但是最简单
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n

        nums[:] = nums[-k:] + nums[:-k]
# 还有一种循环置换法, 没想出来, 看着很复杂, 跑路了

除自身以外数组的乘积

题目要求不能使用除法, 且时间复杂度为 O(n), 那么就只能线性遍历, 先做一遍前缀左乘积，再然后后缀右乘积，把结果原地乘进去

# 简单明了的版本(也就是初版)
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        l = nums.copy()
        r = nums.copy()
        n = len(nums)
        ans = [0] * n

        for i in range(1, n):
            l[i] *= l[i - 1]

        ans[-1] = l[-2]
  
        for i in range(n - 2, 0, -1):
            r[i] *= r[i + 1]
            ans[i] = l[i - 1] * r[i + 1]
          
        ans[0] = r[1]

        return ans
# 空间优化版(O(1))
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [1] * n
		# 直接保存左前缀乘积, 而不是当前乘积
        for i in range(1, n):
            ans[i] = ans[i - 1] * nums[i - 1]
	
        r = 1
      
        for i in range(n - 1, -1, -1):
            ans[i] *= r # 先 *r, 这样才是后缀
            r *= nums[i] # 更新后缀 

        return ans