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-向量究竟是什么 …...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
