[数据结构与算法]【LeetCode周赛-312】子数组按位与最大值、并查集(图)

周赛链接：
https://leetcode.cn/contest/weekly-contest-312/

A. 2418. 按身高排序

题目描述：
给你一个字符串数组 names ，和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。
对于每个下标 i，names[i] 和 heights[i] 表示第 i 个人的名字和身高。
请按身高 降序 顺序返回对应的名字数组 names 。

AC代码：

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

B. 2419. 按位与最大的最长子数组

题目描述：
给你一个长度为 n 的整数数组 nums 。
考虑 nums 中进行 按位与（bitwise AND）运算得到的值 最大 的 非空 子数组。

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

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

• 数组的按位与就是对数组中的所有数字进行按位与运算。 子数组 是数组中的一个连续元素序列。

思维题，子数组按位与的结果一定小于子数组的最大值，所以最大的与值一定是数组的最大值，然后我们检查一下这个最大值连续出现的最大长度即可。

AC代码：

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

C. 2420. 找到所有好下标

题目描述：
给你一个大小为 n 下标从 0 开始的整数数组 nums 和一个正整数 k 。
对于 k <= i < n - k 之间的一个下标 i ，如果它满足以下条件，我们就称它为一个 好 下标：

下标 i 之前 的 k 个元素是 非递增的 。
下标 i 之后 的 k 个元素是 非递减的 。
按 升序 返回所有好下标。

1. 先预处理出up、down数组。
   • up[i]:记录i右边(包括i)连续递增的数列个数。
   • down[i]:记录i左边(包括i)连续递增的数列个数。
2. 直接枚举符合 k <= i < n - k条件的i。

AC代码：

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

D. 2421. 好路径的数目

题目描述：
给你一棵 n 个节点的树（连通无向无环的图），节点编号从 0 到 n - 1 且恰好有 n - 1 条边。
给你一个长度为 n 下标从 0 开始的整数数组 vals ，分别表示每个节点的值。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。
一条 好路径 需要满足以下条件：
开始节点和结束节点的值 相同 。
开始节点和结束节点中间的所有节点值都 小于等于 开始节点的值（也就是说开始节点的值应该是路径上所有节点的最大值）。
请你返回不同好路径的数目。
注意，一条路径和它反向的路径算作 同一 路径。比方说， 0 -> 1 与 1 -> 0 视为同一条路径。单个节点也视为一条合法路径。

AC代码：

class Solution {
public:
    vector<int> fa;
    int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
        int n = vals.size();
        
        vector<vector<int>> g(n);
        
        for (auto &e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        
        vector<int> id(n), size(n, 1);
        fa.resize(n);
        
        // 并查集初始化操作
        // 单个节点也算为一条合法的路径
        for (int i = 0; i < n; i ++) id[i] = i, fa[i] = i;
        
        sort(id.begin(), id.end(), [&](int a, int b){
            return vals[a] < vals[b];
        });
        
        int ans = n;
        // 从小到大遍历
        for (auto u : id) {
            for (auto c : g[u]) {
                // 邻居节点vals大的当前不合并。
                if (vals[c] > vals[u]) continue;
                // 找到这两个集合的代表元，注意pu节点的节点值一定是vals[u]，vals[u]是当前访问过所有节点的最大val
                int fu = find(u), fc = find(c);
                //  属于同一个连通块不需要再次计算
                if (fu == fc) continue;
                // 如果值相等，就说明开始节点和结束节点的值相等，那么就可以合并。
                if (vals[fu] == vals[fc]) {
                    ans += size[fu] * size[fc]; // 乘法原理。因为pu连通块最大值节点与pc连通块最大值节点相连，路径上的节点值都小于等于最大值.
                    size[fu] += size[fc];
                }
                fa[fc] = fu;//按照节点值从小到大遍历，pu的节点值是vals[u]是当前最大的，所以pc合并到pu
            }
            
        }
        return ans;
    }
    
    int find(int x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }

};