第 312 场周赛

Date: 2022-09-25

A 按身高排序

纯模拟排序

C++Python

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

# 首先通过 dict(zip(..,..)) 把 heights 和 names 绑定在一起，然后使用列表推导式转为 list
# 通过对 list 排序，获取到 names 的正确顺序
# 最后再通过列表推导式，得到答案
class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        d = [(h, n) for h, n in dict(zip(heights, names)).items()]
        d.sort(key=lambda x: -x[0])
        return [v[1] for v in d]

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

设 \(x \& y = z\)，那么 \(z\) 不会大于 \(\max(x, y)\)，也就是说按位与不会使得数字变得更大。所以题目汇总所说的子数组按位与结果的最大值就是数组中的最大值。

所以，题目是在求最长的最大值连续长度。

C++Python

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int mx = *max_element(nums.begin(), nums.end());
        int cur = 0, res = 0;
        for (auto &x : nums) {
            if (x == mx) cur++;
            else cur = 0;
            res = max(res, cur);
        }
        return res;
    }
};

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        mx = max(nums)
        cur, res = 0, 0
        for x in nums:
            if x == mx:
                cur += 1
            else:
                cur = 0
            res = max(res, cur)
        return res

C 找到所有好下标

前后设置两个数组，\(d[i]\) 表示以 \(i\) 结尾，最多有多少个非递增元素。

如果 \(i=0\) 或者 \(nums[i] > nums[i-1]\)，\(d[i]=1\)
否则 \(d[i]=d[i-1]+1\)

然后设 \(f[i]\) 表示倒序来看，以 \(i\) 为结尾，有多少个非递增元素。（从后往前看是非递增等同于从前往后看非递减）

然后遍历 \([k,n-k)\) 有多少个 \(i\) 满足 \(d[i-1] \ge k\) 并且 \(f[i+1] \ge k\) 即可。

时间复杂度为 \(O(n)\)，空间复杂度为 \(O(n)\)。

C++Python

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

class Solution:
    def goodIndices(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        d = [0] * n
        f = [0] * n
        for i in range(n):
            if i == 0 or nums[i] > nums[i - 1]:
                d[i] = 1
            else:
                d[i] = d[i - 1] + 1
        for i in range(n - 1, -1, -1):
            if i == n - 1 or nums[i] > nums[i + 1]:
                f[i] = 1
            else:
                f[i] = f[i + 1] + 1
        res = []
        for i in range(k, n - k):
            if d[i - 1] >= k and f[i + 1] >= k:
                res.append(i)
        return res

D 好路径的数目

首先把图清空，按照点权从小到大去考虑往图中新加点。每一批次把点权相同的点（记为 \(v\))一起加入图中。使用并查集维护每个点所属的集合，遍历 \(v\) 中所有点所属的集合，在同一集合中的点对都可以构成好路径。

时间复杂度 \(O(n\log n)\)，空间复杂度 \(O(n)\)。

C++

struct DSU {
    vector<int> f;
    vector<int> cnt;
    int n;
    DSU(int n) : n(n), f(n), cnt(n, 1) { iota(f.begin(), f.end(), 0); }
    bool merge(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        f[x] = y;
        cnt[y] += cnt[x];
        return true;
    }
    int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
    bool same(int x, int y) { return find(x) == find(y); }
    int getCnt(int x) { return cnt[find(x)]; }
};

class Solution {
public:
    int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
        int n = vals.size();
        vector<vector<int>> g(n);
        DSU dsu(n);
        map<int, vector<int>> mp;
        for (int i = 0; i < n; i++) {
            mp[vals[i]].push_back(i);
        }
        for (auto &v : edges) {
            g[v[0]].push_back(v[1]);
            g[v[1]].push_back(v[0]);
        }
        int res = 0;
        for (auto &[k, v] : mp) {
            for (auto &x : v) {
                for (auto &y : g[x]) {
                    if (vals[y] <= vals[x]) {
                        dsu.merge(x, y);
                    }
                }
            }
            map<int, int> count;
            for (auto &x : v) {
                count[dsu.find(x)]++;
            }
            for (auto &[kk, vv] : count) {
                res += vv * (vv - 1) / 2;
            }
        }
        return res + n;
    }
};

本文访问次