蓝桥杯思维训练营(三）

题目详解

680.验证回文串 II

680.验证回文串 II

思路分析：这个题目的关键就是，按照正常来判断对应位置是否相等，如果不相等，那么就判断是删除左边的字符还是右边的字符，删除之后如果不满足，则就直接返回False

class Solution:
    def validPalindrome(self, s: str) -> bool:
        n = len(s)
        left, right = 0, n - 1

        def ishui(a, b):
            while a <= b:
                if s[a] != s[b]:
                    return False
                a += 1
                b -= 1
            return True

        while left <= right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                # 尝试跳过左边或右边的一个字符
                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 = 1
        hp = []
        ans = 0
        # 使用小根堆进行存储当前的负数的情况
        for i in range(n):
            # 负数的话就加入
            if nums[i] < 0:
                heapq.heappush(hp,nums[i])
            # 无论正负，都加入cur
            cur+=nums[i]
            # 如果栈中还有元素，并且当前没有血量,就弹出反悔最小的负数
            while hp and cur <= 0:
                p = heapq.heappop(hp)
                ans+=1
                cur+=abs(p)
        return ans

徒步旅行中的补给问题

徒步旅行中的补给问题

思路分析：这个题目的意思是，你首先得购买补给，然后吃一份，也就是在到达下一个补给站的时候只有k-1份补给，在这题中，我们到达一个新的补给站的时候，也购买k份当前补给站的补给，然后将我们背包中的补给全部进行升序排序，留下前k份，吃一份，然后上路，一直持续这个操作

def solution(n, k, data):
    # Edit your code here
    # 策略，还是正常
    cur = 0
    pq = []
    ans = 0
    # 贪心后悔策略
    #
    for i in range(n):
        pq = pq + [data[i]]*k
        pq.sort()
        pq = [pq[i] for i in range(k)]
        # 取出第一个元素
        ans+=pq[0]
        pq.pop(0)
    return ans   


if __name__ == "__main__":
    # Add your test cases here

    print(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 = 0
    ans = -10005
    for i in range(1,n):
        ans = max(ans,values[i]+leftmax+leftmaxf-i)
        if values[i]+i>=leftmax+leftmaxf:
            leftmax=values[i]
            leftmaxf = i
    return ans

if __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)