代码随想录训练营Day21 | 491.递增子序列 - 46.全排列 - 47.全排列 II - 332.重新安排行程 - 51.N皇后 - 37.解数独
491.递增子序列
- 题目链接:491.递增子序列
- 思路:和子集那道题思路很像,每次在数组中选择一个数,选过的数不能选择,这里要求集合数量必须大于2个才能符合,仍然需要去重,但这里选额的是子序列,数组不能进行排序,故去重使用集合,记录当前回溯函数选择过的数,遇到选择过的数不需要再重新选择
- 代码:
class Solution {
public:vector<vector<int>> findSubsequences(vector<int>& nums) {vector<vector<int>> ans;vector<int> tmp;int n = nums.size();auto dfs = [&](auto&& dfs, int i) {if(i > n) // 终止条件return;if(tmp.size() >= 2) // 符合题目条件加入答案中ans.push_back(tmp);set<int> cnt; // 集合去重,每次回溯函数,同一个数只选择一次for(int j = i; j < n; ++j) {if(!tmp.empty() && nums[j] < tmp.back()) // 每次选择的数必须是递增的continue;if(!cnt.count(nums[j])) {tmp.push_back(nums[j]);dfs(dfs, j + 1);tmp.pop_back();cnt.insert(nums[j]);}}};dfs(dfs, 0);return ans;}
};
46.全排列
- 题目链接:46.全排列
- 思路:全排列思路仍然是每次从数组中选择一个数,选过的数不能再选,因为全排列的特殊性,排列长度和数组长度一样,故不需要额外创建数组来记录每次选择结果,每次将选择的数和当前应该选择的位置上的数交换即可
- 代码:
class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> ans;int n = nums.size();vector<int> tmp;auto dfs = [&](auto&& dfs, int i) {if(i == n) {ans.push_back(nums); // 选择成功加入到ans中return;}for(int j = i; j < n; ++j) {swap(nums[i], nums[j]); // 选择 nums[j],将它和nums[i] 交换dfs(dfs, i + 1);swap(nums[i], nums[j]); // 再交换回来}};dfs(dfs, 0); // 从0开始选择return ans;}
};
47.全排列 II
- 题目链接:47.全排列 II
- 思路:思路和上一题一致,这里需要去重,即相同的数,只能选择一次,去重方法和子序列那题类似,使用集合去重
- 代码:
class Solution {
public:vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> ans;int n = nums.size();vector<int> tmp;auto dfs = [&](auto&& dfs, int i) {if(i == n) {ans.push_back(nums);return;}set<int> cnt; // 集合去重for(int j = i; j < n; j++) {if(cnt.count(nums[j]) != 0) // 去重continue;swap(nums[i], nums[j]); // 交换dfs(dfs, i + 1);swap(nums[i], nums[j]); // 交换cnt.insert(nums[j]); // 选择的数加入到集合中}};dfs(dfs, 0); // 从0开始return ans;}
};
332.重新安排行程
- 题目链接:332.重新安排行程
- 思路:本题没有完整的思路,一刷感觉思路不完善,这里使用的是卡哥的代码,二刷的时候仔细思考,卡哥讲解
- 代码:
class Solution {
private:
// unordered_map<出发城市, map<到达城市, 航班次数>> targets
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result) {if (result.size() == ticketNum + 1) {return true;}for (pair<const string, int>& target : targets[result[result.size() - 1]]) {if (target.second > 0 ) { // 使用int字段来记录到达城市是否使用过了result.push_back(target.first);target.second--;if (backtracking(ticketNum, result)) return true;result.pop_back();target.second++;}}return false;
}
public:vector<string> findItinerary(vector<vector<string>>& tickets) {vector<string> result;for (const vector<string>& vec : tickets) {targets[vec[0]][vec[1]]++; // 记录映射关系}result.push_back("JFK");backtracking(tickets.size(), result);return result;}
};
51.N皇后
- 题目链接:51.N皇后
- 思路:
- N皇后经典题目,使用回溯算法,每次选择一个位置放入皇后,当不符合的时候回溯选择其他位置;
- 使用数组arr,记录每行选择的皇后的列的位置,从第0行开始回溯,每次回溯代表着选择某一行选择某一列放置皇后;
- 使用judge函数判断当前位置是否可以放置皇后;
- GetRow函数获取每行的字符串形式;
- 代码:
class Solution {
public:vector<vector<string>> solveNQueens(int n) {vector<vector<string>> ans;vector<string> row;vector<int> arr(n, 0); // 存储每一行放的皇后的列数auto judge = [&](int t) ->bool {for(int i = 0; i < t; ++i) {// 判断是否有皇后在同一列,判断皇后是否在斜线上,即横坐标距离,于纵坐标之间的距离是否相等if(arr[i] == arr[t] || abs(t - i) == abs(arr[t] - arr[i]))return false;}return true;};auto GetRow = [&](int k) -> string { // 将某一行转换为字符串stringstream ss;for(int i = 0; i < n; ++i) {if(i == k)ss << 'Q';elsess << '.';}return ss.str();};auto dfs = [&](auto&& dfs, int i) {if(i == n) {ans.push_back(row); // 符合放入答案中return;}for(int j = 0; j < n; ++j) { // 每行选择某一列放置皇后arr[i] = j; // 第i行选择将皇后放到第 j 列, 即[i, j]的位置if(judge(i)) { // 判断皇后位置是否合法row.push_back(GetRow(j));dfs(dfs, i + 1);row.pop_back();}}};dfs(dfs, 0); // 从第0行开始,从行开始回溯,默认每次放置的皇后都不再同一行return ans;}
};
37.解数独
- 题目链接:37.解数独
- 思路:
- 回溯数独每一个位置,每个位置需要填写时,从1-9选择一个数;
- 每个数的填充需要进行判断是否符合数独的条件。
- 代码:
class Solution {
public:void solveSudoku(vector<vector<char>>& board) {int n = board.size();// 判断当前位置是否符合数独条件auto isTrue = [&] (int row, int col, char val) {for (int i = 0; i < 9; i++) { // 判断行里是否重复if (board[row][i] == val) {return false;}}for (int j = 0; j < 9; j++) { // 判断列里是否重复if (board[j][col] == val) {return false;}}int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复for (int j = startCol; j < startCol + 3; j++) {if (board[i][j] == val ) {return false;}}}return true;};auto dfs = [&](auto&& dfs) -> bool {// 遍历数独 for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {if(board[i][j] != '.') continue;// 需要填充时,从1到9选择for(int k = 1; k <= 9; k++) { if(isTrue(i, j, k + '0')) { // 判断当前位置放入 k ,是否符合数独条件board[i][j] = k + '0';if(dfs(dfs))return true;board[i][j] = '.';}}return false;}}return true;};dfs(dfs);}
};
相关文章:
代码随想录训练营Day21 | 491.递增子序列 - 46.全排列 - 47.全排列 II - 332.重新安排行程 - 51.N皇后 - 37.解数独
491.递增子序列 题目链接:491.递增子序列思路:和子集那道题思路很像,每次在数组中选择一个数,选过的数不能选择,这里要求集合数量必须大于2个才能符合,仍然需要去重,但这里选额的是子序列&…...
多用户商城系统的功能及设计和开发
多用户商城系统的功能及设计与开发(基于 PHP MySQL) 在现代电子商务平台的开发中,PHP MySQL 是一对非常流行且高效的技术栈。PHP作为服务器端脚本语言,结合MySQL数据库,可以高效地处理多用户商城系统的各种需求。本…...
2024年11月8日day8
半加器和全加器的区别 半加器:只能处理两个二进制位的相加,无法处理进位。全加器:不仅能处理两个二进制位的相加,还能处理来自低位的进位。 ⑴ 完成满足754标准存储格式的浮点数((43940000)16的十进制数值)…...
Debezium系列之:Debezium3版本增量快照和只读增量快照应用的变化
Debezium系列之:Debezium3版本增量快照和只读增量快照应用的变化 一、需求背景二、基于数据库信号表使用增量快照案例三、基于Kafka信号Topic使用增量快照案例四、只读增量快照案例五、增量快照技术总结增量快照相关知识请阅读博主下面系列文章: Debezium系列之:实现增量快照…...
Python正则表达式1 re.match惰性匹配详解案例
点个关注 re.match() re.match() 函数尝试从字符串的开头开始匹配一个模式,如果匹配成功,返回一个匹配成功的对象,否则返回None。大小写区分,内容匹配不到后面的,只能匹配一个,不能有空格(开头匹配&#…...
WPF(C#)学习日志10:Prism框架下按键绑定
在Prism框架下,提供了DelegateCommand类用于处理了UI的按键请求,XAML中可以直接采用 Command"{Binding **}" 来绑定这些方法。这个类是一个泛型的类生命时仅需要DelegateCommand<T>即可,同时在XAML中绑定CommandParameter&qu…...
WPF中的ResizeMode
在 WPF (Windows Presentation Foundation) 中,ResizeMode 属性用于指定窗口是否可以被用户调整大小,以及如何调整大小。ResizeMode 属性可以设置为以下几个值之一: NoResize:窗口不能被用户调整大小,但可以被程序代码…...
Unity3D UI 双击和长按
Unity3D 实现 UI 元素双击和长按功能。 UI 双击和长按 上一篇文章实现了拖拽接口,这篇文章来实现 UI 的双击和长按。 双击 创建脚本 UIDoubleClick.cs,创建一个 Image,并把脚本挂载到它身上。 在脚本中,继承 IPointerClickHa…...
LabVIEW扫描探针显微镜系统
开发了一套基于LabVIEW软件开发的扫描探针显微镜系统。该系统专为微观尺度材料的热性能测量而设计,特别适用于纳米材料如石墨烯、碳纳米管等的研究。系统通过LabVIEW编程实现高精度的表面形貌和热性能测量,广泛应用于科研和工业领域。 项目背景 随着纳…...
问题式教学法在生物教学中的应用探索
问题式教学法在生物教学中的应用探索 李新 山东省德州市平原县第五中学 山东 德州 253100 摘要:时代在发展教育事业也在不断进步,不断创新教学方法有利于提高教学质量。问题教学法能让教材知识点以问题的形式呈现在学生眼前,这对引导学生…...
C++ | Leetcode C++题解之第556题下一个更大元素III
题目: 题解: class Solution { public:int nextGreaterElement(int n) {int x n, cnt 1;for (; x > 10 && x / 10 % 10 > x % 10; x / 10) {cnt;}x / 10;if (x 0) {return -1;}int targetDigit x % 10;int x2 n, cnt2 0;for (; x2 …...
实现链式结构二叉树
目录 需要实现的操作 链式结构二叉树实现 结点的创建 前序遍历 中序遍历 后序遍历 计算结点个数 计算二叉树的叶子结点个数 计算二叉树第k层结点个数 计算二叉树的深度 查找值为x的结点 销毁 层序遍历 判断是否为完全二叉树 总结 需要实现的操作 //前序遍历 void …...
在vscode中如何利用git 查看某一个文件的提交记录
在 Visual Studio Code (VSCode) 中,你可以使用内置的 Git 集成来查看某个文件的提交历史。以下是具体步骤: 使用 VSCode 内置 Git 功能 打开项目: 打开你的项目文件夹,确保该项目已经是一个 Git 仓库(即项目根目录下…...
【ShuQiHere】️`adb kill-server` 和 `adb start-server` 命令的作用
📟🔧 【ShuQiHere】️ 🔧📟 在使用 scrcpy 或其他依赖于 ADB(Android Debug Bridge) 的工具时,您可能会遇到需要重启 ADB 服务器的情况。今天,我们将详细解释两个常用的 ADB 命令&a…...
植物明星大乱斗1
能帮到你的话,就给个赞吧 😘 文章目录 scene.hmenuScene.hgameScene.hmainscene.cppmenuScene.cppgameScene.cpp scene.h #pragma once #include <graphics.h>/* 场景菜单角色选择游戏 */ class Scene { public:virtual ~Scene() 0; public:virt…...
信息安全工程师(84)UNIX/Linux操作系统安全分析与防护
前言 UNIX/Linux操作系统,尤其是Linux,以其开放性、稳定性和安全性在服务器、桌面、嵌入式设备和超级计算机中占据重要地位。然而,没有任何操作系统可以百分之百地保证安全,UNIX/Linux也不例外。 一、UNIX/Linux操作系统安全分析 …...
全面解析 Python typing模块与静态类型注解:从基础到高级
在现代软件开发中,代码的可读性、维护性和可靠性至关重要。Python 作为一门动态类型语言,尽管灵活,但也可能带来一些类型上的困扰。Python 的 typing 模块和静态类型注解提供了一种在编写代码时明确类型信息的方法,从而提升代码质…...
Jekins篇(搭建/安装/配置)
目录 一、环境准备 1. Jenkins安装和持续集成环境配置 2. 服务器列表 3. 安装环境 Jekins 环境 4. JDK 环境 5. Maven环境 6. Git环境 方法一:yum安装 二、JenKins 安装 1. JenKins 访问 2. jenkins 初始化配置 三、Jenkins 配置 1. 镜像配置 四、Mave…...
【工具变量】排污权交易政策试点DID(2000-2023)
数据简介:在过去几十年间的“高增长、高能耗、高污染”的经济发展背景下,随着社会各界不断反应高经济增长背后付出的巨大环境代价,中国ZF将节能环保减排纳入长期规划治理中。在2007年,我国开始启动了二氧化硫(SO2&…...
Proteus中数码管动态扫描显示不全(已解决)
文章目录 前言解决方法后记 前言 我是直接把以前写的 51 数码管程序复制过来的,当时看的郭天祥的视频,先送段选,消隐后送位选,最后来个 1ms 的延时。 代码在 Proteus 中数码管静态是可以的,动态显示出了问题——显示…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...
破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
二维FDTD算法仿真
二维FDTD算法仿真,并带完全匹配层,输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...
