leetcode 第 321 场算法比赛

零、背景

之前提到，我拉了一个算法群，用于分享 leetcode 每日一题的题解以及算法咨询讨论。
对算法感兴趣的朋友可以关注公众号，在对话框里回复 “算法群” 获得进群方法。

最近七天（11-20~11-26）每日一题，有 4 道比较难的题，如果你都做了，那就赚大了。

2022-11-21 第 808 题，数据范围小时使用概率动态规划计算，数据范围大时直接答案固定。
2022-11-23 第 1742 题附加思考题：数位动态规划，参加比赛的同学建议都学习下，比较经典的DP。
2022-11-26 第 882 题，有条件的单源最短路，图论题。

一、找出中枢整数

题意：求找一个 x，使得 1 到 x 的自然数之和等于 x 到 n 的自然数之和。

思路1：枚举判断即可。
思路2：解方程，直接开放计算。

二、追加字符以获得子序列

题意：问 a 数组后缀最少追加多少数字，才能使得存在子序列与 b 数组相等。

思路：数组 b 维护一个游标，扫描 a 数组，与 b 数组的游标相等了，游标后移一位。
最后游标后面的数字个数，就是需要最加的。

三、从链表中移除节点

题意：给一个链表，如果后面节点大于前面节点，删除前面的节点。求删除后的链表。

思路：递归删除即可，优先处理后面的，然后判断当前节点是否需要删除。

四、统计中位数为 K 的子数组

题意：给 n 个数字的排列和一个数字 k，问中位数是 k 的子数组个数。

思路：对于一个子数组，不需要关心具体的值，只关心小于 k 与大于 k 的数字个数的差值，看是否相等。

所以可以预处理 k 位置前面，以 k 为后缀的所有子数组（称为前数组）的差值，储存在 hash 中。
然后枚举所有以 k 为前缀的子数组（称为后数组），再次计算出差值 d。

如果 k 是一位中位数，则前数组和后数组的差值应该相反，差值之和就是 0。
如果 k 是两位中位数，题目要求k需要在左边，所以大于k的数字比小于k的数字多一个，差值之和应该是 -1.

分别统计满足上面两种情况的个数即可。

五、最后

这次比赛题目都不难，通过四道题的同学应该很多吧。

你那道题卡住了吗？卡在哪里了？

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code