LeetCode Hot100 51~60
- 图论
- 51. 岛屿问题
- 52. 腐烂的橘子
- 53. 课程表
- 54. 前缀树
- 55. 全排列
- 56. 子集
- 57. 电话号码
- 58. 组合总和
- 59. 括号生成
- 60. 单词搜索
图论
51. 岛屿问题
经典洪水问题算法
class Solution {
public:int numIslands(vector<vector<char>>& grid) {int nr = grid.size();int nc = grid[0].size();int count = 0;for (int i = 0; i < nr; i++) {for (int j = 0; j < nc; j++) {if (grid[i][j] == '1') {count++;dfs(grid , i , j);}}} return count;}void dfs(vector<vector<char>>& grid , int i , int j) {int row = grid.size();int col = grid[0].size();grid[i][j] = '0';if (i - 1 >= 0 && grid[i-1][j] == '1') {dfs(grid , i - 1 , j);}if (j-1 >= 0 && grid[i][j-1] == '1') {dfs(grid , i , j - 1);}if (j+1 < col && grid[i][j+1] == '1') {dfs(grid , i , j + 1);}if (i+1 < row && grid[i+1][j] == '1') {dfs(grid , i + 1 , j);}}
};
52. 腐烂的橘子
广度优先遍历 队列来实现
class Solution {int dirt[4][2] = {{-1, 0} , {1 , 0} , {0 , -1} , {0 , 1}};
public:int orangesRotting(vector<vector<int>>& grid) {int min = 0;int fresh = 0;queue<pair<int, int>> que;int row = grid.size();int col = grid[0].size();for (int i = 0; i < row; i++) {for(int j = 0; j < col; j++) {if (grid[i][j] == 1) {fresh++;}if (grid[i][j] == 2) {que.push({i , j});}}}while(!que.empty()) {int n = que.size();bool rotten = false;for (int i = 0; i < n; i++) {auto x = que.front();que.pop();for (auto cur : dirt) {int i = x.first + cur[0]; // 更新x的坐标int j = x.second + cur[1]; // 更新y的坐标if (i>=0 && i < row && j>=0 && j < col && grid[i][j] == 1) {grid[i][j] = 2;que.push({i , j});fresh--;rotten = true;}}}if (rotten) {min++;}}return fresh == 0 ? min : -1;}
};
53. 课程表
class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<int> indegrees(numCourses, 0); // 存储每个课程的入度vector<vector<int>> adjacency(numCourses); // 存储课程的邻接表queue<int> queue;// 生成入度数组和邻接表for (const auto& cp : prerequisites) {indegrees[cp[0]]++;adjacency[cp[1]].push_back(cp[0]);}// 将入度为 0 的课程加入队列for (int i = 0; i < numCourses; i++) {if (indegrees[i] == 0) {queue.push(i);}}// BFS 拓扑排序while (!queue.empty()) {int pre = queue.front();queue.pop();numCourses--; // 完成一门课程,剩下的课程数量减少for (int cur : adjacency[pre]) {if (--indegrees[cur] == 0) {queue.push(cur);}}}// 如果所有课程都能完成,返回 truereturn numCourses == 0;}
};
54. 前缀树
struct Node {Node* son[26]{};bool end = false;
};class Trie {Node* root = new Node();int find(string word) {Node* cur = root;for (char c : word) {c -= 'a';if (cur->son[c] == nullptr) {return 0;}cur = cur->son[c];}return cur->end ? 2 : 1;}public:void insert(string word) {Node* cur = root;for (char c : word) {c -= 'a';if (cur->son[c] == nullptr) {cur->son[c] = new Node();}cur = cur->son[c];}cur->end = true;}bool search(string word) {return find(word) == 2;}bool startsWith(string prefix) {return find(prefix) != 0;}
};
55. 全排列
class Solution {
public:vector<int> vis;vector<int> path;void dfs(vector<vector<int>>& ans, vector<int>& nums, int x) {if (x >= nums.size()) {ans.push_back(path);return;}for (int i = 0; i < nums.size(); i++ ) {if (vis[i]) continue;vis[i]++;path.push_back(nums[i]);dfs(ans, nums, x + 1);vis[i]--;path.pop_back();}}vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> ans;vis.resize(nums.size(), 0);dfs(ans, nums, 0);return ans;}
};
56. 子集
class Solution {
public:vector<int> t;vector<vector<int>> ans;vector<vector<int>> subsets(vector<int>& nums) {int n = nums.size();for (int mask = 0; mask < (1 << n); ++mask) {t.clear();for (int i = 0; i < n; ++i) {if (mask & (1 << i)) {t.push_back(nums[i]);}}ans.push_back(t);}return ans;}
};
57. 电话号码
class Solution {string arr[10] = {"" , "" , "abc" , "def" , "ghi" , "jkl" , "mno" , "pqrs" , "tuv" , "wxyz"};
public:void _letterCombinations(string& digits, int i , string& comb , vector<string>& v){// 首先来看回溯结束的条件 是不是当i走到digits最后的时候就结束啊if (i == digits.size()){v.push_back(comb);return;}int j = 0;string str = arr[digits[i] - '0'];for (j = 0; j < str.size() ; j++ ){_letterCombinations(digits, i+1 , comb += str[j] , v);comb.pop_back();}}vector<string> letterCombinations(string digits) {// 整体思路: 回溯:// 我们首先看看整个digits字符串是否为空 如果为空的话直接返回一个空的vector就好// 如果不是空 这个时候我们就开始使用回溯算法来遍历数字中所有的组合了// 遍历完全厚直接返回就可以vector<string> v;if (digits.empty()){return v;}string comb; // 这个字符串用来接受最后的值// 接下来开始回溯算法 _letterCombinations(digits, 0 , comb , v);return v;}
};
58. 组合总和
class Solution {
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<int> state; // 状态(子集)sort(candidates.begin(), candidates.end()); // 对 candidates 进行排序int start = 0; // 遍历起始点vector<vector<int>> res; // 结果列表(子集列表)backtrack(state, target, candidates, start, res);return res;}
private:void backtrack(vector<int> &state, int target, vector<int> &choices, int start, vector<vector<int>> &res) {// 子集和等于 target 时,记录解if (target == 0) {res.push_back(state);return;}// 遍历所有选择// 剪枝二:从 start 开始遍历,避免生成重复子集for (int i = start; i < choices.size(); i++) {// 剪枝一:若子集和超过 target ,则直接结束循环// 这是因为数组已排序,后边元素更大,子集和一定超过 targetif (target - choices[i] < 0) {break;}// 尝试:做出选择,更新 target, startstate.push_back(choices[i]);// 进行下一轮选择backtrack(state, target - choices[i], choices, i, res);// 回退:撤销选择,恢复到之前的状态state.pop_back();}}
};
59. 括号生成
class Solution {void backtrack(vector<string>& ans, string& cur, int open, int close, int n) {if (cur.size() == n * 2) {ans.push_back(cur);return;}if (open < n) {cur.push_back('(');backtrack(ans, cur, open + 1, close, n);cur.pop_back();}if (close < open) {cur.push_back(')');backtrack(ans, cur, open, close + 1, n);cur.pop_back();}}
public:vector<string> generateParenthesis(int n) {vector<string> result;string current;backtrack(result, current, 0, 0, n);return result;}
};
60. 单词搜索
class Solution {
public:bool exist(vector<vector<char>>& board, string word) {rows = board.size();cols = board[0].size();for(int i = 0; i < rows; i++) {for(int j = 0; j < cols; j++) {if (dfs(board, word, i, j, 0)) return true;}}return false;}
private:int rows, cols;bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {if (i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false;if (k == word.size() - 1) return true;board[i][j] = '\0';bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);board[i][j] = word[k];return res;}
};
相关文章:
LeetCode Hot100 51~60
图论51. 岛屿问题52. 腐烂的橘子53. 课程表54. 前缀树55. 全排列56. 子集57. 电话号码58. 组合总和59. 括号生成60. 单词搜索 图论 51. 岛屿问题 经典洪水问题算法 class Solution { public:int numIslands(vector<vector<char>>& grid) {int nr grid.size…...
docker 启动 redis 同时设置密码,关机后会自动重启
以下是使用Docker启动Redis并设置密码,并配置容器自动重启的命令: docker run -d \--name redis \--restartalways \-p 6379:6379 \redis:latest \redis-server --requirepass "your_strong_password"详细解释: docker run -d&am…...
3D Gaussian Splatting代码详解(一):模型训练、数据加载
1.模型训练 训练流程:train.py中的training函数 这段代码实现了一个 3D 高斯模型的训练循环,旨在通过逐步优化模型参数,使其能够精确地渲染特定场景。以下是代码的详细解析: def training(dataset, opt, pipe, testing_iteratio…...
docker部署RustDesk自建服务器
客户端: Releases rustdesk/rustdesk GitHub 服务端: 项目官方地址:GitHub - rustdesk/rustdesk-server: RustDesk Server Program 1、拉取RustDesk库 docker pull rustdesk/rustdesk-server:latest 阿里云库: docker pu…...
工作实战总结与实现-mybatis-plus更新策略部分字段不更新问题
文章目录 案例场景存在问题解决方案一解决方案二继续延伸 案例场景 很简单的工作场景,需要将数据库某个表的字段设置为null或者空字符串,使用mybatis-plus的update语句,如下: order.setPassCode(null);reservationOrderManger.up…...
MFC扩展库BCGControlBar Pro v36.0新版亮点:黑色主题中的自动反转图标
BCGControlBar库拥有500多个经过全面设计、测试和充分记录的MFC扩展类。 我们的组件可以轻松地集成到您的应用程序中,并为您节省数百个开发和调试时间。 BCGControlBar专业版 v36.0已全新发布了,这个版本在黑暗主题中添加自动图标反转、新增一个全新的S…...
Midjourney Describe API 的对接和使用
Midjourney Describe API 的对接和使用 Midjourney Describe API 的主要功能是通过上传图片,获取对图片的描述。使用该 API,只需要传递图片文件地址,API 会返回图片的详细描述。无需繁琐的参数设置,即可获得高质量的图片描述。 …...
《单片机原理及接口技术》(C51编程)(第三版)------张毅刚主编
1.整体框架:1-22题(17-20为编程题分别源自数中的P98,P162,P177页) 2.简答题部分: 3.计算题...
Qt入门9——绘图
基本概念 虽然Qt已经内置了很多的控件,但是不能保证现有控件就可以应对所有场景. 很多时候我们需要更强的"DIY"能力; Qt 提供了画图相关的API,可以允许我们在窗口上绘制任意的图形形状,来完成更复杂的界面设计。 绘图api核心类: 类说明QPaint…...
FreeRTOS之ARM CR5栈结构操作示意图
FreeRTOS之ARM CR5栈结构操作示意图 1 FreeRTOS源码下载地址2 ARM CR5栈结构操作宏和接口2.1 portSAVE_CONTEXT宏2.1.1 portSAVE_CONTEXT源码2.1.2 portSAVE_CONTEXT宏操作栈结构变化示意图 2.2 portRESTORE_CONTEXT宏2.2.1 portRESTORE_CONTEXT源码2.2.2 portRESTORE_CONTEXT宏…...
Java线程的interrupt中断、wait-notify/all(源码级分析)
实例方法: interrupt()方法是设置结束阻塞(sleep、),并且设置中断标记true isInterrupted()判断当前是否中断 静态方法: Thread.interrupted():调用这个方法的线程中断标记位还原为false 那么好,既然上面的方法作用是清晰的&…...
计网408考点讲解
IPv4...
当linux可执行文件缺少或者不兼容so库时候,如何查看版本以及缺少那些库
解决方法: ldd 命令来验证程序是否加载了正确的库: 如检查linear_elasticity可执行文件缺少的库,用下面命令: ldd linear_elasticity 可以发现下面not found就是缺少的库,还有对应的库的位置已经版本 $ ldd lin…...
文件下载的几种方式
1、使用window.open方法 url: 可以为文件存放的地址 function downloadFile(url) {window.open(url); }2、使用<a>标签进行文件下载 <a href"/多因素登录说明文档.pdf" class"link-text">说明文档</a> 3、使用fetch和Blob对象 这种…...
车联网安全学习之TBOX
Telematics BOX,简称 T-BOX,也称远程信息处理控制单元(Telematics Control Unit, TCU),集成GPS、外部通信接口、电子处理单元、微控制器、移动通信单元和存储器等功能模块。 TBOX 提供的功能有网络接入、OTA、远程控制…...
访问http网页强制跳转到了https的解决办法
目录 解决浏览器自动从 HTTP 重定向到 HTTPS 的问题问题原因:HSTS(HTTP Strict Transport Security)什么是 HSTS?HSTS 的工作原理 如何解决?1. 清除浏览器的 HSTS 信息在 Chrome 中清除 HSTS 信息:在 Firef…...
3D 生成重建016-SA3D从nerf中分割一切
3D 生成重建016-SA3D从nerf中分割一切 文章目录 0 论文工作1 方法介绍2 实验结果 0 论文工作 1 SAM的背景和目标: SAM 是一种强大的二维视觉基础模型,能够在 2D 图像中进行任意物体的分割。传统上,SAM 在二维空间表现出色,但其无…...
阿里云整理(二)
阿里云整理 1. 访问网站2. 专业名词2.1 域名2.2 域名备案2.3 云解析DNS2.4 CDN2.5 WAF 1. 访问网站 用户使用浏览器访问网站大体分为几个过程: 用户在浏览器输入域名URL,例如www.baidu.com。 不过,浏览器并不知道为该域名提供服务的服务器具…...
qt基本部分控件用法(一)
前言: 以前 windows下做工具主要是MFC,趁有点空时间,研究了QT,感觉跟MFC 差不多,VS 比 QT CREATOR 还是强大,不过QT可以跨平台,功能更强大,MFC 只能在win平台下.; 1:环境…...
【Linux】环境ChatGLM-4-9B 模型之 openai API 服务
一、摘要 最近看到 Function Call 比较感兴趣,它的核心是赋予大模型能够调用外部API的能力,能够解决大模型功能扩展性问题,允许模型调用外部数据库或API,提供特定领域的详细信息;解决信息实时性问题,模型可以实时获取最新数据;解决数据局限性问题,大模型训练数据虽多但…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?
FTP(File Transfer Protocol)本身是一个基于 TCP 的协议,理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况,主要原因包括: ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...
在golang中如何将已安装的依赖降级处理,比如:将 go-ansible/v2@v2.2.0 更换为 go-ansible/@v1.1.7
在 Go 项目中降级 go-ansible 从 v2.2.0 到 v1.1.7 具体步骤: 第一步: 修改 go.mod 文件 // 原 v2 版本声明 require github.com/apenella/go-ansible/v2 v2.2.0 替换为: // 改为 v…...
【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架
文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理:检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目:RankRAG:Unifying Context Ranking…...
CVE-2023-25194源码分析与漏洞复现(Kafka JNDI注入)
漏洞概述 漏洞名称:Apache Kafka Connect JNDI注入导致的远程代码执行漏洞 CVE编号:CVE-2023-25194 CVSS评分:8.8 影响版本:Apache Kafka 2.3.0 - 3.3.2 修复版本:≥ 3.4.0 漏洞类型:反序列化导致的远程代…...
