fork()==0世界线变动

1621. 大小为 K 的不重叠线段的数目

给你一维空间的 n 个点，其中第 i 个点（编号从 0 到 n-1）位于 x = i 处，请你找到 恰好 k 个不重叠 线段且每个线段至少覆盖两个点的方案数。线段的两个端点必须都是 整数坐标 。这 k 个线段不需要全部覆盖全部 n 个点，且它们的端点 可以 重合。

请你返回 k 个不重叠线段的方案数。由于答案可能很大，请将结果对 10^9 + 7 取余 后返回。

示例 1：

```txt

输入：n = 4, k = 2

输出：5

解释：

如图所示，两个线段分别用红色和蓝色标出。

上图展示了 5 种不同的方案 {(0,2),(2,3)}，{(0,1),(1,3)}，{(0,1),(2,3)}，{(1,2),(2,3)}，{(0,1),(1,2)} 。

```

示例 2：

```txt

输入：n = 3, k = 1

输出：3

解释：总共有 3 种不同的方案 {(0,1)}, {(0,2)}, {(1,2)} 。

```

示例 3：

```txt

输入：n = 30, k = 7

输出：796297179

解释：画 7 条线段的总方案数为 3796297200 种。将这个数对 109 + 7 取余得到 796297179 。

```

示例 4：

```txt

输入：n = 5, k = 3

输出：7

```

示例 5：

```txt

输入：n = 3, k = 2

输出：1

```

提示：

• 2 <= n <= 1000

• 1 <= k <= n-1

100127. 给小朋友们分糖果 II

给你两个正整数 n 和 limit 。

请你将 n 颗糖果分给 3 位小朋友，确保没有任何小朋友得到超过 limit 颗糖果，请你返回满足此条件下的 总方案数 。

示例 1：

```txt

输入：n = 5, limit = 2

输出：3

解释：总共有 3 种方法分配 5 颗糖果，且每位小朋友的糖果数不超过 2 ：(1, 2, 2) ，(2, 1, 2) 和 (2, 2, 1) 。

```

示例 2：

```txt

输入：n = 3, limit = 3

输出：10

解释：总共有 10 种方法分配 3 颗糖果，且每位小朋友的糖果数不超过 3 ：(0, 0, 3) ，(0, 1, 2) ，(0, 2, 1) ，(0, 3, 0) ，(1, 0, 2) ，(1, 1, 1) ，(1, 2, 0) ，(2, 0, 1) ，(2, 1, 0) 和 (3, 0, 0) 。

```

提示：

• 1 <= n <= 10^6

• 1 <= limit <= 10^6

2514. 统计同位异构字符串数目

给你一个字符串 s ，它包含一个或者多个单词。单词之间用单个空格 ' ' 隔开。

如果字符串 t 中第 i 个单词是 s 中第 i 个单词的一个 排列 ，那么我们称字符串 t 是字符串 s 的同位异构字符串。

• 比方说，"acb dfe" 是 "abc def" 的同位异构字符串，但是 "def cab" 和 "adc bef" 不是。

请你返回 s 的同位异构字符串的数目，由于答案可能很大，请你将它对 10^9 + 7 取余 后返回。

示例 1：

```txt

输入：s = "too hot"

输出：18

解释：输入字符串的一些同位异构字符串为 "too hot" ，"oot hot" ，"oto toh" ，"too toh" 以及 "too oht" 。

```

示例 2：

```txt

输入：s = "aa"

输出：1

解释：输入字符串只有一个同位异构字符串。

```

提示：

• 1 <= s.length <= 10^5

• s 只包含小写英文字母和空格 ' ' 。

• 相邻单词之间由单个空格隔开。

2954. 统计感冒序列的数目

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

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

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

由于答案可能很大，请你将答案对 10^9 + 7 取余后返回。

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

示例 1：

```txt

输入：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：

```txt

输入：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 <= 10^5

• 1 <= sick.length <= n - 1

• 0 <= sick[i] <= n - 1

• sick 按升序排列。

100126. 重新排列后包含指定子字符串的字符串数目

给你一个整数 n 。

如果一个字符串 s 只包含小写英文字母，且 将 s 的字符重新排列后，新字符串包含 子字符串 "leet" ，那么我们称字符串 s 是一个 好 字符串。

比方说：

• 字符串 "lteer" 是好字符串，因为重新排列后可以得到 "leetr" 。

• "letl" 不是好字符串，因为无法重新排列并得到子字符串 "leet" 。

请你返回长度为 n 的好字符串 总 数目。

由于答案可能很大，将答案对 10^9 + 7 取余 后返回。

子字符串 是一个字符串中一段连续的字符序列。

示例 1：

```txt

输入：n = 4

输出：12

解释：总共有 12 个字符串重新排列后包含子字符串 "leet" ："eelt" ，"eetl" ，"elet" ，"elte" ，"etel" ，"etle" ，"leet" ，"lete" ，"ltee" ，"teel" ，"tele" 和 "tlee" 。

```

示例 2：

```txt

输入：n = 10

输出：83943898

解释：长度为 10 的字符串重新排列后包含子字符串 "leet" 的方案数为 526083947580 。所以答案为 526083947580 % (109 + 7) = 83943898 。

```

提示：

• 1 <= n <= 10^5

1368. 使网格图至少有一条有效路径的最小代价

给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：

• 1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]

• 2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]

• 3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]

• 4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]

注意网格图中可能会有 无效数字 ，因为它们可能指向 grid 以外的区域。

一开始，你会从最左上角的格子 (0,0) 出发。我们定义一条 有效路径 为从格子 (0,0) 出发，每一步都顺着数字对应方向走，最终在最右下角的格子 (m - 1, n - 1) 结束的路径。有效路径 不需要是最短路径 。

你可以花费 cost = 1 的代价修改一个格子中的数字，但每个格子中的数字 只能修改一次 。

请你返回让网格图至少有一条有效路径的最小代价。

示例 1：

```txt

输入：grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]

输出：3

解释：你将从点 (0, 0) 出发。

到达 (3, 3) 的路径为： (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) 花费代价 cost = 1 使方向向下 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) 花费代价 cost = 1 使方向向下 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) 花费代价 cost = 1 使方向向下 --> (3, 3)

总花费为 cost = 3.

```

示例 2：

```txt

输入：grid = [[1,1,3],[3,2,2],[1,1,4]]

输出：0

解释：不修改任何数字你就可以从 (0, 0) 到达 (2, 2) 。

```

示例 3：

```txt

输入：grid = [[1,2],[4,3]]

输出：1

```

示例 4：

```txt

输入：grid = [[2,2,2],[2,2,2]]

输出：3

```

示例 5：

```txt

输入：grid = [[4]]

输出：0

```

提示：

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 100

2290. 到达角落需要移除障碍物的最小数目

给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n 。每个单元格都是两个值之一：

• 0 表示一个 空 单元格，

• 1 表示一个可以移除的 障碍物 。

你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。

现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) ，返回需要移除的障碍物的 最小 数目。

示例 1：

```txt

输入：grid = [[0,1,1],[1,1,0],[1,1,0]]

输出：2

解释：可以移除位于 (0, 1) 和 (0, 2) 的障碍物来创建从 (0, 0) 到 (2, 2) 的路径。

可以证明我们至少需要移除两个障碍物，所以返回 2 。

注意，可能存在其他方式来移除 2 个障碍物，创建出可行的路径。

```

示例 2：

```txt

输入：grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]

输出：0

解释：不移除任何障碍物就能从 (0, 0) 到 (2, 4) ，所以返回 0 。

```

提示：

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 10^5

• 2 <= m * n <= 10^5

• grid[i][j] 为 0 或 1

• grid[0][0] == grid[m - 1][n - 1] == 0