外贸仿牌网站,赣州人才网找工作,网站上传图片问题,找回老网站参考灵神和闫总的讲解和代码#xff1a; https://www.bilibili.com/video/BV1rP411s7Z5 https://space.bilibili.com/206214
7006. 销售利润最大化
https://leetcode.cn/problems/maximize-the-profit-as-the-salesman/
Solution
动态规划 哈希表
首先按照 end 的顺序分…参考灵神和闫总的讲解和代码 https://www.bilibili.com/video/BV1rP411s7Z5 https://space.bilibili.com/206214
7006. 销售利润最大化
https://leetcode.cn/problems/maximize-the-profit-as-the-salesman/
Solution
动态规划 哈希表
首先按照 end 的顺序分组每个组记录所有以 end 为终点的区间。
f[i1] 表示不超过 i 的房屋的最大盈利。
若编号 i 的房屋不卖从上一个编号转移过来f[i 1] f[i]若卖需要遍历所有以 i 为终点的区间找出最大的 f[s] g取最大即可
class Solution:def maximizeTheProfit(self, n: int, offers: List[List[int]]) - int:groups [[] for _ in range(n)]for s, e, g in offers:groups[e].append((s, g))# f[i1] 表示编号不超过 i 的房屋的最大盈利f [0] * (n 1)for end, group in enumerate(groups):# 不选f[end 1] f[end]for s, g in group:# 选f[end 1] max(f[end 1], f[s] g)return f[n]
6467. 找出最长等值子数组
https://leetcode.cn/problems/find-the-longest-equal-subarray/
Solution
同相双指针 class Solution:def longestEqualSubarray(self, nums: List[int], k: int) - int:pos [[] for _ in range(len(nums) 1)]for i, x in enumerate(nums):pos[x].append(i)ans 0for ps in pos:left 0for right, p in enumerate(ps):while p - ps[left] - (right - left) k:left 1ans max(ans, right - left 1)return ansSolution
暴力方法
class Solution:def minimumOperations(self, nums: List[int]) - int:# 暴力方法res n len(nums)for i in range(n 1):for j in range(n - i 1):cnt 0for k in range(n):t -1if k i - 1:t 1elif k i j - 1:t 2else:t 3# 有多少不同if t ! nums[k]:cnt 1res min(res, cnt)return res最长子序列 https://leetcode.cn/u/xiongxyowo/ 最长递增子序列。为了在最少操作次数内使得数组有序我们只需要对不在最长递增子序列中的元素进行修改使其满足递增要求即可。也就是求原数组长度减去最长递增子序列长度。 例如[1,3,2,1,3,3] 的最长递增子序列为 [1,-,2,-,3,3]我们只需要修改 [-,3,-,1,-,-] 即可。代码如下 class Solution:def minimumOperations(self, nums: List[int]) - int:n len(nums)dp [1] * nfor i in range(1, n):for j in range(0, i):if nums[i] nums[j]:dp[i] max(dp[i], dp[j] 1)return n - max(dp)DP
最少修改多少个数字可以使数组非递减。定义 a, b, c 分别表示以 1, 2, 3 结尾的前缀数组需要修改的最小次数。
class Solution:def minimumOperations(self, nums: List[int]) - int:a, b, c 0, 0, 0for x in nums:aa, bb, cc a, b, cif x 1:a aa # 因为本身就是 1所以不用修改b min(aa, bb) 1c min(aa, bb, cc) 1elif x 2:a aa 1b min(aa, bb)c min(aa, bb, cc) 1else:a aa 1b min(aa, bb) 1c min(aa, bb, cc)return min(a, b, c)
