fork()==0世界线变动

6392. 使数组所有元素变成 1 的最少操作次数

给你一个下标从 0 开始的 正 整数数组 nums 。你可以对数组执行以下操作 任意 次：

• 选择一个满足 0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。

请你返回使数组 nums 中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。

两个正整数的最大公约数指的是能整除这两个数的最大正整数。

示例 1：

```txt

输入：nums = [2,6,3,4]

输出：4

解释：我们可以执行以下操作：

• 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。

• 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。

• 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。

• 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。

```

示例 2：

```txt

输入：nums = [2,10,6,14]

输出：-1

解释：无法将所有元素都变成 1 。

```

提示：

• 2 <= nums.length <= 50

• 1 <= nums[i] <= 10^6

6423. 英雄的力量

给你一个下标从 0 开始的整数数组 nums ，它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的 力量 定义为：

• i0 ，i1 ，... ik 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i0],nums[i1] ... nums[ik])^2 * min(nums[i0],nums[i1] ... nums[ik]) 。

请你返回所有可能的 非空 英雄组的 力量 之和。由于答案可能非常大，请你将结果对 10^9 + 7 取余。

示例 1：

```txt

输入：nums = [2,1,4]

输出：141

解释：

第 1 组：[2] 的力量为 22 * 2 = 8 。

第 2 组：[1] 的力量为 12 * 1 = 1 。

第 3 组：[4] 的力量为 42 * 4 = 64 。

第 4 组：[2,1] 的力量为 22 * 1 = 4 。

第 5 组：[2,4] 的力量为 42 * 2 = 32 。

第 6 组：[1,4] 的力量为 42 * 1 = 16 。

第​ ​​​​​​7 组：[2,1,4] 的力量为 42​​​​​​​ * 1 = 16 。

所有英雄组的力量之和为 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141 。

```

示例 2：

```txt

输入：nums = [1,1,1]

输出：7

解释：总共有 7 个英雄组，每一组的力量都是 1 。所以所有英雄组的力量之和为 7 。

```

提示：

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

• 1 <= nums[i] <= 10^9

982. 按位与为零的三元组

给你一个整数数组 nums ，返回其中 按位与三元组 的数目。

按位与三元组 是由下标 (i, j, k) 组成的三元组，并满足下述全部条件：

• 0 <= i < nums.length

• 0 <= j < nums.length

• 0 <= k < nums.length

• nums[i] & nums[j] & nums[k] == 0 ，其中 & 表示按位与运算符。

示例 1：

```txt

输入：nums = [2,1,3]

输出：12

解释：可以选出如下 i, j, k 三元组：

(i=0, j=0, k=1) : 2 & 2 & 1

(i=0, j=1, k=0) : 2 & 1 & 2

(i=0, j=1, k=1) : 2 & 1 & 1

(i=0, j=1, k=2) : 2 & 1 & 3

(i=0, j=2, k=1) : 2 & 3 & 1

(i=1, j=0, k=0) : 1 & 2 & 2

(i=1, j=0, k=1) : 1 & 2 & 1

(i=1, j=0, k=2) : 1 & 2 & 3

(i=1, j=1, k=0) : 1 & 1 & 2

(i=1, j=2, k=0) : 1 & 3 & 2

(i=2, j=0, k=1) : 3 & 2 & 1

(i=2, j=1, k=0) : 3 & 1 & 2

```

示例 2：

```txt

输入：nums = [0,0,0]

输出：27

```

提示：

• 1 <= nums.length <= 1000

• 0 <= nums[i] < 2^16

2488. 统计中位数为 K 的子数组

给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的 不同 整数组成。另给你一个正整数 k 。

统计并返回 nums 中的 中位数 等于 k 的非空子数组的数目。

注意：

• 数组的中位数是按 递增 顺序排列后位于 中间 的那个元素，如果数组长度为偶数，则中位数是位于中间靠 左 的那个元素。

  • 例如，[2,3,1,4] 的中位数是 2 ，[8,4,3,5,1] 的中位数是 4 。

• 子数组是数组中的一个连续部分。

示例 1：

```txt

输入：nums = [3,2,1,4,5], k = 4

输出：3

解释：中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。

```

示例 2：

```txt

输入：nums = [2,3,1], k = 3

输出：1

解释：[3] 是唯一一个中位数等于 3 的子数组。

```

提示：

• n == nums.length

• 1 <= n <= 10^5

• 1 <= nums[i], k <= n

• nums 中的整数互不相同

1960. 两个回文子字符串长度的最大乘积

给你一个下标从 0 开始的字符串 s ，你需要找到两个 不重叠的回文 子字符串，它们的长度都必须为 奇数 ，使得它们长度的乘积最大。

更正式地，你想要选择四个整数 i ，j ，k ，l ，使得 0 <= i <= j < k <= l < s.length ，且子字符串 s[i...j] 和 s[k...l] 都是回文串且长度为奇数。s[i...j] 表示下标从 i 到 j 且 包含 两端下标的子字符串。

请你返回两个不重叠回文子字符串长度的 最大 乘积。

回文字符串 指的是一个从前往后读和从后往前读一模一样的字符串。子字符串 指的是一个字符串中一段连续字符。

示例 1：

```txt

输入：s = "ababbb"

输出：9

解释：子字符串 "aba" 和 "bbb" 为奇数长度的回文串。乘积为 3 * 3 = 9 。

```

示例 2：

```txt

输入：s = "zaaaxbbby"

输出：9

解释：子字符串 "aaa" 和 "bbb" 为奇数长度的回文串。乘积为 3 * 3 = 9 。

```

提示：

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

• s 只包含小写英文字母。

1825. 求出 MK 平均值

给你两个整数 m 和 k ，以及数据流形式的若干整数。你需要实现一个数据结构，计算这个数据流的 MK 平均值 。

MK 平均值 按照如下步骤计算：

1. 如果数据流中的整数少于 m 个，MK 平均值 为 -1 ，否则将数据流中最后 m 个元素拷贝到一个独立的容器中。

2. 从这个容器中删除最小的 k 个数和最大的 k 个数。

3. 计算剩余元素的平均值，并 向下取整到最近的整数 。

请你实现 MKAverage 类：

• MKAverage(int m, int k) 用一个空的数据流和两个整数 m 和 k 初始化 MKAverage 对象。

• void addElement(int num) 往数据流中插入一个新的元素 num 。

• int calculateMKAverage() 对当前的数据流计算并返回 MK 平均数 ，结果需 向下取整到最近的整数 。

示例 1：

```txt

输入：

["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"]

[[3, 1], [3], [1], [], [10], [], [5], [5], [5], []]

输出：

[null, null, null, -1, null, 3, null, null, null, 5]

解释：

MKAverage obj = new MKAverage(3, 1);

obj.addElement(3); // 当前元素为 [3]

obj.addElement(1); // 当前元素为 [3,1]

obj.calculateMKAverage(); // 返回 -1 ，因为 m = 3 ，但数据流中只有 2 个元素

obj.addElement(10); // 当前元素为 [3,1,10]

obj.calculateMKAverage(); // 最后 3 个元素为 [3,1,10]

                      // 删除最小以及最大的 1 个元素后，容器为 [3]                      // [3] 的平均值等于 3/1 = 3 ，故返回 3

obj.addElement(5); // 当前元素为 [3,1,10,5]

obj.addElement(5); // 当前元素为 [3,1,10,5,5]

obj.addElement(5); // 当前元素为 [3,1,10,5,5,5]

obj.calculateMKAverage(); // 最后 3 个元素为 [5,5,5]

                      // 删除最小以及最大的 1 个元素后，容器为 [5]                      // [5] 的平均值等于 5/1 = 5 ，故返回 5

```

提示：

• 3 <= m <= 10^5

• 1 <= k*2 < m

• 1 <= num <= 10^5

• addElement 与 calculateMKAverage 总操作次数不超过 10^5 次。

1172. 餐盘栈

我们把无限数量 ∞ 的栈排成一行，按从左到右的次序从 0 开始编号。每个栈的的最大容量 capacity 都相同。

实现一个叫「餐盘」的类 DinnerPlates：

• DinnerPlates(int capacity) - 给出栈的最大容量 capacity。

• void push(int val) - 将给出的正整数 val 推入 从左往右第一个 没有满的栈。

• int pop() - 返回 从右往左第一个 非空栈顶部的值，并将其从栈中删除；如果所有的栈都是空的，请返回 -1。

• int popAtStack(int index) - 返回编号 index 的栈顶部的值，并将其从栈中删除；如果编号 index 的栈是空的，请返回 -1。

示例：

```txt

输入：

["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]

[[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]

输出：

[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

解释：

DinnerPlates D = DinnerPlates(2); // 初始化，栈最大容量 capacity = 2

D.push(1);

D.push(2);

D.push(3);

D.push(4);

D.push(5); // 栈的现状为： 2  4

1  3  5

                                ﹈ ﹈ ﹈

D.popAtStack(0); // 返回 2。栈的现状为：  4

                                      1  3  5                                      ﹈ ﹈ ﹈

D.push(20); // 栈的现状为： 20 4

1  3  5

                               ﹈ ﹈ ﹈

D.push(21); // 栈的现状为： 20 4 21

1  3  5

                               ﹈ ﹈ ﹈

D.popAtStack(0); // 返回 20。栈的现状为： 4 21

                                        1  3  5                                        ﹈ ﹈ ﹈

D.popAtStack(2); // 返回 21。栈的现状为： 4

                                        1  3  5                                        ﹈ ﹈ ﹈

D.pop() // 返回 5。栈的现状为： 4

                                        1  3                                        ﹈ ﹈

D.pop() // 返回 4。栈的现状为： 1 3

                                       ﹈ ﹈

D.pop() // 返回 3。栈的现状为： 1

                                       ﹈

D.pop() // 返回 1。现在没有栈。

D.pop() // 返回 -1。仍然没有栈。

```

提示：

• 1 <= capacity <= 20000

• 1 <= val <= 20000

• 0 <= index <= 100000

• 最多会对 push，pop，和 popAtStack 进行 200000 次调用。