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在设备端的应用,我们看到越来越多的可穿戴设备出现以及自动驾驶汽车的发展,可以看到嵌入式人工智能是新的发展方向。我为大家介绍嵌入式人工智能的…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台
🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...
