第312场周赛

NO2.按位与最大的最长子数组-题目描述：

给你一个长度为 n 的整数数组 nums 。

考虑 nums 中进行 按位与（bitwise AND）运算得到的值 最大 的 非空 子数组。

换句话说，令 k 是 nums 任意 子数组执行按位与运算所能得到的最大值。那么，只需要考虑那些执行一次按位与运算后等于 k 的子数组。

返回满足要求的 最长 子数组的长度。

数组的按位与就是对数组中的所有数字进行按位与运算。

子数组 是数组中的一个连续元素序列。

No2.按位与最大的最长子数组-题目解析：

首先通过一次遍历找到数组中的最大值，然后再通过一次遍历，如果当前值为最大值则med++，如果出现连续的最大值时，则med持续加1，在med变化的过程中，计算ans与med中的最大值最为ans值，如果当前值不为最大值时将med赋值为0，代码如下：

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int len = nums.size();
        int med(0);
        for(int i = 0 ; i<len ; i++){
            med = max(nums[i],med);
        }
        int ans = 1;
        int temp = 1;
        for(int i = 1 ; i<len ; i++){
            if(nums[i]==med){
                if(nums[i]==nums[i-1])temp++;
                ans = max(temp,ans);
            }
            else{
                temp = 1;
            }
        }
        return ans;
    }
};

执行用时：140 ms, 在所有 C++ 提交中击败了50.00%的用户

内存消耗：80.3 MB, 在所有 C++ 提交中击败了100.00%的用户

NO3.找到所有好下标-题目描述：

给你一个大小为 n 下标从 0 开始的整数数组 nums 和一个正整数 k 。

对于 k <= i < n - k 之间的一个下标 i ，如果它满足以下条件，我们就称它为一个 好 下标：

下标 i 之前 的 k 个元素是 非递增的 。

下标 i 之后 的 k 个元素是 非递减的 。

按 升序 返回所有好下标。

NO3.找到所有好下标-题目解析：

通过两个数组，一个left数组，一个right数组，left数组统计从左边开始的最长非递增数列的长度，即left[i]=k，表明第i个数及之前的k个数为非递增，而k+1个数不满足非递增，同理使用right数组统计从右边开始的最长非递减数列的长度，代码如下：

class Solution {
public:
    vector<int> goodIndices(vector<int>& nums, int k) {
        int len = nums.size();
        int left[len];
        fill(left,left+len,1);
        int right[len];
        fill(right,right+len,1);
        vector<int> ans;
        for(int i = 1 ; i<len ; i++){
            if(nums[i]<=nums[i-1])left[i] = left[i-1]+1;
            else left[i] = 1;
        }
        for(int i = len-2 ; i>=0 ; i--){
            if(nums[i]<=nums[i+1])right[i] = right[i+1]+1;
            else right[i] = 1;
        }
        for(int i = 1 ; i<len-1 ; i++){
            if(left[i-1]>=k&&right[i+1]>=k)ans.push_back(i);
        }
        return ans;
    }
};

执行用时：136 ms, 在所有 C++ 提交中击败了50.00%的用户

内存消耗：81.8 MB, 在所有 C++ 提交中击败了100.00%的用户

NO4.好路径的数目-题目描述：

给你一棵 n 个节点的树（连通无向无环的图），节点编号从 0 到 n - 1 且恰好有 n - 1 条边。

给你一个长度为 n 下标从 0 开始的整数数组 vals ，分别表示每个节点的值。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。

一条 好路径 需要满足以下条件：

开始节点和结束节点的值 相同 。

开始节点和结束节点中间的所有节点值都 小于等于 开始节点的值（也就是说开始节点的值应该是路径上所有节点的最大值）。

请你返回不同好路径的数目。

注意，一条路径和它反向的路径算作 同一 路径。比方说， 0 -> 1 与 1 -> 0 视为同一条路径。单个节点也视为一条合法路径。

NO4.好路径的数目-题目解析：

并查集！将所有结点放进矩阵中，每个结点的父结点都指向自己，然后按value值从小到大进行遍历，如果与该结点的父节点A和与该结点相连的结点的父节点B的值大于该结点或者两个结点已经在一个集合中了那么就continue，如果小于的话就将该结点B的父节点指向结点A，如果等于的话就将两个结点对于集合的size相乘加在ans上，结点A的size等于A.size+B.size，然后将结点B的父节点指向结点A。具体的证明可以看：

【力扣周赛 312】并查集_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1ve411K7P5/?spm_id_from=333.1007.top_right_bar_window_history.content.click

class Solution {
public:
    int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
        int len = vals.size();
        vector<vector<int>> gra(len);
        for(auto &e:edges){
            int x = e[0];
            int y = e[1];
            gra[x].push_back(y);
            gra[y].push_back(x);
        }

        int id[len],parent[len],size[len];
        iota(id,id+len,0);
        iota(parent,parent+len,0);
        fill(size,size+len,1);

        sort(id,id+len,[&](int i , int j){return vals[i]<vals[j];});
        int ans = len;
        for(int x:id){
            int x_val = vals[x];
            int fx = find(x,parent);
            for(int y:gra[x]){
                int fy = find(y,parent);
                if(fy==fx||vals[fy]>x_val)continue;
                if(vals[fy]==x_val){
                    ans += size[fy]*size[fx];
                    size[fx] += size[fy]; 
                }
                parent[fy] = fx;
            }
        }
        return ans;
    }

    int find(int x , int parent[]){
        while(parent[x]!=x){
            x = parent[x];
        }
        return x;
    }
};

执行用时：1628 ms, 在所有 C++ 提交中击败了50.00%的用户

内存消耗：125.2 MB, 在所有 C++ 提交中击败了100.00%的用户