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 ,快速获取一个功能齐全的日…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
