当前位置: 首页 > news >正文

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力扣打卡

打卡记录 统计无向图中无法互相到达点对数&#xff08;并查集 / DFS&#xff09; 链接 并查集 思路&#xff1a;用并查集将连通区域的连在一起&#xff0c;再遍历所有点&#xff0c;用hash表存储不同连通块的元素个数&#xff0c;然后 乘积和 便是答案。 注意&#xff1a; /…...

10月面试js基础

作用域 变量的可用范围 作用域链 保存的变量的使用顺序的一个链&#xff08;也就是路线图&#xff09;&#xff0c; 被称为作用域链。 当在Javascript中使用一个变量的时候&#xff0c;首先Javascript引擎会尝试在当前作用域下去寻找该变量&#xff0c;如果没找到&#xff0c;再…...

研发日常踩坑-Mysql分页数据重复 | 京东云技术团队

踩坑描述: 写分页查询接口&#xff0c;order by和limit混用的时候&#xff0c;出现了排序的混乱情况 在进行第N页查询时&#xff0c;出现与第一前面页码的数据一样的记录。 问题 在MySQL中分页查询&#xff0c;我们经常会用limit&#xff0c;如:limit(0,20)表示查询第一页的…...

Ubuntu18.04安装QGC报错 `GLIBC_2.29‘ not found

按照官网教程&#xff0c;最后运行时出错。 /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大家好&#xff0c;这里是dark flame master&#xff0c;今天给大家带来Easyx图形库最后一节功能实现的介绍&#xff0c;前边介绍了绘制各种图形及键盘交互&#xff0c;文字&#xff0c;图片等操作&#xff0c;今天就可以使写出的程序更加生动且容易操控。一起学习吧&…...

towxml的使用,在微信小程序中快速将markdown格式渲染为wxml文本

towxml的使用&#xff0c;在微信小程序中快速将markdown格式渲染为wxml文本 Towxml概述安装下载 Towxml在小程序中使用 towxml Towxml概述 towxml3.0 支持以下功能&#xff1a; ● echarts图表&#xff0c;默认禁用&#xff0c;需自行构建以开启此功能 ● LaTeX数学公式&#…...

项目管理实战总结(一)-沟通路径问题

前言 那是2021年春节之后&#xff0c;我决定主动申请参与到这个项目&#xff0c;是知道工作强度大、难度大的情况的。有很多的同事是想躲&#xff0c;而我是明知山有虎偏向虎山行。我确定&#xff0c;通过这个项目&#xff0c;一定有我需要的东西。现在项目已经完成了终验专家…...

UE5场景逐渐变亮问题

1、显示 -- 关闭眼部适应 2、项目设置 -- 关闭自动曝光 参考&#xff1a; 虚幻5/UE5 场景亮度逐渐变亮完美解决方法 - 哔哩哔哩...

VM16Pro的Win10虚拟机安装Linux子系统Kali

VM16Pro的Win10虚拟机安装Linux子系统Kali 一、启用Windows功能二、配置WSL三、安装Kali四、安装kali基本工具包五、图形化六、适用的报错七、其他问题参考 一、启用Windows功能 启用后需重启二、配置WSL wsl --update #管理员启动Powershell执行&#xff0c;完成后将下面…...

C++中类的声明

C中类的声明 假设您要编写一个模拟人&#xff08;如您自己&#xff09;的程序。人有其特征&#xff1a;姓名、出生日期、出生地和性别&#xff08;这些信息让每个人都是独一无二的&#xff09;&#xff0c;还能做某些事情&#xff0c;如交谈、自我介绍等。 要在程序中模拟人&…...

IDEA常用AI插件

只推荐免费的 一、对话式AI 1. ChatGPT GPT-4 - Bito AI Code Assistant ChatGPT GPT-4 - Bito AI Code Assistant 插件地址&#xff1a;https://plugins.jetbrains.com/plugin/18289-chatgpt-gpt-4–bito-ai-code-assistant支持自定义prompt支持解释代码支持生成代码注释支持…...

【LeetCode】每日一题最后一个单词的长度投票法求解多数元素异或操作符巧解只出现一次的数字整数反转

个人主页直达&#xff1a;小白不是程序媛 LeetCode系列专栏&#xff1a;LeetCode刷题掉发记 目录 LeetCode 58.最后一个单词的长度 LeetCode169.多数元素 LeetCode 136.出现一次的数字 LeetCode 7.整数反转 LeetCode 58.最后一个单词的长度 难度&#xff1a;简单 OJ链接…...

自然语言处理---注意力机制

注意力概念 观察事物时&#xff0c;之所以能够快速判断一种事物(当然允许判断是错误的)&#xff0c;是因为大脑能够很快把注意力放在事物最具有辨识度的部分从而作出判断&#xff0c;而并非是从头到尾的观察一遍事物后&#xff0c;才能有判断结果。正是基于这样的理论&#xf…...

目标检测YOLO实战应用案例100讲-基于改进YOLO v7的智能振动分拣系统开发(续)

目录 3.2 引入EIOU损失函数 3.2.1 CIOU损失函数 3.3.2 基于Focal-EIOU损失函数的网络优化 ​编辑...

Ubuntu - 用户和权限

sudo sudo&#xff08;Super User Do&#xff09;是在Linux和Unix系统中用于执行具有超级用户&#xff08;root&#xff09;权限的命令的命令。它允许普通用户以特权身份运行特定命令&#xff0c;通常需要输入密码以确认其身份。 sudo 是一种安全的方式&#xff0c;用于限制哪…...

JAVA实现Jfilechooser搜索功能

JAVA实现Jfilechooser搜索功能 背景介绍需求描述思路和方法Java代码实现和注释相关知识点介绍视频演示结语 背景介绍 Java是一种面向对象的编程语言&#xff0c;广泛应用于各种应用程序开发中。文件搜索是我们在日常工作或者学习中经常会遇到的需求&#xff0c;比如查找某个文…...

​iOS上架App Store的全攻略

第一步&#xff1a;申请开发者账号 在开始将应用上架到App Store之前&#xff0c;你需要申请一个开发者账号。 1.1 打开苹果开发者中心网站&#xff1a;Apple Developer 1.2 使用Apple ID和密码登录&#xff08;如果没有账号则需要注册&#xff09;&#xff0c;要确保使用与公…...

线性代数3:矢量方程

一、前言 欢迎回到系列文章的第三篇文章&#xff0c;内容是线性代数的基础知识&#xff0c;线性代数是机器学习背后的基础数学。在我之前的文章中&#xff0c;我介绍了梯队矩阵形式。本文将介绍向量、跨度和线性组合&#xff0c;并将这些新想法与我们已经学到的内容联系起来。本…...

线性代数的本质笔记

课程来自b站发现的《线性代数的本质》&#xff0c;可以帮助从直觉层面理解线性代数的一些基础概念&#xff0c;以及把一些看似不同的数学概念解释之后&#xff0c;发现其实有内在的关联。 这里只对部分内容做一个记录&#xff0c;完整内容请自行观看视频~ 01-向量究竟是什么 …...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...