龙华app网站开发,网站建设成交话术,天津商城网站建设,山东省作风建设网站前言
这几天搞工作处理数据真是类似我也#xff0c;还被老板打电话push压力有点大的#xff0c;还好搞的差不多了#xff0c;明天再汇报#xff0c;赶紧偷闲再刷几道题#xff08;可恶#xff0c;被打破连更记录了#xff09;这几天刷的是动态规划#xff0c;由于很成…前言
这几天搞工作处理数据真是类似我也还被老板打电话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_length1): # 遍历结束指针ifor j in range(i): # 遍历开始指针jif 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 # 结果先取1for i in range(1, n):for j in range(i):if nums[i] nums[j]: # 只要比前面的递增子串长度1dp[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 0for 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 0dp [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# ))先看前一个)匹配多长再看后一个)能否匹配上(可以的话就2elif 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]以前为0dp[i] dp[i-1] last 2 # 前一个)匹配的长度 后一个)找到(之前已经匹配的长度 2res max(res, dp[i]) # 更新最大值没有以上情况dp[i]就是0return res
后言
最后这道困难题真顶啊要完全搞懂花了不少时间这两天继续去巩固dp去
