专栏名称: LeetCode(微博搜索)

LeetCode(微博搜索)-20230910-1

LeetCode(微博搜索) · 微博搜索 · · 2023-09-10 00:00

正文

本条微博地址 gitpush-force
关注我，每天59秒拿下每日一题
国区每日一题今日思路：
拓扑排序问题。首先预处理先修课程，将其转化为图同时统计入度，这里我使用的是邻接链表，稀疏图的情况下比较节省空间。然后将所有入度为0的节点入队，将与队列中节点相邻的节点减度，若度为0将其入队；重复这一操作直至队列为空。最后判断度为0的节点数是否等于课程总数即可。这道题唯一和昨天不同的是，入队的同时将其加入答案数组，即可得到一种可能的顺序。
国际站每日一题今日思路：
这道题可以用插隔板的方法去做，感兴趣的可以去看题解。我这里给出一种动态规划的方法，记dp[i][j]为执行第i个订单，且已经完成j个收件情况下的总可能数，那么答案为dp[2n][n]，初始状态dp[0][0]=1，dp[i][j]=dp[i-1][j]*(j-(i-1-j))+dp[i-1][j-1]*(n-j+1) ,注意取模。状态转移为两种，一种当前选取的为配送，此时只能从已经收件的订单中选取，但是已经配送了(i-1-j)个订单，将这部分已配送减去。第二种为当前选取收件，那么一共有n-(j-1)中选择，即从未收件的订单任取一个。这里还需要注意因为收件必须在配件之前，所以i个订单，至少有i/2向上取整个收件。
#leetcode# #每日一题# #每天59秒拿下每日一题#

本条微博地址快乐批发市场_
leetcode刷题体验感yyds

本条微博地址前端开发博客
12 个练习编码的网站🚀

✦ codewars.com：