Leetcode第312场周赛题解（未完结）

好久没回来写题解了，算了先说说最近的动态，反正这篇题解发出来除了我自己估计也没人看。最近把数学建模搞完了，数学竞赛估计是没希望了，所以之后就专注于算法和课业了。

暂定的计划是每天固定三小时算法，及时总结和反思。

扯远了，说题。

首先第一题pair排序，pair语法

第二题，按位与计算规则

第三题，前后缀分解

第四题，不会

第一题，6188. 按身高排序

 简单点说就是给身高的数组排序，其中题目有说明身高不会相同，但名字有重复。所以直接给身高排序，输出姓名即可。

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

这里运用了pair的排序，将身高与姓名组合，并且运用了pair排序的特点。排序的特点为从大到小，这里注意加了个负号。

第二题：6189. 按位与最大的最长子数组

 这里注意按位与计算是越算越小的，题目这里要求得到最大的非空子数组，即搜索数组中的最大数字，并统计出最大值连续出现的次数，即为答案。

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int val = 0;
        for(int x : nums) val = max(val, x);

        int ans = 0, cnt = 0;
        //统计最大值最多连续出现过几次
        for(int x : nums){
            if(x == val) cnt ++ ;
            else ans = max(ans, cnt), cnt = 0;
        }
        ans = max(ans, cnt);
        return ans;
    }
};

第三题：6190. 找到所有好下标

 “好”下标的条件，就是下标i前非递增，那就是下标i前的数递减，后面的非递减，就是递增。那么我们就可以以下标i为边界，将整个数组分成两端，也就是前后缀分解，可以参考一下思路，如图

 仔细说一下上图的思路，首先设立两个数组,f[n],g[n]，两个数组都有两个处理思路，先对f[n]数组进行说明，如果ai前一个元素大于ai，那么不满足题目要求，那么长度就只有1；如果ai前一个元素小于ai，那么长度就如图所示。类似的，g数组也相同。

其实这里就是用f，g两个数组来表示长度，然后遍历下表，搜索符合条件的好下标。

贴代码

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

这里划分的思路其实挺不错的。

第四题：6191. 好路径的数目

这题有点难，大体讲一下思路，之后看看有没时间再细讲，首先先将树上的权值进行排序，算了讲不了，这里的大体思路可以说一下，重点就在于并查集，构图，这里的知识点不熟悉，先跳过。