做网站的人会不会拿走我的网站,wordpress 列表页输出,asp iis设置网站路径,手机网站seo免费软件记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 3/25 518. 零钱兑换 II3/26 2642. 设计可以求最短路径的图类3/27 2580. 统计将重叠区间合并成组的方案数3/28 1997. 访问完所有房间的第一天3/29 2908. 元素和最小的山形三…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 3/25 518. 零钱兑换 II3/26 2642. 设计可以求最短路径的图类3/27 2580. 统计将重叠区间合并成组的方案数3/28 1997. 访问完所有房间的第一天3/29 2908. 元素和最小的山形三元组 I3/30 2952. 需要添加的硬币的最小数量3/31 331. 验证二叉树的前序序列化 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: intn len(coins)dp [[0]*(amount1) for _ in range(n1)]for i in range(1,n1):dp[i][0] 1for i in range(1,n1):for j in range(1,amount1):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: intn len(coins)dp [0]*(amount1)dp[0]1for i in range(1,n1):for j in range(coins[i-1],amount1):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: Noneself.m[edge[0]].append((edge[1],edge[2]))def shortestPath(self, node1, node2)::type node1: int:type node2: int:rtype: intimport heapqdis [float(inf)]*len(self.m)dis[node1] 0h [(0,node1)]while h:d,nxt heapq.heappop(h)if nxtnode2:return dif d dis[nxt]:continuefor y,v in self.m[nxt]:if dv dis[y]:dis[y] dvheapq.heappush(h,(dis[y],y))return -1 3/27 2580. 统计将重叠区间合并成组的方案数 按起始位置从小到大排序 记录有多少个单独的区间 num 每个单独区间都可以选择第一组或第二组 所以有2^num种方案 def countWays(ranges)::type ranges: List[List[int]]:rtype: intranges.sort(keylambda x:x[0])num 0prer -1for l,r in ranges:if lprer:num 1prer max(prer,r)MOD10**97return pow(2,num,MOD) 3/28 1997. 访问完所有房间的第一天 第一次访问i 为奇数必定要返回左侧的nextVisit 只有第二次访问i 才能继续下一步i1 此时i1左侧必定都访问了偶数次 定义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: intn len(nextVisit)MOD 10**97dp [0]*nfor i in range(1,n):dp[i] (2*dp[i-1]-dp[nextVisit[i-1]]2)%MODreturn 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: intn len(nums)l [float(inf)]*nr [float(inf)]*ncur nums[0]for i in range(1,n):if curnums[i]:l[i]curelse:cur nums[i]cur nums[-1]for i in range(n-2,-1,-1):if curnums[i]:r[i]curelse: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]的情况 如果xcoins[i] s 那么可以继续得到区间s~sx-1之间的情况 如果xs 那么我们无法得到[s,x-1]之间的数 所以必须添加s进入数组中 得到[s,2s-1] 下一个将考虑2*s的情况 def minimumAddedCoins(coins, target)::type coins: List[int]:type target: int:rtype: intcoins.sort()ans 0s 1i 0while starget:if ilen(coins) and coins[i]s:s coins[i]i1else:s*2ans1return ans 3/31 331. 验证二叉树的前序序列化 1.计算叶节点个数 添加一个数值必定有两个叶节点包括#2,每一个值也必定是一个叶节点(-1) 最终叶节点剩余值为0 2.将节点压入栈中根据根左右顺序如果压入的是叶节点必定左右为# 及后面两个为# 则可以将这个叶节点取出用#代替 最终stack中只剩一个# def isValidSerialization(preorder)::type preorder: str:rtype: booll preorder.split(,)leaf 1for i in l:leaf -1if leaf0:return Falseif i!#:leaf2return leaf0def isValidSerialization2(preorder)::type preorder: str:rtype: booll preorder.split(,)if len(l)1 and (l[-1]!# or l[-2]!#):return Falsestack []for i in l:stack.append(i)if len(stack)2:continuewhile stack[-1]# and stack[-2]#:if len(stack)2 or stack[-3]#:return Falsestack.pop()stack.pop()stack.pop()stack.append(#)if len(stack)1:breakif len(stack)1 and stack[0]#:return Trueelse:return False
