这次的题还是挺简单的，还是做出来3道题，最后一道题审题失误，先写了一份回头就来不及了，思路还是有的，排名2017 / 4292，提交错误被罚时，导致排名比上周下降了

5938. 找出数组排序后的目标下标 [EASY]

给你一个下标从 0 开始的整数数组 nums 以及一个目标元素 target 。

目标下标 是一个满足 nums[i] == target 的下标 i 。

将 nums 按 非递减 顺序排序后，返回由 nums 中目标下标组成的列表。如果不存在目标下标，返回一个 空 列表。返回的列表必须按 递增 顺序排列。

示例 1：
输入：nums = [1,2,5,2,3], target = 2
输出：[1,2]
解释：排序后，nums 变为 [1,2,2,3,5] 。
满足 nums[i] == 2 的下标是 1 和 2 。

示例 2：
输入：nums = [1,2,5,2,3], target = 3
输出：[3]
解释：排序后，nums 变为 [1,2,2,3,5] 。
满足 nums[i] == 3 的下标是 3 。

示例 3：
输入：nums = [1,2,5,2,3], target = 5
输出：[4]
解释：排序后，nums 变为 [1,2,2,3,5] 。
满足 nums[i] == 5 的下标是 4 。

示例 4：
输入：nums = [1,2,5,2,3], target = 4
输出：[]
解释：nums 中不含值为 4 的元素。

提示：
1 <= nums.length <= 100
1 <= nums[i], target <= 100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/* 
审题：
这题不难，先排序，然后二分法查找即可
*/
class Solution {
public:
    vector<int> targetIndices(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<int> result;
        auto index = std::lower_bound(nums.begin(), nums.end(), target);
        auto distance = index - nums.begin();
        if (distance >= nums.size()) {
            return result;
        }
        if (nums[distance] == target) {
            for (int i = distance; i < nums.size(); ++i) {
                if (nums[i] == target) {
                    result.emplace_back(i);   
                } else {
                    break;
                }
            }
        }
        return result;
    }
};

5939. 半径为 k 的子数组平均值 [MEDIUM]

给你一个下标从 0 开始的数组 nums ，数组中有 n 个整数，另给你一个整数 k 。

半径为 k 的子数组平均值 是指：nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值，即下标在 i - k 和 i + k 范围（含 i - k 和 i + k）内所有元素的平均值。如果在下标 i 前或后不足 k 个元素，那么 半径为 k 的子数组平均值 是 -1 。

构建并返回一个长度为 n 的数组 avgs ，其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。

x 个元素的 平均值 是 x 个元素相加之和除以 x ，此时使用截断式 整数除法 ，即需要去掉结果的小数部分。

例如，四个元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 3.75，截断后得到 3 。

示例 1：

输入：nums = [7,4,3,9,1,8,5,2,6], k = 3
输出：[-1,-1,-1,5,4,4,-1,-1,-1]
解释：

• avg[0]、avg[1] 和 avg[2] 是 -1 ，因为在这几个下标前的元素数量都不足 k 个。
• 中心为下标 3 且半径为 3 的子数组的元素总和是：7 + 4 + 3 + 9 + 1 + 8 + 5 = 37 。
  使用截断式 整数除法，avg[3] = 37 / 7 = 5 。
• 中心为下标 4 的子数组，avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4 。
• 中心为下标 5 的子数组，avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4 。
• avg[6]、avg[7] 和 avg[8] 是 -1 ，因为在这几个下标后的元素数量都不足 k 个。
• 示例 2：
  输入：nums = [100000], k = 0
  输出：[100000]
  解释：
• 中心为下标 0 且半径 0 的子数组的元素总和是：100000 。
  avg[0] = 100000 / 1 = 100000 。

示例 3：
输入：nums = [8], k = 100000
输出：[-1]
解释：

• avg[0] 是 -1 ，因为在下标 0 前后的元素数量均不足 k 。

提示：
n == nums.length
1 <= n <= 105
0 <= nums[i], k <= 105

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/*
审题：虽然是一道中等题，但比较简单，找到合理的区间，滑动过程中删左加右即可，注意求和用int会溢出
*/
#include <numeric>
class Solution {
public:
    vector<int> getAverages(vector<int>& nums, int k) {
        vector<int> result(nums.size(), -1);
        if (2 * k + 1 > nums.size()) {
            return result;
        }
        int centre = k;
        long long curSum = 0;
        for (int i = 0; i <= 2 * k; ++i) {
            curSum += nums[i];
        }
        result[centre] = floor(curSum / (2 * k + 1));
        
        while (++centre < nums.size()) {
            // cout << centre << ", " << curSum << endl;
            if (centre > k && centre < nums.size() - k) {
                curSum -= nums[centre - k - 1];
                curSum += nums[centre + k];
                result[centre] = floor(curSum / (2 * k + 1));
            }
        }
        return result;
    }
};

5940. 从数组中移除最大值和最小值 [MEDIUM]

给你一个下标从 0 开始的数组 nums ，数组由若干 互不相同 的整数组成。

nums 中有一个值最小的元素和一个值最大的元素。分别称为 最小值 和 最大值 。你的目标是从数组中移除这两个元素。

一次 删除 操作定义为从数组的 前面 移除一个元素或从数组的 后面 移除一个元素。

返回将数组中最小值和最大值 都 移除需要的最小删除次数。

示例 1：
输入：nums = [2,10,7,5,4,1,8,6]
输出：5
解释：
数组中的最小元素是 nums[5] ，值为 1 。
数组中的最大元素是 nums[1] ，值为 10 。
将最大值和最小值都移除需要从数组前面移除 2 个元素，从数组后面移除 3 个元素。
结果是 2 + 3 = 5 ，这是所有可能情况中的最小删除次数。

示例 2：
输入：nums = [0,-4,19,1,8,-2,-3,5]
输出：3
解释：
数组中的最小元素是 nums[1] ，值为 -4 。
数组中的最大元素是 nums[2] ，值为 19 。
将最大值和最小值都移除需要从数组前面移除 3 个元素。
结果是 3 ，这是所有可能情况中的最小删除次数。

示例 3：
输入：nums = [101]
输出：1
解释：
数组中只有这一个元素，那么它既是数组中的最小值又是数组中的最大值。
移除它只需要 1 次删除操作。

提示：
1 <= nums.length <= 105
-105 <= nums[i] <= 105
nums 中的整数 互不相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

审题：这题有点简单，一共就四种删除的方式，删左删左，删左删右，删右删左，删右删右，四种情况都比较取最小就行了，然后删左删右和删右删左是同一种

class Solution {
public:
    int minimumDeletions(vector<int>& nums) {
        int numsLen = nums.size();
        if (numsLen == 1) {
            return 1;
        }
        if (numsLen == 2) {
            return 2;
        }
        int minIndex = -1;
        int maxIndex = -1;
        int minValue = INT_MAX;
        int maxValue = -INT_MAX;
        for (int i = 0; i < numsLen; ++i) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
                maxIndex = i;
            }
            if (nums[i] < minValue) {
                minValue = nums[i];
                minIndex = i;
            }
        }
        
        int left = min(minIndex, maxIndex);
        int right = max(minIndex, maxIndex);
        
        int minOps = INT_MAX; 
        
        int Ops;
        {
            // left, left
            Ops = right + 1;
            if (Ops < minOps) {
                minOps = Ops;
            }
            // left, right
            Ops = (left + 1) + (numsLen - right);
            if (Ops < minOps) {
                minOps = Ops;
            }
            // right, right
            Ops = numsLen - left;
            if (Ops < minOps) {
                minOps = Ops;
            }
            // right, left
            Ops = (numsLen - right) + (left + 1);
            if (Ops < minOps) {
                minOps = Ops;
            }
        }
        return minOps;
    }
};

5941. 找出知晓秘密的所有专家 [HARD]

给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号。另外给你一个下标从 0 开始的二维整数数组 meetings ，其中 meetings[i] = [xi, yi, timei] 表示专家 xi 和专家 yi 在时间 timei 要开一场会。一个专家可以同时参加 多场会议 。最后，给你一个整数 firstPerson 。

专家 0 有一个 秘密 ，最初，他在时间 0 将这个秘密分享给了专家 firstPerson 。接着，这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播。更正式的表达是，每次会议，如果专家 xi 在时间 timei 时知晓这个秘密，那么他将会与专家 yi 分享这个秘密，反之亦然。

秘密共享是 瞬时发生 的。也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享。

在所有会议都结束之后，返回所有知晓这个秘密的专家列表。你可以按 任何顺序 返回答案。

示例 1：
输入：n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
输出：[0,1,2,3,5]
解释：
时间 0 ，专家 0 将秘密与专家 1 共享。
时间 5 ，专家 1 将秘密与专家 2 共享。
时间 8 ，专家 2 将秘密与专家 3 共享。
时间 10 ，专家 1 将秘密与专家 5 共享。
因此，在所有会议结束后，专家 0、1、2、3 和 5 都将知晓这个秘密。

示例 2：
输入：n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
输出：[0,1,3]
解释：
时间 0 ，专家 0 将秘密与专家 3 共享。
时间 2 ，专家 1 与专家 2 都不知晓这个秘密。
时间 3 ，专家 3 将秘密与专家 0 和专家 1 共享。
因此，在所有会议结束后，专家 0、1 和 3 都将知晓这个秘密。

示例 3：
输入：n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
输出：[0,1,2,3,4]
解释：
时间 0 ，专家 0 将秘密与专家 1 共享。
时间 1 ，专家 1 将秘密与专家 2 共享，专家 2 将秘密与专家 3 共享。
注意，专家 2 可以在收到秘密的同一时间分享此秘密。
时间 2 ，专家 3 将秘密与专家 4 共享。
因此，在所有会议结束后，专家 0、1、2、3 和 4 都将知晓这个秘密。

示例 4：
输入：n = 6, meetings = [[0,2,1],[1,3,1],[4,5,1]], firstPerson = 1
输出：[0,1,2,3]
解释：
时间 0 ，专家 0 将秘密与专家 1 共享。
时间 1 ，专家 0 将秘密与专家 2 共享，专家 1 将秘密与专家 3 共享。
因此，在所有会议结束后，专家 0、1、2 和 3 都将知晓这个秘密。

提示：
2 <= n <= 105
1 <= meetings.length <= 105
meetings[i].length == 3
0 <= xi, yi <= n - 1
xi != yi
1 <= timei <= 105
1 <= firstPerson <= n - 1

1
2
3
4
5

审题：这题上来忘记`在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享`这个条件，就只记录已知的人，然后根据会议时间进行传染；其实应该按时间找同一时间内各已知人的连通图，然后标记已知的人，最后输出知道的人

BFS或者并查集甚至同一时间将知道的人排序在前也可以

[官方解答](https://leetcode-cn.com/problems/find-all-people-with-secret/solution/zhao-chu-zhi-xiao-mi-mi-de-suo-you-zhuan-fzxf/)