leetcode在力扣 App 中打开
调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
相关企业
提示

给你一个整数 n 和一个下标从 0 开始的整数数组 sick ,数组按 升序 排序。

有 n 位小朋友站成一排,按顺序编号为 0 到 n - 1 。数组 sick 包含一开始得了感冒的小朋友的位置。如果位置为 i 的小朋友得了感冒,他会传染给下标为 i - 1 或者 i + 1 的小朋友,前提 是被传染的小朋友存在且还没有得感冒。每一秒中, 至多一位 还没感冒的小朋友会被传染。

经过有限的秒数后,队列中所有小朋友都会感冒。感冒序列 指的是 所有 一开始没有感冒的小朋友最后得感冒的顺序序列。请你返回所有感冒序列的数目。

由于答案可能很大,请你将答案对 109 + 7 取余后返回。

注意,感冒序列 包含一开始就得了感冒的小朋友的下标。

 

示例 1:

输入:n = 5, sick = [0,4]
输出:4
解释:一开始,下标为 1 ,2 和 3 的小朋友没有感冒。总共有 4 个可能的感冒序列:
- 一开始,下标为 1 和 3 的小朋友可以被传染,因为他们分别挨着有感冒的小朋友 0 和 4 ,令下标为 1 的小朋友先被传染。
然后,下标为 2 的小朋友挨着感冒的小朋友 1 ,下标为 3 的小朋友挨着感冒的小朋友 4 ,两位小朋友都可以被传染,令下标为 2 的小朋友被传染。
最后,下标为 3 的小朋友被传染,因为他挨着感冒的小朋友 2 和 4 ,感冒序列为 [1,2,3] 。
- 一开始,下标为 1 和 3 的小朋友可以被传染,因为他们分别挨着感冒的小朋友 0 和 4 ,令下标为 1 的小朋友先被传染。
然后,下标为 2 的小朋友挨着感冒的小朋友 1 ,下标为 3 的小朋友挨着感冒的小朋友 4 ,两位小朋友都可以被传染,令下标为 3 的小朋友被传染。
最后,下标为 2 的小朋友被传染,因为他挨着感冒的小朋友 1 和 3 ,感冒序列为  [1,3,2] 。
- 感冒序列 [3,1,2] ,被传染的顺序:[0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] 。
- 感冒序列 [3,2,1] ,被传染的顺序:[0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] => [0,1,2,3,4] 。

示例 2:

输入:n = 4, sick = [1]
输出:3
解释:一开始,下标为 0 ,2 和 3 的小朋友没有感冒。总共有 3 个可能的感冒序列:
- 感冒序列 [0,2,3] ,被传染的顺序:[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3] 。
- 感冒序列 [2,0,3] ,被传染的顺序:[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3] 。
- 感冒序列 [2,3,0] ,被传染的顺序:[0,1,2,3] => [0,1,2,3] => [0,1,2,3] => [0,1,2,3] 。

 

提示:

  • 2 <= n <= 105
  • 1 <= sick.length <= n - 1
  • 0 <= sick[i] <= n - 1
  • sick 按升序排列。
通过次数
1.7K
提交次数
4.3K
通过率
40.0%


相关企业

提示 1
Consider infected children as 0 and non-infected as 1, then divide the array into segments with the same value.

提示 2
For each segment of non-infected children whose indices are [i, j] and indices (i - 1) and (j + 1), if they exist, are already infected. Then if i == 0 or j == n - 1, each second there is only one kid that can be infected (which is at the other endpoint).

提示 3
If i > 0 and j < n - 1, we have two choices per second since the children at the two endpoints can both be the infect candidates. So there are 2j - i orders to infect all children in the segment.

提示 4
Each second we can select a segment and select one endpoint from it.

提示 5
The answer is: S! / (len[1]! * len[2]! * ... * len[m]! * lenstart! * lenend!) * 2k where len[1], len[2], ..., len[m] are the lengths of each segment of non-infected children that have an infected child at both endpoints, lenstart and lenend denote the number of non-infected children with infected child at one endpoint, S is the total length of all segments of non-infected children, and k = (len[1] - 1) + (len[2] - 1) + ... + (len[m] - 1).


评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
n =
5
sick =
[0,4]
Source