代码编织梦想

前言

  • 这几天搞工作处理数据真是类似我也,还被老板打电话push压力有点大的,还好搞的差不多了,明天再汇报,赶紧偷闲再刷几道题(可恶,被打破连更记录了)
  • 这几天刷的是动态规划,由于很成体系不适合零散刷,还是把代码随想录动态规划部分的题目快速再过一遍,代码简单但是思路也要记住

139. 单词拆分 - 力扣(LeetCode)

  • 动态规划

    • class Solution:
          def wordBreak(self, s: str, wordDict: List[str]) -> bool:
              s_length = len(s)
              dp = [False] * (s_length + 1)   # dp[i]表示s[0:i]能否被拼接
              dp[0] = True                    # 初始化,空字符串可以
              for i in range(1, s_length+1):  # 遍历结束指针i
                  for j in range(i):          # 遍历开始指针j
                      if dp[j] and s[j:i] in wordDict:  # 如果j-1已经可拼,s[j:i]可再拼一个
                          dp[i] = True        # 整体就可以拼接
                          break               # 找到一组拼接,更新为True就退出
              return dp[s_length]

 300. 最长递增子序列 - 力扣(LeetCode)

  • 动态规划

    • class Solution:
          def lengthOfLIS(self, nums: List[int]) -> int:
              n = len(nums)  # dp[i]表示以nums[i]结尾的最长递增子串长度
              dp = [1] * n   # 初始化为全1,子串至少为1个
              res = 1  # 结果先取1
              for i in range(1, n):
                  for j in range(i):
                      if nums[i] > nums[j]:  # 只要比前面的递增,子串长度+1
                          dp[i] = max(dp[i], dp[j] + 1)
                  res = max(res, dp[i])  # 更新最长值
              return res

152. 乘积最大子数组 - 力扣(LeetCode)

  • 动态规划

    • class Solution:
          def maxProduct(self, nums: List[int]) -> int:
              n = len(nums)
              dp_max = [float('-inf')] * n  # 表示以nums[i]为底的连续子数组的最大乘积,也可以用pre_max一个变量表示
              dp_min = [float('inf')] * n  # 表示以nums[i]为底的连续子数组的最小乘积,也可以用pre_min一个变量表示
              dp_max[0] = dp_min[0] = res = nums[0]
              for i in range(1, n):
                  # 由于当前可能正可能负,三种取最大/小:当前数,前最大×当前数,前最小×当前数
                  dp_max[i] = max(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])
                  dp_min[i] = min(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])
                  res = max(res, dp_max[i])
              return res
  • 符号个数

    • 思路参考题解及评论区
    • class Solution:
          def maxProduct(self, nums: List[int]) -> int:
              reverse_nums = nums[::-1]
              # 先按照0分成多个数组,在不同数组里统计奇数个数
              # 负数个数为偶数,全部相乘,负数个数为奇数,某奇数的前缀乘积或后缀乘积为最大值
              for i in range(1, len(nums)):
                  nums[i] *= nums[i - 1] or 1   # 前缀乘积(遇到0就重置)
                  reverse_nums[i] *= reverse_nums[i - 1] or 1  # 后缀乘积(遇到0就重置)
              return max(nums + reverse_nums)  # 一定是前缀乘积和后缀乘积的最大值

416. 分割等和子集 - 力扣(LeetCode)

  • 01背包

    • class Solution:
          def canPartition(self, nums: List[int]) -> bool:
              numSum = sum(nums)
              if numSum % 2 == 1: return False  # 总和为奇数无法等分
              target = numSum // 2  # 01背包大小
              dp = [0] * (target + 1)  # dp[j]表示以j为容量的背包装的最大价值
              for i in range(len(nums)):  # 遍历物品,从头到尾,重量和价值都为nums[i]
                  for j in range(target, nums[i] - 1, -1):  # 遍历背包,从target到nums[i]倒序
                      dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
              return dp[target] == target  # 如果target容量的背包刚好能装价值为target,找到分割方法

32. 最长有效括号 - 力扣(LeetCode)

  • 辅助栈

    • 参考题解
    • class Solution:
          def longestValidParentheses(self, s: str) -> int:
              st = []  # 栈中存储的是到当前位置暂时不可以构成括号的索引
              res = 0
              for i in range(len(s)):
                  # 可以构成括号:栈不空 and 当前字符为'(' and 栈顶字符为'('
                  if st and s[i] == ')' and s[st[-1]] == '(':
                      st.pop()   # 弹出栈顶'('
                      # 与最远不能构成括号的下标计算距离,更新最大长度,注意越界
                      res = max(res, i - (st[-1] if st else - 1)) 
                  # 不可以构成括号:栈空 or 当前字符为')' or 栈顶字符为')'
                  else:
                      st.append(i)  # 存入下标
              return res
  • 动态规划

    •  参考题解

    • class Solution:
          def longestValidParentheses(self, s: str) -> int:
              n = len(s)
              if n <= 1: return 0
              dp = [0] * n  # dp[i]表示以s[i]结尾的最长有效括号子串
              res = 0   # 用于更新最大值
              for i in range(1, n):
                  # (),在dp[i-2]基础上直接延续2个
                  if s[i] == ')' and s[i-1] == '(':           
                      dp[i] = dp[i-2] + 2 if i >= 2 else 2    # 防止越界,dp[0]以前为0
                  # )),先看前一个)匹配多长,再看后一个)能否匹配上(,可以的话就+2
                  elif s[i] == ')' and s[i-1] == ')':         
                      sub_len = dp[i-1]  # 前一个)已经匹配的长度
                      if i-sub_len-1 >= 0 and s[i-sub_len-1] == '(':  # 后一个)要找到(才能匹配上
                          last = dp[i-sub_len-2] if i-sub_len-2 >= 0 else 0  # 找到(之前已经匹配多长,防止越界,dp[0]以前为0
                          dp[i] = dp[i-1] + last + 2  # 前一个)匹配的长度 + 后一个)找到(之前已经匹配的长度 + 2
                  res = max(res, dp[i])  # 更新最大值,没有以上情况dp[i]就是0
              return res

后言

  • 最后这道困难题真顶啊,要完全搞懂花了不少时间,这两天继续去巩固dp去
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_56077562/article/details/136579304

【力扣hot100】刷题笔记day1-爱代码爱编程

前言 既然打算年后去找算法的实习,所以之后想直接改用python刷hot100了(新坑芜湖~),在B站大学找到这个刷题教程,先快速过一遍里面提到的python语法 Python数组 # 创建数组 a = [] # 添加元素,O(1) a.append(1) a.append(2) a.append(3) # [1, 2, 3] # 插入元素,O(

【力扣hot100】刷题笔记day14-爱代码爱编程

前言 又是新的一周,快乐的周一,快乐地刷题,今天把链表搞完再干活! 114. 二叉树展开为链表 - 力扣(LeetCode) 前序遍历 class Solution: def flatten(self, root: Optional[TreeNode]) -> None: if not root:

【力扣hot100】刷题笔记day7-爱代码爱编程

前言 身边同学已经陆陆续续回来啦,舍友都开始投简历了,我也要加油啦!刷完hot100就投! 73. 矩阵置零 - 力扣(LeetCode) 标记数组:空间复杂度O(m+n) class Solution: def setZeroes(self, matrix: List[List[int]]) -> None:

【力扣hot100】刷题笔记day2-爱代码爱编程

前言 hot100!开刷!不熟悉python就cv大法先,理清楚思路更重要 哈希 1. 两数之和 - 力扣(LeetCode) 暴力法 能过,遍历两遍求和是否为target class Solution(object): def twoSum(self, nums, target): n = len(nums)

【力扣hot100】刷题笔记day11-爱代码爱编程

前言 科研不顺啊......又不想搞了,随便弄弄吧,多花点时间刷题,今天开启二叉树! 94. 二叉树的中序遍历 - 力扣(LeetCode) 递归 # 最简单递归 class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: i

【力扣hot100】刷题笔记day6-爱代码爱编程

前言 今天是社畜开工第一天,刷题刷题刷题💪 53. 最大子数组和 - 力扣(LeetCode) 贪心法 连续子数组累加和小于零就重新累加,【代码随想录】刷题笔记Day34-CSDN博客 class Solution: def maxSubArray(self, nums: List[int]) -> in

【力扣hot100】刷题笔记day3-爱代码爱编程

前言 以撒真是一不小心就玩太久了,终于解锁骨哥嘞,抓紧来刷题,今天是easy双指针! 283. 移动零 - 力扣(LeetCode) 一个指针遍历找非0,一个指针用于把0换到后面 class Solution(object): def moveZeroes(self, nums): pre = 0 # 用于交换前面的0

【力扣hot100】刷题笔记day5-爱代码爱编程

前言 回学校了,荒废了半天之后打算奋发图强猛猛刷题,找实习!赚钱!! 560. 和为 K 的子数组 - 力扣(LeetCode) 前缀法 + 哈希表 这个题解解释比官方清晰,截个图方便看,另一个题解的代码简洁计算前缀和并统计前缀和个数,遇到相减为k的情况就把前面个数加上 class Solution: def subarraySum(