律师网站素材,推荐好用的浏览器,网站开发销售怎么做,湖南吧文章目录 子集II1191.K次串联后最大子数组之和 子集II
子集II 思路分析#xff1a; 求解子集的问题的关键就是#xff0c;通过递归与回溯#xff0c;我们就是得确定以某个元素开始的子集#xff0c;对于这个题目来说#xff0c;比较麻烦的一点就是#xff0c;存在重复的… 文章目录 子集II1191.K次串联后最大子数组之和 子集II
子集II 思路分析 求解子集的问题的关键就是通过递归与回溯我们就是得确定以某个元素开始的子集对于这个题目来说比较麻烦的一点就是存在重复的元素这样如果不增加一个判断的话会导致我们的结果存在重复的元素 如何消除重复的情况 nums.sort() # 排序方便去重
# 在这个for 训练里面我们是用于选择子集的开始的元素的只要我们开始的元素没有和前一个元素相同那么就可以进行递归增加元素
if i start and nums[i] nums[i-1]:continue整体的代码中我们使用ans 来记录全部的子集path来记录当前的元素的情况 class Solution:def subsetsWithDup(self, nums: List[int]) - List[List[int]]:nums.sort() # 排序方便去重ans []path []def backtrack(start):ans.append(path[:]) # 添加当前子集到结果中for i in range(start, len(nums)):# 跳过重复元素if i start and nums[i] nums[i-1]:continuepath.append(nums[i]) # 选择当前元素backtrack(i 1) # 递归path.pop() # 撤销选择backtrack(0)return ans
1191.K次串联后最大子数组之和
1191.K次串联后最大子数组之和 思路分析由于k和arr数组长度都很长所以不可能全部拼接起来所以说就根本不用全部拼接起来 规律当k1的时候就是正常算如果K2的时候我们可以先拼接两个进行正常运算如果max(dp) 小于等于0则返回0然后我们思考这两段之间能否插入剩余的段所以我们计算sum(arr),如果sum(arr)0,就可以拼接在两段之间否则就直接返回两段的情况记得要取模再返回 class Solution:def kConcatenationMaxSum(self, arr: List[int], k: int) - int:# 肯定是不能直接拼接上去再dp的不然o(n)的时间复杂度也到了10^10,所以还是在之前的数组arr操作#n len(arr)ans 0if k 1:dp [0]*ndp[0] arr[0]for i in range(1,n):dp[i] max(dp[i-1]arr[i],arr[i])# 判断ans,如果小于等于0就返回0否则就是取模返回ans max(dp)return ans%(10**97) if ans 0 else 0else:dp [0]*(2*n)dp[0] arr[0]# 拼接nums arr arrfor i in range(1,2*n):dp[i] max(dp[i-1]nums[i],nums[i])# 查看最大值ans max(dp)# 小于等于0就返回if ans0:return 0sumarr sum(arr)# 看看能否插入其中if sumarr0:return (ans(k-2)*sumarr)%(10**97)else:return ans%(10**97)
