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

力扣hot100——图论

200. 岛屿数量

class Solution {
public:int numIslands(vector<vector<char>>& grid) {int ans = 0;vector<int> dx = { 0, 1, 0, -1 };vector<int> dy = { 1, 0, -1, 0 };int n = grid.size(), m = grid[0].size();vector<vector<int>> vis(n, vector<int>(m, 0));auto dfs = [&](this auto&& dfs, int x, int y) -> void {vis[x][y] = 1;for (int i = 0; i < 4; i++) {int tx = x + dx[i];int ty = y + dy[i];if (tx < 0 || ty < 0 || tx >= n || ty >= m) continue;if (grid[tx][ty] == '0' || vis[tx][ty]) continue;dfs(tx, ty);}};for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!vis[i][j] && grid[i][j] == '1') {dfs(i, j);ans++;}}}return ans;}
};

 dfs求连通块

994. 腐烂的橘子 

class Solution {
public:int orangesRotting(vector<vector<int>>& a) {vector<int> dx = { 0, 1, 0, -1 };vector<int> dy = { 1, 0, -1, 0 };int n = a.size(), m = a[0].size();vector<vector<int>> vis(n, vector<int>(m, 0));queue <pair<int, int>> q;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (a[i][j] == 2) q.push({ i, j });}}int ans = 0;while (q.size()) {if (q.size()) ans++;vector<pair<int, int>> v;while (q.size()) {auto [x, y] = q.front();q.pop();vis[x][y] = 1;v.push_back({x, y});}for (auto [x, y] : v) {for (int i = 0; i < 4; i++) {int tx = x + dx[i], ty = y + dy[i];if (tx < 0 || ty < 0 || tx >= n || ty >= m) continue;if (vis[tx][ty] || a[tx][ty] != 1) continue;q.push({tx, ty});}}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (a[i][j] == 1 && !vis[i][j]) return -1;}}return max(ans - 1, 0);}
};

bfs

207. 课程表 

class Solution {
public:bool canFinish(int n, vector<vector<int>>& a) {vector<vector<int>> e(n);vector<int> deg(n, 0);for (int i = 0; i < a.size(); i++) {int x = a[i][0], y = a[i][1];e[x].push_back(y);deg[y]++;}int cnt = 0;queue<int> q;for (int i = 0; i < n; i++) {if (!deg[i]) q.push(i);}while (q.size()) {auto u = q.front();q.pop();cnt++;for (auto v : e[u]) {deg[v]--;if (!deg[v]) q.push(v);}}return cnt == n;}
};

拓扑排序

 208. 实现 Trie (前缀树)

class Trie {
public:int idx;vector<vector<int>> tr;vector<int> cnt;Trie() {idx = 0;tr.resize(1e5, vector<int>(26, 0));cnt.resize(1e5, 0);}void insert(string word) {int p = 0;for (auto ch : word) {int t = ch - 'a';if (!tr[p][t]) tr[p][t] = ++idx;p = tr[p][t];}cnt[p]++;}bool search(string word) {int p = 0;for (auto ch : word) {int t = ch - 'a';if (!tr[p][t]) return false;p = tr[p][t];}return cnt[p];}bool startsWith(string prefix) {int p = 0;for (auto ch : prefix) {int t = ch - 'a';if (!tr[p][t]) return false;p = tr[p][t];}return true;}
};

字典树,注意节点不为0不代表有这个前缀

然后注意tr数组一维的大小

相关文章:

力扣hot100——图论

200. 岛屿数量 class Solution { public:int numIslands(vector<vector<char>>& grid) {int ans 0;vector<int> dx { 0, 1, 0, -1 };vector<int> dy { 1, 0, -1, 0 };int n grid.size(), m grid[0].size();vector<vector<int>> …...

Docker- Unable to find image “hello-world“locally

Docker- Unable to find image “hello-world“locally 文章目录 Docker- Unable to find image “hello-world“locally问题描述一. 切换镜像1. 编辑镜像源2. 切换镜像内容 二、 检查设置1、 重启dockers2、 检查配置是否生效3. Docker镜像源检查4. Dokcer执行测试 三、自定义…...

spring-boot启动源码分析(二)之SpringApplicationRunListener

在上一篇《spring-boot启动源码分析&#xff08;一&#xff09;之SpringApplication实例构造》后&#xff0c;继续看了一个月的Spring boot启动源码&#xff0c;初步把流程看完了&#xff0c;接下来会不断输出总结&#xff0c;以巩固这段时间的学习。同时也希望能帮到同样感兴趣…...

ELK入门教程(超详细)

什么是ELK&#xff1f; ELK是Elasticsearch、Logstash、Kibana三大开源框架首字母大写简称(后来出现的filebeat属于beats家族中的一员&#xff0c;可以用来替代logstash的数据收集功能&#xff0c;比较轻量级)&#xff0c;也被称为Elastic Stack。 Filebeat Filebeat是用于转…...

人工智能知识分享第六天-机器学习_​逻辑回归(Logistic Regression)

简介 在机器学习中&#xff0c;分类问题是一种常见的任务&#xff0c;目标是根据输入特征将数据点分配到不同的类别中。为了实现分类&#xff0c;我们需要训练一个分类器&#xff0c;该分类器能够根据输入数据的特征进行预测。 逻辑回归&#xff08;Logistic Regression&…...

基于Springboot + vue实现的校园周边美食探索及分享平台

&#x1f942;(❁◡❁)您的点赞&#x1f44d;➕评论&#x1f4dd;➕收藏⭐是作者创作的最大动力&#x1f91e; &#x1f496;&#x1f4d5;&#x1f389;&#x1f525; 支持我&#xff1a;点赞&#x1f44d;收藏⭐️留言&#x1f4dd;欢迎留言讨论 &#x1f525;&#x1f525;&…...

初学STM32 --- 外部SRAM

目录 SRAM简介 SRAM特性: XM8A51216 功能框图 8080并口读时序​编辑 8080并口写时序 SRAM 读写操作步骤 FSMC介绍 FSMC时序介绍 FSMC控制器对内核地址映射​编辑 FSMC HAL库相关驱动 SRAM驱动步骤 SRAM简介 静态随机存取存储器&#xff08;Static Random-Access Memory&am…...

创龙3588——debian根文件系统制作

文章目录 build.sh debian 执行流程build.sh源码流程 30-rootfs.sh源码流程 mk-rootfs-bullseys.sh源码流程 mk-sysroot.sh源码流程 mk-image.sh源码流程 post-build.sh 大致流程系统制作步骤 build.sh debian 执行流程 build.sh 源码 run_hooks() {DIR"$1"shiftf…...

javacript中function (res) {}与箭头函数表达式(res) =>{}的区别

javacript中function (res) {}与(res) &#xff1e;{}的区别 function (res) {} 代码演示 let shape {name:长方形,say:function(){console.log(我是this.name)setTimeout(function(){console.log(3秒后输出我是: this.name); //this.name为undefined}, 3000)} }shape.sa…...

kylin安装docker

1. 前言 本文详细介绍如何在kylin v10上安装docker。系统环境如下&#xff1a; dockder: 20.10.7 linux os: kylinv 10 (GFB) linux kernel: 4.19.90-52.23.v2207.gfb01.ky10.aarch642. 安装docker 2.1. 下载docker二进制包 wget https://mirror.nju.edu.cn…...

【Yarn】通过JMX采集yarn相关指标的Flink任务核心逻辑

通过JMX采集yarn相关指标的Flink任务核心逻辑 文章目录 通过JMX采集yarn相关指标的Flink任务核心逻辑通过jmx接口查询Yarn队列指标请求JMX配置项核心处理流程输出到kafka格式通过jmx接口查询ResourceManager核心指标请求JMX读取配置yaml配置文件核心处理逻辑输出Kafka格式彩蛋 …...

鸿蒙HarmonyOS开发:基于Swiper组件和自定义指示器实现多图片进度条轮播功能

文章目录 一、概述1、场景介绍2、技术选型 二、实现方案1、图片区域实现2、底部导航点设计3、手动切换 三、所有代码1、设置沉浸式2、外层Tabs效果3、ImageSwiper组件 四、效果展示 一、概述 在短视频平台上&#xff0c;经常可以见到多图片合集。它的特点是&#xff1a;由多张…...

Excel 身份证号计算年龄

1. 设置身份证号列格式 复制身份证列值到记事本或其他地方重新设置身份证号列单元格格式为“文本”将复制出去的身份证号重新复制粘贴回来 2. 年龄列单元格中添加公式 DATEDIF(DATE(LEFT(MID(A2, 7, 8), 4), MID(MID(A2, 7, 8), 5, 2), RIGHT(MID(A2, 7, 8), 2)), TODAY(), …...

【2024年-6月-14日-开源社区openEuler实践记录】探索 test - tools:高效测试的开源宝库

开篇引言 大家好&#xff0c;我是 fzr123&#xff0c;在软件开发领域深耕多年&#xff0c;一直致力于探索各种提升效率的工具与技术。今天&#xff0c;我将为大家深入介绍一款在测试领域极具价值的开源项目——test - tools&#xff0c;它为开发者们提供了一系列强大的测试功能…...

2022浙江大学信号与系统笔记

原视频地址&#xff1a;2022浙江大学信号与系统&#xff08;含配套课件和代码&#xff09; - 胡浩基老师-哔哩哔哩 ⭐⭐⭐ 我的笔记&#xff1a;飞书链接 - 信号与系统 基于视频&#xff0c;记得笔记&#xff0c;加了点自己的补充&#xff08;有的是问 ChatGPT 的&#xff09;…...

DeepSeek-VL2

《DeepSeek-VL2: Mixture-of-Experts Vision-Language Models for Advanced Multimodal Understanding》是 DeepSeek-AI 团队发布的关于视觉语言模型 DeepSeek-VL2 的论文&#xff0c;以下是对该论文的详细介绍&#xff1a; 研究背景与动机 多模态理解的重要性&#xff1a;在当…...

前端⾯试⼋股⽂

1.http 和 https 的基本概念 - http: 是⼀个客⼾端和服务器端请求和应答的标准&#xff08;TCP&#xff09;&#xff0c;⽤于从 WWW 服务器传输超⽂本到本地浏 览器的超⽂本传输协议。 - https:是以安全为⽬标的 HTTP 通道&#xff0c;即 HTTP 下 加⼊ SSL 层进⾏加密。其作⽤…...

【Rust自学】8.6. HashMap Pt.2:更新HashMap

8.6.0. 本章内容 第八章主要讲的是Rust中常见的集合。Rust中提供了很多集合类型的数据结构&#xff0c;这些集合可以包含很多值。但是第八章所讲的集合与数组和元组有所不同。 第八章中的集合是存储在堆内存上而非栈内存上的&#xff0c;这也意味着这些集合的数据大小无需在编…...

Python异常处理详解:概念、语法与实践

1. 异常的概念 在Python中&#xff0c;异常&#xff08;Exception&#xff09;是程序运行时出现的错误或不正常情况。异常通常表示程序在运行时遇到了无法继续执行的条件。Python通过 try/except 语句来捕获和处理异常。 异常可以分为两类&#xff1a; 内建异常&#xff1a;…...

Kotlin在医疗大健康域的应用实例探究与编程剖析(上)

一、引言 1.1 研究背景与意义 在当今数字化时代,医疗行业正经历着深刻的变革。随着信息技术的飞速发展,尤其是人工智能、大数据、物联网等新兴技术的广泛应用,医疗行业数字化转型已成为必然趋势。这种转型旨在提升医疗服务的效率和质量,优化医疗资源配置,为患者提供更加…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

Python 高级应用10:在python 大型项目中 FastAPI 和 Django 的相互配合

无论是python&#xff0c;或者java 的大型项目中&#xff0c;都会涉及到 自身平台微服务之间的相互调用&#xff0c;以及和第三发平台的 接口对接&#xff0c;那在python 中是怎么实现的呢&#xff1f; 在 Python Web 开发中&#xff0c;FastAPI 和 Django 是两个重要但定位不…...