域名拍卖网站,全国建筑行业资质平台查询官网,国外网站后缀,电子商务网站开发岗位文章目录 题目详解680.验证回文串 II30.魔塔游戏徒步旅行中的补给问题观光景点组合得分问题 题目详解
680.验证回文串 II
680.验证回文串 II 思路分析#xff1a;这个题目的关键就是#xff0c;按照正常来判断对应位置是否相等#xff0c;如果不相等#xff0c;那么就判… 文章目录 题目详解680.验证回文串 II30.魔塔游戏徒步旅行中的补给问题观光景点组合得分问题 题目详解
680.验证回文串 II
680.验证回文串 II 思路分析这个题目的关键就是按照正常来判断对应位置是否相等如果不相等那么就判断是删除左边的字符还是右边的字符删除之后如果不满足则就直接返回False class Solution:def validPalindrome(self, s: str) - bool:n len(s)left, right 0, n - 1def ishui(a, b):while a b:if s[a] ! s[b]:return Falsea 1b - 1return Truewhile left right:if s[left] s[right]:left 1right - 1else:# 尝试跳过左边或右边的一个字符return ishui(left 1, right) or ishui(left, right - 1)return True
30.魔塔游戏
30.魔塔游戏 思路分析总体的思路首先判断sum是否大于0如果不行那么如何调整都不会满足,如果可以满足那么我们从左往右进行遍历分析当目前没有血量的时候就将先前遇到的最小的负数移到末尾(实际上只用恢复cur加回来) 其中如何得到先前遇到的最小负数在这里我们使用小根堆进行存储 import heapq
class Solution:def magicTower(self, nums: List[int]) - int:# 首先判断能否去其实就统计总和是否》0即可。# 在可以到达的时候最多调整次数为负数的次数if not sum(nums)0:return -1# 可以到达# 其实可以统计一个数的左边最小的负数,包含当前的数n len(nums)cur 1hp []ans 0# 使用小根堆进行存储当前的负数的情况for i in range(n):# 负数的话就加入if nums[i] 0:heapq.heappush(hp,nums[i])# 无论正负都加入curcurnums[i]# 如果栈中还有元素并且当前没有血量,就弹出反悔最小的负数while hp and cur 0:p heapq.heappop(hp)ans1curabs(p)return ans徒步旅行中的补给问题
徒步旅行中的补给问题 思路分析这个题目的意思是你首先得购买补给然后吃一份也就是在到达下一个补给站的时候只有k-1份补给在这题中我们到达一个新的补给站的时候也购买k份当前补给站的补给然后将我们背包中的补给全部进行升序排序留下前k份吃一份然后上路一直持续这个操作 def solution(n, k, data):# Edit your code here# 策略还是正常cur 0pq []ans 0# 贪心后悔策略#for i in range(n):pq pq [data[i]]*kpq.sort()pq [pq[i] for i in range(k)]# 取出第一个元素anspq[0]pq.pop(0)return ans if __name__ __main__:# Add your test cases hereprint(solution(5, 2, [1, 2, 3, 3, 2]) 9)
观光景点组合得分问题
观光景点组合得分问题 思路分析对于这题我们肯定是直接进行一次遍历然后边遍历边更新答案即可 不过要注意的是更新的条件中我们不仅要记录values[i]之前的最大的值还要记录下标因为下标也会贡献得分是values[i] i 贡献全部的得分这一点我们通过分解公式可以得出 def solution(values: list) - int:# PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE# write code here# 直接求解出当前values[i]左边的最高的分数n len(values)leftmax values[0]leftmaxf 0ans -10005for i in range(1,n):ans max(ans,values[i]leftmaxleftmaxf-i)if values[i]ileftmaxleftmaxf:leftmaxvalues[i]leftmaxf ireturn ansif __name__ __main__:print(solution(values[8, 3, 5, 5, 6]) 11)print(solution(values[10, 4, 8, 7]) 16)print(solution(values[1, 2, 3, 4, 5]) 8)
