记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
3/25 518. 零钱兑换 II
完全背包问题
1.动态规划
前i个面额可以凑出j的方法
dp[i][j] = dp[i-1][j]+dp[i][j-coins[i-1]]
2.压缩 二维变一维
因为可以无限次数使用 所以j无需逆序考虑
def change(amount, coins):
"""
:type amount: int
:type coins: List[int]
:rtype: int
"""
n = len(coins)
dp = [[0]*(amount+1) for _ in range(n+1)]
for i in range(1,n+1):
dp[i][0] = 1
for i in range(1,n+1):
for j in range(1,amount+1):
if j - coins[i-1]>=0:
dp[i][j] = dp[i-1][j]+dp[i][j-coins[i-1]]
else:
dp[i][j] = dp[i-1][j]
return dp[n][amount]
def change2(amount, coins):
"""
:type amount: int
:type coins: List[int]
:rtype: int
"""
n = len(coins)
dp = [0]*(amount+1)
dp[0]=1
for i in range(1,n+1):
for j in range(coins[i-1],amount+1):
dp[j] += dp[j-coins[i-1]]
return dp[amount]
3/26 2642. 设计可以求最短路径的图类
m为邻接表 m[x]=(y,v)表示节点x能到达y并且长度为v
dijkstra
dis[x]用来存放开始节点到当前x节点最短距离
堆用来保存当前可达的所有节点 距离短的优先处理
class Graph(object):
def __init__(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
"""
self.m = [[] for _ in range(n)]
for x,y,v in edges:
self.m[x].append((y,v))
def addEdge(self, edge):
"""
:type edge: List[int]
:rtype: None
"""
self.m[edge[0]].append((edge[1],edge[2]))
def shortestPath(self, node1, node2):
"""
:type node1: int
:type node2: int
:rtype: int
"""
import heapq
dis = [float("inf")]*len(self.m)
dis[node1] = 0
h = [(0,node1)]
while h:
d,nxt = heapq.heappop(h)
if nxt==node2:
return d
if d > dis[nxt]:
continue
for y,v in self.m[nxt]:
if d+v < dis[y]:
dis[y] = d+v
heapq.heappush(h,(dis[y],y))
return -1
3/27 2580. 统计将重叠区间合并成组的方案数
按起始位置从小到大排序
记录有多少个单独的区间 num
每个单独区间都可以选择第一组或第二组
所以有2^num种方案
def countWays(ranges):
"""
:type ranges: List[List[int]]
:rtype: int
"""
ranges.sort(key=lambda x:x[0])
num = 0
prer = -1
for l,r in ranges:
if l>prer:
num +=1
prer = max(prer,r)
MOD=10**9+7
return pow(2,num,MOD)
3/28 1997. 访问完所有房间的第一天
第一次访问i 为奇数必定要返回左侧的nextVisit
只有第二次访问i 才能继续下一步i+1
此时i+1左侧必定都访问了偶数次
定义dp[i]为第一次访问i的时间
dp[i-1]为第一次访问i-1的时间
此时从i-1花一天时间回退到nextVisit[i-1]
nextVisit[i-1]出为奇数次访问 nextVisit[i-1]+1~i-2为偶数次访问
此时相当于nextVisit[i-1]被第一次访问
所以再次到i-1步数为dp[i-1]-dp[nextVisit[i-1]]
再花一天可以到达i
所以dp[i]=dp[i-1]+1+(dp[i-1]-dp[nextVisit[i-1]])+1
dp[i]=2*dp[i-1]-dp[nextVisit[i-1]]+2
def firstDayBeenInAllRooms(nextVisit):
"""
:type nextVisit: List[int]
:rtype: int
"""
n = len(nextVisit)
MOD = 10**9+7
dp = [0]*n
for i in range(1,n):
dp[i] = (2*dp[i-1]-dp[nextVisit[i-1]]+2)%MOD
return dp[-1]
3/29 2908. 元素和最小的山形三元组 I
先从左到右 l[i]记录位置i左侧比它小的最小值
同理从右到左 r[i]记录位置i右侧比它小的最小值
寻找最小和l[i]+r[i]+nums[i]
def minimumSum(nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
l = [float("inf")]*n
r = [float("inf")]*n
cur = nums[0]
for i in range(1,n):
if cur<nums[i]:
l[i]=cur
else:
cur = nums[i]
cur = nums[-1]
for i in range(n-2,-1,-1):
if cur<nums[i]:
r[i]=cur
else:
cur = nums[i]
ans = min([l[i]+r[i]+nums[i] for i in range(n)])
return ans if ans!=float("inf") else -1
3/30 2952. 需要添加的硬币的最小数量
从小到大排序
假设当前位置为i 目标总和为s 已得到[0,s-1]的情况
如果x=coins[i] <=s
那么可以继续得到区间s~s+x-1之间的情况
如果x>s
那么我们无法得到[s,x-1]之间的数
所以必须添加s进入数组中 得到[s,2s-1] 下一个将考虑2*s的情况
def minimumAddedCoins(coins, target):
"""
:type coins: List[int]
:type target: int
:rtype: int
"""
coins.sort()
ans = 0
s = 1
i = 0
while s<=target:
if i<len(coins) and coins[i]<=s:
s += coins[i]
i+=1
else:
s*=2
ans+=1
return ans
3/31 331. 验证二叉树的前序序列化
1.计算叶节点个数 添加一个数值必定有两个叶节点（包括#）+2,每一个值也必定是一个叶节点(-1) 最终叶节点剩余值为0
2.将节点压入栈中，根据根左右顺序如果压入的是叶节点必定左右为# 及后面两个为# 则可以将这个叶节点取出用#代替 最终stack中只剩一个#
def isValidSerialization(preorder):
"""
:type preorder: str
:rtype: bool
"""
l = preorder.split(",")
leaf = 1
for i in l:
leaf -=1
if leaf<0:
return False
if i!="#":
leaf+=2
return leaf==0
def isValidSerialization2(preorder):
"""
:type preorder: str
:rtype: bool
"""
l = preorder.split(",")
if len(l)>1 and (l[-1]!="#" or l[-2]!="#"):
return False
stack =[]
for i in l:
stack.append(i)
if len(stack)<2:
continue
while stack[-1]=="#" and stack[-2]=="#":
if len(stack)==2 or stack[-3]=="#":
return False
stack.pop()
stack.pop()
stack.pop()
stack.append("#")
if len(stack)==1:
break
if len(stack)==1 and stack[0]=="#":
return True
else:
return False
