Day6力扣打卡
打卡记录

统计无向图中无法互相到达点对数(并查集 / DFS)
链接
并查集
思路:用并查集将连通区域的连在一起,再遍历所有点,用hash表存储不同连通块的元素个数,然后 乘积和 便是答案。
注意:
// 计算乘积和(妙)
long long ans = 0, total = 0;
for (auto [_, x] : hash) {ans += x * total;total += x;
}
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;}
};
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;}
};
反转二叉树的奇数层(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;}
};
相关文章:
Day6力扣打卡
打卡记录 统计无向图中无法互相到达点对数(并查集 / DFS) 链接 并查集 思路:用并查集将连通区域的连在一起,再遍历所有点,用hash表存储不同连通块的元素个数,然后 乘积和 便是答案。 注意: /…...
10月面试js基础
作用域 变量的可用范围 作用域链 保存的变量的使用顺序的一个链(也就是路线图), 被称为作用域链。 当在Javascript中使用一个变量的时候,首先Javascript引擎会尝试在当前作用域下去寻找该变量,如果没找到,再…...
研发日常踩坑-Mysql分页数据重复 | 京东云技术团队
踩坑描述: 写分页查询接口,order by和limit混用的时候,出现了排序的混乱情况 在进行第N页查询时,出现与第一前面页码的数据一样的记录。 问题 在MySQL中分页查询,我们经常会用limit,如:limit(0,20)表示查询第一页的…...
Ubuntu18.04安装QGC报错 `GLIBC_2.29‘ not found
按照官网教程,最后运行时出错。 /tmp/.mount_QGroun2NOhPP/QGroundControl: /lib/x86_64-linux-gnu/libm.so.6: version GLIBC_2.29 not found (required by /tmp/.mount_QGroun2NOhPP/QGroundControl) /tmp/.mount_QGroun2NOhPP/QGroundControl: /usr/lib/x86_64-…...
回归预测 | MATLAB实现BO-GRU贝叶斯优化门控循环单元多输入单输出回归预测
回归预测 | MATLAB实现BO-GRU贝叶斯优化门控循环单元多输入单输出回归预测 目录 回归预测 | MATLAB实现BO-GRU贝叶斯优化门控循环单元多输入单输出回归预测效果一览基本介绍模型搭建程序设计参考资料 效果一览 基本介绍 MATLAB实现BO-GRU贝叶斯优化门控循环单元回归预测。基于贝…...
Easyx趣味编程7,鼠标消息读取及音频播放
hello大家好,这里是dark flame master,今天给大家带来Easyx图形库最后一节功能实现的介绍,前边介绍了绘制各种图形及键盘交互,文字,图片等操作,今天就可以使写出的程序更加生动且容易操控。一起学习吧&…...
towxml的使用,在微信小程序中快速将markdown格式渲染为wxml文本
towxml的使用,在微信小程序中快速将markdown格式渲染为wxml文本 Towxml概述安装下载 Towxml在小程序中使用 towxml Towxml概述 towxml3.0 支持以下功能: ● echarts图表,默认禁用,需自行构建以开启此功能 ● LaTeX数学公式&#…...
项目管理实战总结(一)-沟通路径问题
前言 那是2021年春节之后,我决定主动申请参与到这个项目,是知道工作强度大、难度大的情况的。有很多的同事是想躲,而我是明知山有虎偏向虎山行。我确定,通过这个项目,一定有我需要的东西。现在项目已经完成了终验专家…...
UE5场景逐渐变亮问题
1、显示 -- 关闭眼部适应 2、项目设置 -- 关闭自动曝光 参考: 虚幻5/UE5 场景亮度逐渐变亮完美解决方法 - 哔哩哔哩...
VM16Pro的Win10虚拟机安装Linux子系统Kali
VM16Pro的Win10虚拟机安装Linux子系统Kali 一、启用Windows功能二、配置WSL三、安装Kali四、安装kali基本工具包五、图形化六、适用的报错七、其他问题参考 一、启用Windows功能 启用后需重启二、配置WSL wsl --update #管理员启动Powershell执行,完成后将下面…...
C++中类的声明
C中类的声明 假设您要编写一个模拟人(如您自己)的程序。人有其特征:姓名、出生日期、出生地和性别(这些信息让每个人都是独一无二的),还能做某些事情,如交谈、自我介绍等。 要在程序中模拟人&…...
IDEA常用AI插件
只推荐免费的 一、对话式AI 1. ChatGPT GPT-4 - Bito AI Code Assistant ChatGPT GPT-4 - Bito AI Code Assistant 插件地址:https://plugins.jetbrains.com/plugin/18289-chatgpt-gpt-4–bito-ai-code-assistant支持自定义prompt支持解释代码支持生成代码注释支持…...
【LeetCode】每日一题最后一个单词的长度投票法求解多数元素异或操作符巧解只出现一次的数字整数反转
个人主页直达:小白不是程序媛 LeetCode系列专栏:LeetCode刷题掉发记 目录 LeetCode 58.最后一个单词的长度 LeetCode169.多数元素 LeetCode 136.出现一次的数字 LeetCode 7.整数反转 LeetCode 58.最后一个单词的长度 难度:简单 OJ链接…...
自然语言处理---注意力机制
注意力概念 观察事物时,之所以能够快速判断一种事物(当然允许判断是错误的),是因为大脑能够很快把注意力放在事物最具有辨识度的部分从而作出判断,而并非是从头到尾的观察一遍事物后,才能有判断结果。正是基于这样的理论…...
目标检测YOLO实战应用案例100讲-基于改进YOLO v7的智能振动分拣系统开发(续)
目录 3.2 引入EIOU损失函数 3.2.1 CIOU损失函数 3.3.2 基于Focal-EIOU损失函数的网络优化 编辑...
Ubuntu - 用户和权限
sudo sudo(Super User Do)是在Linux和Unix系统中用于执行具有超级用户(root)权限的命令的命令。它允许普通用户以特权身份运行特定命令,通常需要输入密码以确认其身份。 sudo 是一种安全的方式,用于限制哪…...
JAVA实现Jfilechooser搜索功能
JAVA实现Jfilechooser搜索功能 背景介绍需求描述思路和方法Java代码实现和注释相关知识点介绍视频演示结语 背景介绍 Java是一种面向对象的编程语言,广泛应用于各种应用程序开发中。文件搜索是我们在日常工作或者学习中经常会遇到的需求,比如查找某个文…...
iOS上架App Store的全攻略
第一步:申请开发者账号 在开始将应用上架到App Store之前,你需要申请一个开发者账号。 1.1 打开苹果开发者中心网站:Apple Developer 1.2 使用Apple ID和密码登录(如果没有账号则需要注册),要确保使用与公…...
线性代数3:矢量方程
一、前言 欢迎回到系列文章的第三篇文章,内容是线性代数的基础知识,线性代数是机器学习背后的基础数学。在我之前的文章中,我介绍了梯队矩阵形式。本文将介绍向量、跨度和线性组合,并将这些新想法与我们已经学到的内容联系起来。本…...
线性代数的本质笔记
课程来自b站发现的《线性代数的本质》,可以帮助从直觉层面理解线性代数的一些基础概念,以及把一些看似不同的数学概念解释之后,发现其实有内在的关联。 这里只对部分内容做一个记录,完整内容请自行观看视频~ 01-向量究竟是什么 …...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...
Vue ③-生命周期 || 脚手架
生命周期 思考:什么时候可以发送初始化渲染请求?(越早越好) 什么时候可以开始操作dom?(至少dom得渲染出来) Vue生命周期: 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...
PH热榜 | 2025-06-08
1. Thiings 标语:一套超过1900个免费AI生成的3D图标集合 介绍:Thiings是一个不断扩展的免费AI生成3D图标库,目前已有超过1900个图标。你可以按照主题浏览,生成自己的图标,或者下载整个图标集。所有图标都可以在个人或…...
