22.回溯算法4
递增子序列
这里不能排序,因为数组的顺序是对结果有影响的,所以只能通过used数组来去重
class Solution {
public:vector<int> path;vector<vector<int>> res;void backtracking(vector<int>& nums,int start){if(path.size()>1)res.push_back(path);int used[201]={0};for(int i=start;i<nums.size();i++){if(path.empty()||nums[i]>=path[path.size()-1]){if(used[nums[i]+100])continue;;path.push_back(nums[i]);used[nums[i]+100]=1;backtracking(nums,i+1);path.pop_back();}}}vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums,0);return res;}
};
全排列
class Solution {
public:vector<int> path;vector<vector<int>> res;int* used;int level=0;void backtracking(vector<int>& nums){if(level==nums.size()){res.push_back(path);return;}for(int i=0;i<nums.size();i++){if(used[i])continue;path.push_back(nums[i]);level++;used[i]=1;backtracking(nums);path.pop_back();used[i]=0;level--;}}vector<vector<int>> permute(vector<int>& nums) {used= new int[nums.size()]{0};backtracking(nums);return res;}
};
全排列2
class Solution {
public:vector<int> path;vector<vector<int>> res;int* used;int level=0;void backtracking(vector<int>& nums){if(level==nums.size()){res.push_back(path);return;}int pre=20040503;for(int i=0;i<nums.size();i++){if(used[i])continue;if(nums[i]==pre)continue;path.push_back(nums[i]);level++;used[i]=1;pre=nums[i];backtracking(nums);path.pop_back();used[i]=0;level--;}}vector<vector<int>> permuteUnique(vector<int>& nums) {used= new int[nums.size()]{0};sort(nums.begin(),nums.end());backtracking(nums);return res;}
};
重新安排行程
class Solution {public:unordered_map<string,map<string,int>> targets;vector<string> res; int tiknum;vector<string> backtracking(int stop,string start){if(stop==tiknum)return res;vector<string> tmp;for(auto it:targets[start]){if(it.second){res.push_back(it.first);targets[start][it.first]--;}else continue;tmp=backtracking(stop+1,it.first);if(!tmp.empty())return tmp;res.pop_back();targets[start][it.first]++;}return tmp;}vector<string> findItinerary(vector<vector<string>>& tickets) {for(auto tick:tickets){targets[tick[0]][tick[1]]++;}tiknum=tickets.size();res.push_back("JFK");return backtracking(0,"JFK");}
};
N皇后
class Solution {
public:vector<string> tmp;vector<vector<string>> res;int n;bool isConf(int y,int x){for(int i=1;i<=y;i++){if(tmp[y-i][x]=='Q')return 1;if(x+i<n&&tmp[y-i][x+i]=='Q')return 1;if(x-i>=0&&tmp[y-i][x-i]=='Q')return 1;}return 0;}void backtracking(int k){if(k==n){res.push_back(tmp);}for(int i=0;i<n;i++){if(isConf(k,i))continue;tmp[k][i]='Q';backtracking(k+1);tmp[k][i]='.';}}vector<vector<string>> solveNQueens(int n0) {n=n0;tmp.resize(n);for(int i=0;i<n;i++){tmp[i].resize(n);for(int j=0;j<n;j++){tmp[i][j]='.';}}backtracking(0);return res; }
};
- 时间复杂度: O(n!)
- 空间复杂度: O(n)
解数独
class Solution {
public:bool isValid(int row, int col, char val,vector<vector<char>>& board) {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;
}bool backtracking(int x,int y,vector<vector<char>>& board){int n=board.size();if(x>=n){x=x%n;y++;}while(x<n&&y<n){if(board[y][x]!='.'){x++;if(x>=n){x=x%n;y++;}continue;}for(int i=1;i<10;i++){if(!isValid(y,x,i+'0',board))continue;board[y][x]=i+'0'; if(backtracking(x+1,y,board))return 1;board[y][x]='.';}return 0;}return 1;}void solveSudoku(vector<vector<char>>& board) {backtracking(0,0,board);}
};
相关文章:
22.回溯算法4
递增子序列 这里不能排序,因为数组的顺序是对结果有影响的,所以只能通过used数组来去重 class Solution { public:vector<int> path;vector<vector<int>> res;void backtracking(vector<int>& nums,int start){if(path.si…...
linux -对文件描述符的操作dup、fcntl有五种
dup #include<unistd.h> int dup(int oldfd);作用:复制一个新的文件描述符fd 3, int fd1 dup(fd);f指向的是a.txt,fd1指向的也是a.txt从空闲的文件描述符表中找一个最小的作为新的拷贝的文件描述符返回:成功返回新的文件描述符,失败…...
技术解析 | 适用于TeamCity的Unreal Engine支持插件,提升游戏构建效率
龙智是JetBrains授权合作伙伴、Perforce授权合作伙伴,为您提供TeamCity、Perforce Helix Core等热门的游戏开发工具及一站式服务 TeamCity 是游戏开发的热门选择,大家选择它的原因包括支持 Perforce、可以进行本地安装,并提供了多种配置选项。…...
Ubuntu22.04 - brpc的安装和使用
目录 介绍安装使用 介绍 brpc 是用 c语言编写的工业级 RPC 框架,常用于搜索、存储、机器学习、广告、推荐等高性能系统 安装 先安装依赖 apt-get install -y git g make libssl-dev libprotobuf-dev libprotoc-dev protobuf-compiler libleveldb-dev libgflags-d…...
网络运维学习笔记 018 HCIA-Datacom综合实验02
文章目录 综合实验2sw3:sw4:gw:core1(sw1):core2(sw2):ISP 综合实验2 sw3: vlan 2 stp mode stp int e0/0/1 port link-type trunk port trunk allow-pass v…...
Vulhub靶机 Apache Druid(CVE-2021-25646)(渗透测试详解)
一、开启vulhub环境 docker-compose up -d 启动 docker ps 查看开放的端口 1、漏洞范围 在Druid0.20.0及更低版本中 二、访问靶机IP 8888端口 1、点击Load data进入新界面后,再点击local disk按钮。 2、进入新界面后,在标红框的Base directory栏写上…...
VSCode配置自动生成头文件
一、配置步骤: 1.打开命令面板(CtrlShiftp): 2.输入snippets 选择配置代码片段 3. 选择新建全局代码片段 输入文件名,比如header_cpp(随便定义),然后点击键盘回车按钮,得到下面这个文件。 增加配置文…...
Xcode如何高效的一键重命名某个关键字
1.选中某个需要修改的关键字; 2.右击,选择Refactor->Rename… 然后就会出现如下界面: 此时就可以一键重命名了。 还可以设置快捷键。 1.打开Settings 2.找到Key Bindings 3.搜索rename 4.出现三个,点击一个地方设置后其…...
React 高阶组件的优缺点
React 高阶组件的优缺点 优点 1. 代码复用性高 公共逻辑封装:当多个组件需要实现相同的功能或逻辑时,高阶组件可以将这些逻辑封装起来,避免代码重复。例如,多个组件都需要在挂载时进行数据获取操作,就可以创建一个数…...
(五)趣学设计模式 之 建造者模式!
目录 一、 啥是建造者模式?二、 为什么要用建造者模式?三、 建造者模式怎么实现?四、 建造者模式的应用场景五、 建造者模式的优点和缺点六、 总结 🌟我的其他文章也讲解的比较有趣😁,如果喜欢博主的讲解方…...
香橙派/树莓派 利用Wiring库 使用GPIO模拟PWM
香橙派或者树莓派 等开发板,本身带有硬件PWM,比如香橙派3 lts版,但是这个引脚不符合我的项目需求,我需要外接一个电机,在检测到人脸的时候 转动,但是这个硬件引脚,只要上电就开始输出pwm 信号,导…...
全面收集中间件Exporter适配:从Redis到ActiveMQ,掌握监控数据采集的最佳实践
#作者:任少近 文章目录 说明:一 Redis的适配exporter版1.1 Redis的exporter源码版本1.2 Redis的exporter的releases版1.3 Redis_exporter版本选择理由1.4 Redis_exporter docer镜像 二 Zookeeper的适配exporter版2.1 Zookeeper的exporter源码版本2.2 Zo…...
机器学习数学通关指南——链式法则
前言 本文隶属于专栏《机器学习数学通关指南》,该专栏为笔者原创,引用请注明来源,不足和错误之处请在评论区帮忙指出,谢谢! 本专栏目录结构和参考文献请见《机器学习数学通关指南》 正文 一、定义与公式 链式法则&a…...
JavaScript函数-arguments的使用
在JavaScript编程语言中,函数是构建复杂逻辑和实现代码复用的关键组件。虽然现代JavaScript(尤其是ES6及之后版本)提供了更多灵活的方式来处理函数参数(如剩余参数、默认参数等),但arguments对象仍然是一个…...
千峰React:函数组件使用(2)
前面写了三千字没保存,恨! 批量渲染 function App() {const list [{id:0,text:aaaa},{id:1,text:bbbb},{id:2,text:cccc}]// for (let i 0; i < list.length; i) {// list[i] <li>{list[i]}</li>// }return (<div><…...
DPVS-3: 双臂负载均衡测试
测试拓扑 双臂模式, 使用两个网卡,一个对外,一个对内。 Client host是物理机, RS host都是虚拟机。 LB host是物理机,两个CX5网卡分别在两个子网。 配置文件 用dpvs.conf.sample作为双臂配置文件,其中…...
2016年下半年试题二:论软件设计模式及其应用
论文库链接:系统架构设计师论文 论文题目 软件设计模式(Software DesignPatter)是一套被反复使用的、多数人知晓的、经过分类编目的代码设计经验的总结。使用设计模式是为了重用代码以提高编码效率增加代码的可理解性、保证代码的可靠性。软件设计模式是软件开发中的…...
深入理解 SQL 中的 DATEDIFF 函数
深入理解 SQL 中的 DATEDIFF 函数 DATEDIFF 函数在 SQL 中是一个用于计算两个日期之间差值的重要工具。不同数据库实现了不同版本的 DATEDIFF,它们在功能和语法上有所不同。本文将详细解析 DATEDIFF 的用法、数据库间差异、复杂场景中的应用,以及替代方…...
【第二节】C++设计模式(创建型模式)-抽象工厂模式
目录 引言 一、抽象工厂模式概述 二、抽象工厂模式的应用 三、抽象工厂模式的适用场景 四、抽象工厂模式的优缺点 五、总结 引言 抽象工厂设计模式是一种创建型设计模式,旨在解决一系列相互依赖对象的创建问题。它与工厂方法模式密切相关,但在应用…...
【学习资料】嵌入式人工智能Embedded AI
图片来源: Embedded Artificial Intelligence for Business Purposes | DAC.digital 随着AI在设备端的应用,我们看到越来越多的可穿戴设备出现以及自动驾驶汽车的发展,可以看到嵌入式人工智能是新的发展方向。我为大家介绍嵌入式人工智能的…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
