Leetcode每日一题：1782. 统计点对的数目（2023.8.24 C++）-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode每日一题：1782. 统计点对的数目（2023.8.24 C++）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1782. 统计点对的数目

题目描述：

实现代码与解析：

hash + 双指针

原理思路：

1782. 统计点对的数目

题目描述：

给你一个无向图，无向图由整数 n ，表示图中节点的数目，和 edges 组成，其中 edges[i] = [ui, vi] 表示 ui 和 vi 之间有一条无向边。同时给你一个代表查询的整数数组 queries 。

第 j 个查询的答案是满足如下条件的点对 (a, b) 的数目：

a < b
cnt 是与 a 或者 b 相连的边的数目，且 cnt 严格大于 queries[j] 。

请你返回一个数组 answers ，其中 answers.length == queries.length 且 answers[j] 是第 j 个查询的答案。

请注意，图中可能会有 多重边 。

示例 1：

Leetcode每日一题：1782. 统计点对的数目（2023.8.24 C++）,LeetCode,leetcode,c++,算法

输入：n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3]
输出：[6,5]
解释：每个点对中，与至少一个点相连的边的数目如上图所示。
answers[0] = 6。所有的点对(a, b)中边数和都大于2，故有6个；
answers[1] = 5。所有的点对(a, b)中除了(3,4)边数等于3，其它点对边数和都大于3，故有5个。

示例 2：

输入：n = 5, edges = [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]], queries = [1,2,3,4,5]
输出：[10,10,9,8,6]

提示：

2 <= n <= 2 * 104
1 <= edges.length <= 105
1 <= ui, vi <= n
ui != vi
1 <= queries.length <= 20
0 <= queries[j] < edges.length

实现代码与解析：

hash + 双指针

class Solution {
public:
    vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
        
        vector<int> deg(n); // 每个节点的度 1 ~ n
        unordered_map<int, int> rpt; // 重复计算的边

        // 算度，hash记边
        for (int i = 0; i < edges.size(); i++)
        {
            int a = edges[i][0] - 1, b = edges[i][1] - 1;
            if (a > b) swap(a, b);
            deg[a]++;
            deg[b]++;
            rpt[a << 16 | b]++; // 相当于两个hash，ab边转换，以及对应个数 
        }

        vector<int> arr = deg;
        sort(arr.begin(), arr.end());
        vector<int> res;

        for (int i = 0; i < queries.size(); i++)
        {
            int bound = queries[i];
            int sum = 0;

            // 双指针r找的是第二个数的左边界，因为右边界已经确定是n-1，不用再找了，别搞错了
            for (int l = 0, r = n - 1; l < n; l++ ) 
            {
                while(l < r && arr[l] + arr[r] > bound) r--;
                sum += n - 1 - max(l, r);
            }

            // 去重复
            for (auto &[rp, cnt]: rpt)
            {
                int a = rp >> 16, b = rp & 0xffff;
                if (deg[a] + deg[b] > bound && deg[a] + deg[b] - cnt <= bound) sum--;
            }
            res.push_back(sum);
        }
        return res;
    }
};