力扣第 312 场周赛题解

6188. 按身高排序

根据题意直接枚举排序即可

class Solution {
public:
    
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        vector<pair<int,string>>v;
        for(int i=0;i<names.size();i++)
            v.push_back({heights[i],names[i]});
        sort(v.begin(),v.end(),greater<pair<int,string>>());
        vector<string>res;
        for(int i=0;i<v.size();i++)
            res.push_back(v[i].second);
        return res;
    }
};

6189. 按位与最大的最长子数组

最大与值等于数组的最大值，求与最大值相等的最长连续子段的长度

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

6190. 找到所有好下标

这道题难在代码实现
用两个数组分别存它前边和后边与之相连非递增非递减数的个数。
最后判断一下就好

class Solution {
public:
    vector<int> goodIndices(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int>a(n),b(n);
        a[0]=1;
        for(int i=1;i<n;i++)
        {
            if(nums[i]<=nums[i-1])a[i]=a[i-1];
            a[i]++;
        }
        b[n-1]=1;
        for(int i=n-2;i>=0;i--)
        {
            if(nums[i+1]>=nums[i])b[i]=b[i+1];
            b[i]++;
        }
        vector<int>res;
        for(int i=k;i<n-k;i++)
        {
            if(a[i-1]>=k&&b[i+1]>=k)res.push_back(i);
        }
        return res;
    }
};

6191. 好路径的数目

路径的起点与终点的权值相等，并且路径中其余各点都小于等于起点与终点的权值。

1. 对所有权值进行排序

对于相同权值的点可以作为起点与终点，如图中的x，以x为起点终点的路径上的其余节点只能是x之前的点。
2. 通过并查集将符合条件的点合并在同一个集合，用hash存每个集合中的点。
3. k个点合并路径一共有C(k,2)+k种

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 n=vals.size();
        vector<vector<int>>g(n);
        for(auto x:edges)
        {
            int a=x[0],b=x[1];
            g[a].push_back(b);
            g[b].push_back(a);
        }   
        vector<int>q(n);
        p.resize(n);
        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];
        });
        int res=0;
        for(int i=0,j=0;i<n;i++)
        {
            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])
                       p[find(x)]=find(y);
                }
            }
            unordered_map<int,int>mp;
            for(int k=i;k<j;k++)
            mp[find(q[k])]++;
            for(auto x:mp)
            res+=x.second*(x.second+1)/2;
            i=j-1;
        }
        return res;
    }
};