• Day6力扣打卡


    打卡记录

    在这里插入图片描述


    统计无向图中无法互相到达点对数(并查集 / DFS)

    链接

    并查集

    思路:用并查集将连通区域的连在一起,再遍历所有点,用hash表存储不同连通块的元素个数,然后 乘积和 便是答案。

    注意:

    // 计算乘积和(妙)
    long long ans = 0, total = 0;
    for (auto [_, x] : hash) {
    	ans += x * total;
    	total += x;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    class Solution {
    public:
        long long countPairs(int n, vector<vector<int>>& edges) {
            vector<int> p(n);
            for (int i = 0; i < n; ++i) p[i] = i;
            function<int(int)> find = [&](int u) -> int {
                if (p[u] != u) p[u] = find(p[u]);
                return p[u];
            };
            for (auto& edge : edges) {
                int x = find(edge[0]), y = find(edge[1]);
                if (x != y) p[x] = y;
            }
            unordered_map<int, int> hash;
            for (int i = 0; i < n; ++i) {
                hash[find(i)]++;
            }
            long long ans = 0, total = 0;
            for (auto [_, x] : hash) {
                ans += x * total;
                total += x;
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    DFS

    思路:搜寻每个连通块的元素个数,之后同理便可以计算出答案。

    class Solution {
    public:
        long long countPairs(int n, vector<vector<int>>& edges) {
            vector<int> g[n];
            for (auto& edge : edges) {
                int a = edge[0], b = edge[1];
                g[a].push_back(b);
                g[b].push_back(a);
            }
            vector<bool> st(n, false);
            function<int(int)> dfs = [&](int u) -> int {
                if (st[u]) return 0;
                int cnt = 1;
                st[u] = true;
                for (auto& e : g[u]) cnt += dfs(e);
                return cnt;
            };
            long long ans = 0, sum = 0;
            for (int i = 0; i < n; ++i) {
                int cnt = dfs(i);
                ans += sum * cnt;
                sum += cnt;
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    反转二叉树的奇数层(BFS[层序遍历] / DFS)

    链接

    BFS(层序遍历)

    思路:在层序遍历使用 queue 的基础上,将奇数层的整层的节点按照从左到右的顺序全部存入新开的一个数组中,然后对数组中的所有值进行颠倒。

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        TreeNode* reverseOddLevels(TreeNode* root) {
            queue<TreeNode*> q;
            q.push(root);
            bool flag = false;
            while (!q.empty()) {
                vector<TreeNode*> t;
                while (!q.empty()) {
                    t.push_back(q.front());
                    q.pop();
                }
                if (flag) {
                    for (int i = 0, j = t.size() - 1; i < j; ++i, --j)
                        swap(t[i]->val, t[j]->val);
                }
                flag = !flag;
                for (auto u : t) {
                    if (u->left) q.push(u->left);
                    if (u->right) q.push(u->right);
                }
            }
            return root;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
  • 相关阅读:
    大白话云IDE产品初体验测评(运行一个.py python文件)
    使用Spring Boot向邮箱发送邮件
    STM32单片机三线制PT100温度采集控制系统LCD12864显示器
    ARM裸机
    mysql之备份和恢复
    中国社科院大学-美国杜兰大学金融管理硕士暨能源管理硕士项目2023年毕业典礼
    背靠背 HVDC-MMC模块化多电平转换器输电系统-用于无源网络系统的电能质量调节(Simulink仿真实现)
    Java代码沙箱
    密码学基础知识
    shell
  • 原文地址:https://blog.csdn.net/qq947467490/article/details/133967465