LeetCode 每日一题 2023/4/17-2023/4/23

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

4/17 2409. 统计共同度过的日子数

在同一年 可以将日期转化成该年第几天

def countDaysTogether(arriveAlice, leaveAlice, arriveBob, leaveBob):""":type arriveAlice: str:type leaveAlice: str:type arriveBob: str:type leaveBob: str:rtype: int"""mon = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]d = [0]*12for i in range(1,12):d[i] = d[i-1]+mon[i-1]def trans(date):m = int(date[:2])ind = d[m-1]ind += int(date[-2:])return indaA = trans(arriveAlice)aB = trans(arriveBob)lA = trans(leaveAlice)lB = trans(leaveBob)if aA>lB or aB>lA:return 0return min(lA,lB)-max(aA,aB)+1

4/18 1026. 节点与其祖先之间的最大差值

从根节点往子节点判断 记录当前最大值和最小值
当前节点与最大值最小值能够得到的最大差值

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right
def maxAncestorDiff(root):""":type root: TreeNode:rtype: int"""global ansans = 0def check(node,minv,maxv):global ansif not node:returnans = max(ans,abs(minv-node.val))ans = max(ans,abs(maxv-node.val))minv = min(node.val,minv)maxv = max(node.val,maxv)check(node.left,minv,maxv)check(node.right,minv,maxv)check(root,root.val,root.val)return ans

4/19 1043. 分隔数组以得到最大和

dp
dp[i]为以i结尾分割的最大和
倒序枚举i-k<=j<=i-1 以j为结尾分割为另一部分
dp[i] = max(dp[j]+maxv*(i-j))

def maxSumAfterPartitioning(arr, k):""":type arr: List[int]:type k: int:rtype: int"""n = len(arr)dp = [0]*(n+1)for i in range(1,n+1):maxv=arr[i-1]for j in range(i-1,max(-1,i-k-1),-1):dp[i] = max(dp[i],dp[j]+maxv*(i-j))if j>0:maxv=max(maxv,arr[j-1])return dp[n]

4/20 1187. 使数组严格递增

设定dp[i]为不替换arr1[i]能够满足条件的最小替换次数
在arr1头尾增加负无穷 正无穷
如果arr1[i]前替换为0个 要满足arr1[i-1]<arr1[i] 此时dp[i]=min(dp[i],dp[i-1])
如果arr1[i]前替换k个 在arr2中找到第一个大于arr1[i]的位置arr2[j]
k必定小于i 小于j 遍历所有可能的k值
需要满足arr[i-1-k]<arr2[j-k] 此时可以替换arr[i-k]~arr[i-1]之间k个数

def makeArrayIncreasing(arr1, arr2):""":type arr1: List[int]:type arr2: List[int]:rtype: int"""import bisectarr2 = sorted(list(set(arr2)))arr = [float("-inf")]+arr1+[float("inf")]n = len(arr)dp=[float("inf")]*ndp[0]=0for i in range(1,n):if arr[i-1]<arr[i]:dp[i]=dp[i-1]j = bisect.bisect_left(arr2,arr[i])for k in range(1,min(i-1,j)+1):if arr[i-k-1]<arr2[j-k]:dp[i] = min(dp[i],dp[i-k-1]+k)if dp[n-1]==float("inf"):return -1return dp[n-1]

4/21 2413. 最小偶倍数

如果n是偶数就是n 如果是奇数则是2*n

def smallestEvenMultiple(n):""":type n: int:rtype: int"""return n if n%2==0 else n*2

4/22 1027. 最长等差数列

求数组数值的最大值 最小值
可以得到在数组内两数之差最大为diff=maxv-minv
遍历每一种可能的差值d=[-diff,diff]
遍历每一个数num 判断其num-d在之前是否出现以及最大长度

def longestArithSeqLength(self, nums):""":type nums: List[int]:rtype: int"""from collections import defaultdictminv= min(nums)maxv= max(nums)diff=maxv-minvans = 1for d in range(-diff,diff+1):mem = defaultdict(int)for num in nums:prev = num-dif mem[prev]>0:mem[num] = max(mem[num],mem[prev]+1)ans = max(ans,mem[num])mem[num] = max(mem[num],1)return ans

4/23