蓝桥杯思维训练营(三）

题目详解

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])# 无论正负，都加入curcur+=nums[i]# 如果栈中还有元素，并且当前没有血量,就弹出反悔最小的负数while hp and cur <= 0:p = heapq.heappop(hp)ans+=1cur+=abs(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)]# 取出第一个元素ans+=pq[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]+leftmax+leftmaxf-i)if values[i]+i>=leftmax+leftmaxf:leftmax=values[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)