LeetCode Hot 100:图论
LeetCode Hot 100:图论
200. 岛屿数量
思路 1:深度优先搜索
class Solution {
private:const int dx[4] = {-1, 0, 1, 0};const int dy[4] = {0, 1, 0, -1};public:int numIslands(vector<vector<char>>& grid) {if (grid.empty())return 0;int m = grid.size(), n = m ? grid[0].size() : 0;function<void(int, int)> dfs = [&](int x, int y) -> void {if (x < 0 || x >= m || y < 0 || y >= n)return;if (grid[x][y] == '0')return;grid[x][y] = '0';for (int i = 0; i < 4; i++) {int r = x + dx[i], c = y + dy[i];dfs(r, c);}};int ans = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (grid[i][j] == '1') {ans++;dfs(i, j);}return ans;}
};
思路 2:广度优先搜索
class Solution {
public:int numIslands(vector<vector<char>>& grid) {if (grid.empty())return 0;int m = grid.size(), n = m ? grid[0].size() : 0;int islands = 0;for (int r = 0; r < m; r++)for (int c = 0; c < n; c++)if (grid[r][c] == '1') {islands++;grid[r][c] = '0';queue<pair<int, int>> neighbors;neighbors.push({r, c});while (!neighbors.empty()) {auto rc = neighbors.front();neighbors.pop();int row = rc.first, col = rc.second;if (row - 1 >= 0 && grid[row - 1][col] == '1') {neighbors.push({row - 1, col});grid[row - 1][col] = '0';}if (row + 1 < m && grid[row + 1][col] == '1') {neighbors.push({row + 1, col});grid[row + 1][col] = '0';}if (col - 1 >= 0 && grid[row][col - 1] == '1') {neighbors.push({row, col - 1});grid[row][col - 1] = '0';}if (col + 1 < n && grid[row][col + 1] == '1') {neighbors.push({row, col + 1});grid[row][col + 1] = '0';}}}return islands;}
};
994. 腐烂的橘子
思路 1:广度优先搜索
class Solution {
private:const int dx[4] = {0, 0, 1, -1};const int dy[4] = {1, -1, 0, 0};public:int orangesRotting(vector<vector<int>>& grid) {int m = grid.size(), n = m ? grid[0].size() : 0;queue<pair<int, int>> q;int fresh = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (grid[i][j] == 1)fresh++;else if (grid[i][j] == 2)q.push({i, j});}if (fresh == 0)return 0;else if (q.empty())return -1;int time = 0;while (fresh > 0 && !q.empty()) {int size = q.size();for (int i = 0; i < size; i++) {auto [x, y] = q.front();q.pop();for (int i = 0; i < 4; i++) {int r = x + dx[i], c = y + dy[i];if (r >= 0 && r < m && c >= 0 && c < n)if (grid[r][c] == 1) {fresh--;grid[r][c] = 2;q.push({r, c});}}}time++;}return fresh > 0 ? -1 : time;}
};
207. 课程表
思路 1:拓扑排序
class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> graph(numCourses, vector<int>()); // 邻接矩阵vector<int> inDegree(numCourses, 0); // 入度数组for (vector<int>& prerequisity : prerequisites) {int from = prerequisity[1];int to = prerequisity[0];graph[from].push_back(to);inDegree[to]++;}queue<int> q;// 把入度为0的节点(即没有前置课程要求)放在队列中for (int i = 0; i < inDegree.size(); i++)if (inDegree[i] == 0)q.push(i);while (!q.empty()) {int u = q.front();q.pop();for (int& v : graph[u]) {inDegree[v]--;if (inDegree[v] == 0)q.push(v);}}for (int& in : inDegree)if (in)return false;return true;}
};
208. 实现 Trie (前缀树)
思路 1:字典树
class TrieNode {
public:TrieNode* childNode[26];bool isEnd;TrieNode() : isEnd(false) {for (int i = 0; i < 26; i++)childNode[i] = nullptr;}
};class Trie {
private:TrieNode* root;public:Trie() : root(new TrieNode()) {}// 向字典树插入一个词void insert(string word) {TrieNode* node = root;for (char& c : word) {if (node->childNode[c - 'a'] == nullptr)node->childNode[c - 'a'] = new TrieNode();node = node->childNode[c - 'a'];}node->isEnd = true;}// 判断字典树里是否有一个词bool search(string word) {TrieNode* node = root;for (char& c : word) {if (node == nullptr)break;node = node->childNode[c - 'a'];}return node ? node->isEnd : false;}// 判断字典树是否有一个以词开始的前缀bool startsWith(string prefix) {TrieNode* node = root;for (char& c : prefix) {if (node == nullptr)break;node = node->childNode[c - 'a'];}return node != nullptr;}
};/*** Your Trie object will be instantiated and called as such:* Trie* obj = new Trie();* obj->insert(word);* bool param_2 = obj->search(word);* bool param_3 = obj->startsWith(prefix);*/
相关文章:
LeetCode Hot 100:图论
LeetCode Hot 100:图论 200. 岛屿数量 思路 1:深度优先搜索 class Solution { private:const int dx[4] {-1, 0, 1, 0};const int dy[4] {0, 1, 0, -1};public:int numIslands(vector<vector<char>>& grid) {if (grid.empty())retu…...
tracert和ping的区别
1、简介 tracert(在 Windows 系统中)和 traceroute(在 Unix/Linux 系统中)以及 ping 都是网络诊断工具,但它们的功能和用途有所不同: ping: 用途:ping 是一个网络工具&…...
回归、分类模型的评估指标
1. 分类模型的评估指标 评估机器学习模型的好坏至关重要,它帮助我们判断模型的性能、稳定性以及在实际问题中的应用效果。不同类型的机器学习任务(分类、回归、聚类等)有不同的评估指标。以下是详细介绍常见的模型评估指标,尤其针…...
k8s中如何将pod的标准输出日志输出到一个文件
假设容器的启动命令是 grpcserver,我们将通过修改启动命令,将 grpcserver 的标准输出重定向到指定的日志文件 /var/log/app/grpcserver.log,同时保留标准输出以便 Kubernetes 日志系统仍然能够捕获日志。 目标: 将 grpcserver 的…...
软件工程文档规范要点总结
需求分析文档 1.目标用户应该体现为用例图里的执行者(执行者要标明是哪一类用户) 2.用例模型由功能概述得到,用例顺序图由基本交互过程得到,分析类图由顺序图得到 3.执行者和用例之间的关系:执行、触发、驱动 用例…...
Django 序列化serializers
在Django中,序列化通常指的是将数据库中的模型数据转换为JSON、XML或其他格式的过程。Django提供了内置的序列化工具,可以通过django.core.serializers模块进行序列化操作。 当你使用Django的序列化功能时,可以序列化以下两种对象类型&#…...
混个1024勋章
一眨眼毕业工作已经一年了,偶然进了游戏公司成了一名初级游戏服务器开发。前两天总结的时候,本来以为自己这一年没学到多少东西,但是看看自己的博客其实也有在进步,虽然比不上博客里的众多大佬,但是回头看也算是自己的…...
Java Spring Boot 项目开发示例指南
开发和扩展一个 Java Spring Boot 项目可以分为几个步骤。以下是一个简单的指南,涵盖项目的创建、基本功能的实现、以及扩展的示例。 第一步:创建 Spring Boot 项目 使用 Spring Initializr 创建项目: 访问 Spring Initializr选择项目的配置(…...
Python学习路线:从新手到专家
引言 Python 是一种高级编程语言,以其简洁清晰的语法而闻名,被广泛应用于Web开发、数据科学、人工智能、自动化脚本等领域。无论你是编程初学者还是有经验的开发者,Python 都是一个值得学习的语言。本文将提供一份详细的Python学习路线图&am…...
R实验——logistic回归、LDA、QDAKNN
数据集介绍: mpg,miles per gallon即油耗,这个数据集来自卡内基梅隆大学维护的StatLib库。1983年美国统计协会博览会使用了该数据集。这个数据集是对StatLib库中提供的数据集稍加修改的版本。根据Ross Quinlan(1993)在预测属性“mpg”中的使…...
Java 使用 itextpdf 自定义 生成 pdf
Java 使用 itextpdf 自定义 生成 pdf maven 依赖实现docker 服务 字体文件找不到问题 maven 依赖 <!-- iText 7 --> <dependency><groupId>com.itextpdf</groupId><artifactId>itext7-core</artifactId><version>7.2.3</version…...
Rust小练习,编写井字棋
画叉画圈的游戏通常指的是 井字棋(Tic-Tac-Toe),是一个简单的两人游戏,规则如下: 游戏规则 棋盘:游戏在一个3x3的方格上进行。玩家:有两个玩家,一个用“X”表示,另一个…...
RabbitMQ 入门(八)SpringAMQP消息转换器
一、消息转换器 Spring会把你发送的消息序列化为字节发送给MQ,接收消息的时候,还会把字节反序列化为Java对象。 只不过,默认情况下Spring采用的序列化方式是JDK序列化。众所周知,JDK序列化存在下列问题: - 数…...
【C++】一文带你深入理解C++异常机制
⭐️个人主页:小羊 ⭐️所属专栏:C 很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~ 目录 前言一、C语言处理错误的方式二、C异常三、异常的使用3.1 异常的抛出和捕获3.2 异常的重新抛出3.3 异常安全3.4 异常规范 四、自定义异…...
Qt之QObject
简介 QObject是qt中所有对象的基类,也是信号槽的基础 结构 #mermaid-svg-mpp2FHEcRCzUK75S {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-mpp2FHEcRCzUK75S .error-icon{fill:#552222;}#mermaid-svg-…...
鸿蒙到底是不是纯血?到底能不能走向世界?
关注卢松松,会经常给你分享一些我的经验和观点。 2016年5月鸿蒙系统开始立项。 2018年美国开始经济战争,其中一项就是制裁华为,不让华为用安卓。 2019年8月9日华为正式发布鸿蒙系统。问题就出在这里,大家可以仔细看。 安卓一…...
【Android】MVP架构
MVP架构简介 MVP(Model-View-Presenter)是一种常见的软件架构模式,尤其在Android应用开发中被广泛使用。它将应用程序分为三层:Model、View 和 Presenter,以实现职责分离,提高代码的可维护性和可测试性。 …...
Web服务器之Nginx
Nginx(发音为Engine X)是一款开源的高性能HTTP和反向代理服务器,同时也提供了IMAP/POP3/SMTP服务。由伊戈尔赛索耶夫(Igor Sysoev)为俄罗斯访问量第二的Rambler.ru站点开发,Nginx自发布以来,凭借…...
【大模型实战篇】大模型分词算法Unigram及代码示例
1. 算法原理介绍 与 BPE 分词(参考《BPE原理及代码示例》)和 WordPiece 分词(参考《WordPiece原理及代码示例》)不同,Unigram 分词方法【1】是从一个包含足够多字符串或词元的初始集合开始,迭代地删除其中的…...
Dockerfile搭建ELK
使用 Dockerfile 安装 ELK 一、引言 ELK Stack(Elasticsearch, Logstash, Kibana)是一种流行的日志管理和分析解决方案。它允许用户实时搜索、分析和可视化日志数据。通过 Docker,可以方便地部署 ELK ,快速获取一个功能齐全的日…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...
