題目詳解

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)