【周赛复盘】力扣第 312 场单周赛

1.按身高排序

1)题目描述

给你一个字符串数组 names ，和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。

对于每个下标 i，names[i] 和 heights[i] 表示第 i 个人的名字和身高。

请按身高 降序 顺序返回对应的名字数组 names 。

2）原题链接

LeetCode.6188. 按身高排序

3）思路解析

$(1)$考虑将名字和身高放一起，进行二维排序，按身高来排。

4）模板代码

public String[] sortPeople(String[] names, int[] heights) {
            int n=names.length;
            Node[] node=new Node[n];
        for (int i = 0; i < n; i++) {
            node[i]=new Node(names[i],heights[i]);
        }
        Arrays.sort(node, Comparator.comparing(a->a.d));
        int pre=n-1;
        for (int i = 0; i <n; i++) {
            names[i]=node[pre--].s;
        }
        return names;
    }
    class Node{
        String s;
        int d;
        public Node(String s, int d) {
            this.s = s;
            this.d = d;
        }
    }

5）算法与时间复杂度

算法：排序
时间复杂度：$O(nlogn)$

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

1.题目描述

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

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

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

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

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

2）原题链接

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

3)思路解析

$(1)$首先我们要思考：这个最大值k会是多少呢？
这得从与运算&的性质出发，我们知道：0&0=0,1&0=0,1&1=1。对于某一个二进制位，只有可能从1变为0，不可能从0变为1。这就说明对于一个数 $x$ ，如果与上区间$[1,x-1]$的数，它是不可能变大的，只可能变小，当它与上自身时值不变。
$(2)$根据上述结论，我们可知道k的值就是数组中的最大值，问题则转换为求原数组内最大值max最长连续出现的区间，我们可以使用双指针进行求解。

4）模板代码

class Solution {
 public int longestSubarray(int[] arr) {
        int mx=0;
        for (int i = 0; i < arr.length; i++) {
            mx=Math.max(arr[i],mx);
        }
        int ans=0;
        for (int i = 0; i <arr.length; i++) {
            if (arr[i]==mx){
                int s=1;
                int j;
                for (j = i+1; j <arr.length; j++) {
                    if (arr[j]==mx) s++;
                    else{
                        break;
                    }
                }
                i=j;
                ans=Math.max(s,ans);
            }
        }
        return ans;
    }
}

5）算法与时间复杂度

算法：双指针
时间复杂度：$O(n)$

3.找到所有好下标

1.题目描述

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

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

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

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

2）原题链接

LeetCode.6190. 找到所有好下标

3)思路解析

$(1)$考虑到我们需要判断的区间都是长度为k的，自然我们想到使用滑动窗口，去预处理出所有长度为k，非递增以及非递减的区间，分别使用两个set存下这些区间的起始下标。当我们判断下标 $x$ 是否是一个好下标时，则要去判断区间$[x-k,x-1]$是否非递增，如果存非递增区间的set包含 $x-k$ 这点说明符合。同时需要判断区间 $[x+1,x+k]$是否是非递减，我们去另外一个set去判断是否存在点 $x+1$ 即可，两者都存在说明 $x$ 是一个好下标。

4）模板代码

class Solution {
      public List<Integer> goodIndices(int[] a, int k) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        int n = a.length;
        int ans = 0;
        for (int i = 0, j = 0; i < n; i++) {
            if (i > 0 && a[i] <= a[i - 1]) ans++;
            if (i - j + 1 > k) {
                if (a[j] >= a[j + 1]) ans--;
                j++;
            }
            if (i - j + 1 == k && ans == k - 1) {
                set1.add(i);
            }
        }
        ans=0;
        for (int i = 0, j = 0; i < n; i++) {
            if (i > 0 && a[i] >= a[i - 1]) ans++;
            if (i - j + 1 > k) {
                if (a[j] <= a[j + 1]) ans--;
                j++;
            }
            if (i - j + 1 == k && ans == k - 1) {
                set2.add(i);
            }
        }
        List<Integer> list=new ArrayList<>();
        for (int i = k; i <=n-k-1; i++) {
            int l=i-1,r=i+k;
            if (set1.contains(l)&&set2.contains(r)) list.add(i);
        }
        return list;
    }
}

5）算法与时间复杂度

算法：滑动窗口 哈希表
时间复杂度：$O(n)$

4.好路径的数目

1.题目描述

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

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

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

1. 开始节点和结束节点的值 相同 。
2. 开始节点和结束节点中间的所有节点值都 小于等于 开始节点的值（也就是说开始节点的值应该是路径上所有节点的最大值）。
   请你返回不同好路径的数目。

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

2）原题链接

LeetCode.6190. 找到所有好下标

3)解题思路

$(1)$由于每个相同节点的值相互到达的前提是不能经过大于自己的值的节点，所以我们先假设所有的点都是独立的，从节点值小的开始合并，当两个节点的值在同一个联通块中说明存在一条好路径，因为我们是从小到达合并的，所以一定路线上一定不存在大于当前节点值的节点。我们可以使用并查集完成这个操作。
$(2)$当一个联通块出现 $x$ 个相同值的节点时，可以产生的好路径数目为 $x\ast (x-1)/2$，我们统计进答案中，最后加上节点个数为最终答案。

4）模板代码

struct UF {
    std::vector<int> f, siz;
    UF(int n) : f(n), siz(n, 1) { std::iota(f.begin(), f.end(), 0); }
    int find(int x) {
        while (x != f[x]) x = f[x] = f[f[x]];
        return x;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    int size(int x) { return siz[find(x)]; }
};
class Solution {
public:
    int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
        int n = vals.size();
        vector<vector<int>> g(n);
        UF uf(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;
        //v是集合
        for (auto [k, v] : mp) {
            //所有的x的节点值是相同的
            for (auto x : v) {
                for (auto y : g[x]) {
                    if (vals[y] <= vals[x]) {
                        uf.merge(x, y);
                    }
                }
            }
            map<int, int> count;
            for(auto x:v){
                count[uf.find(x)]++;
            }
            for(auto [kk,vv]:count){
                res+=vv*(vv-1)/2;
            }
        }
        return res+n;
    }
};

5）算法与时间复杂度

算法：并查集
时间复杂度：$O(nlogn)$