前言
继续leetcode刷题生涯
这里记录的都是笔者觉得有点意思的做法
参考了好几位大佬的题解，感谢各位大佬
1184. 公交站间的距离
class Solution:def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:s1 = sum(distance[start:destination]) if destination > start else sum(distance[destination:start])return min(sum(distance)-s1,s1)
1185. 一周中的第几天
class Solution:def dayOfTheWeek(self, day: int, month: int, year: int) -> str:if (month == 1 or month == 2):month += 12year -= 1iWeek = (day+2*month+3*(month+1)//5+year+year//4-year//100+year//400)%7result = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday","Sunday"]return result[iWeek]
1186. 删除一次得到子数组最大和
class Solution:def maximumSum(self, arr: List[int]) -> int:n = len(arr)if n == 1: return arr[0]dp1, dp2 = [0] * n, [0] * ndp1[0] = arr[0]dp1[1] = max(arr[1], dp1[0] + arr[1])dp2[0] = 0dp2[1] = max(arr[0], arr[1])res = max(dp1[0], dp1[1], dp2[1])for i in range(2, n):dp1[i] = max(arr[i], dp1[i-1] + arr[i])dp2[i] = max(dp2[i-1], dp1[i-2]) + arr[i]res = max(res, dp1[i], dp2[i])return res
1187. 使数组严格递增
''' 动态规划，看序列arr1最后一个数值怎么处理，要么把它放大，让前面的序列比较容易凑出来，这样会有一次开销 要么不变，把前面的序列的数值缩小，去把前面的子串凑成合法的，两种策略取交换次数少的作为答案dp(i, max_val) 表示 把arr1[:i+1] 转成最大值不超过max_val的严格递增子串的最少操作次数如果扩大最后一个数字 备选答案是 1 + dp(i, replace_val-1) replace_val是arr2中小于等于max_val的最大的值，可以二分找出来如果最后一个数字不变 备选答案是 dp(i-1, arr1[i]-1)两个备选答案选较大者，记忆化递归进行递推'''from typing import List
from functools import lru_cache
class Solution:def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:arr = list(set(arr2))arr.sort()# 把arr1[:i+1] 转成最大值不超过max_val的严格递增子串的最少操作次数@lru_cache(typed=False, maxsize=128000000)def dp(i, max_val) -> int:if i == -1:return 0l, r = 0, len(arr)-1# 找小于等于max_val的最大的数pos = -1while l <= r:mid = l + (r-l) //2if arr[mid] <= max_val:pos = midl = mid + 1else:r = mid - 1if arr1[i] <= max_val:ans = dp(i-1, arr1[i]-1)if pos != -1 and arr[pos] > arr1[i]:ret = dp(i-1, arr[pos]-1)if ret != -1:if ans == -1 or ret + 1 < ans:ans = ret + 1return anselse:if pos == -1:return -1ret = dp(i - 1, arr[pos] - 1)return ret + 1 if ret != -1 else -1return dp(len(arr1)-1, 0x7fffffff)1189. “气球” 的最大数量
class Solution:def maxNumberOfBalloons(self, text: str) -> int:return min(text.count('a'),text.count('b'),text.count('n'),text.count('l')//2,text.count('o')//2)1190. 反转每对括号间的子串
class Solution:def reverseParentheses(self, s: str) -> str:res = ['']for w in s:if w == '(':res += ['']elif w == ')':res[-2] += res[-1][:: -1]res.pop()else:res[-1] += wreturn res[0]