力扣第312场周赛题解：

Loading Question... - 力扣（LeetCode）LeetCode 2420. 找到所有好下标 ：题目链接：Loading Question... - 力扣（LeetCode）

我们可以发现对于任何数a, b. a & b <= max(a, b)所以我们只需要找出一个数组中的最大值，然后判断该最大值连续出现的最多的次数即可：

代码如下：

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int val = 0, res = 0, j = 0;
        for (auto num : nums) val = max(val, num);
        for (auto num : nums)
            if (num == val)
            {
                j ++ ;
                res = max(j, res);
            }
            else j = 0;

            return res; 
    }
};

LeetCode 2420. 找到所有好下标：

题目链接：

Loading Question... - 力扣（LeetCode） 

我们定义两个数组f[N], g[N]:

f[i]表示以i为终点的最大的连续非递增子序列的数目。

g[i]表示以i为终点的最大的连续非递减子序列数目。

如图情况为：

因此要判断第i个点是否满足条件，即g[i + 1] >= k && f[i - 1] >= k

代码如下：

 

class Solution {
public:

    vector<int> goodIndices(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> f(n);
        vector<int> g(n);
        for (int i = 0; i < n; i ++ )
        {
            f[i] = 1;
            if (i && nums[i - 1] >= nums[i]) f[i] = f[i - 1] + 1;
        }

        for (int i = n - 1; i >= 0; i -- )
        {
            g[i] = 1;
            if (i + 1 < n && nums[i + 1] >= nums[i]) g[i] = g[i + 1] + 1;
        }

        vector<int> ans;
        for (int i = k; i < n - k; i ++ )
            if (f[i - 1] >= k && g[i + 1] >= k) ans.push_back(i);
        
        return ans;
    }
};

 

LeetCode 2421. 好路径的数目：题目链接：

Loading Question... - 力扣（LeetCode）

解题思路：
枚举每个以x为起点和终点的路径，将权值小于等于x的路径加入集合（可以用并查集），因为集合中任意两点都可成为一条路径，假设集合中有k个点，则方案数为从k个点里面任意选择两个点，即组合数

加2是因为每个点自己也算一条路径 

代码如下：

class Solution {
public:
    vector<int> p;
    int find(int x)//并查集模板
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
        int res = 0;
        int n = vals.size();
        p.resize(n);
        vector<int> q(n);
        vector<vector<int>> g(n);
        for (auto &e : edges)//建图
        {
            int a = e[0], b = e[1];
            g[a].push_back(b);
            g[b].push_back(a);

        }

        for (int i = 0; i < n; i ++ ) p[i] = q[i] = i;

        sort(q.begin(), q.end(), [&](int a, int b){//将点按权值从小到大排序
            return vals[a] < vals[b];
        });

        for (int i = 0; i < n; i ++ )
        {
            int j = i + 1;
            while (j < n && vals[q[i]] == vals[q[j]]) j ++ ;//找到权值相等的区间

            for (int k = i; k < j; k ++ )
            {
                int x = q[k];
                for (auto y : g[x]) 
                    if (vals[x] >= vals[y])//判断x权值是否大于y的权值
                        p[find(x)] = find(y);//若大于将x加入y集合中
            }

            unordered_map<int, int> hash;
                for (int k = i; k < j; k ++ )
                    hash[find(q[k])] ++ ;//q[k]这个点所在的集合要加上q[k]这个点
                for (auto &[u, v] : hash)//将q[k]即正在枚举的点所在的集合中任意选择两个点组成一条路径
                    res += v * (v + 1) / 2;//组合数公式
            i = j - 1;
        }

        return res;
    }
};