代码随想录第28天|回溯算法

491. 非递减子序列

在这里插入图片描述
思路:

  • 不可以排序, 否则会改变元素的顺序
  • 对收获的结果有要求, num.size() >= 2, 且 num[i - 1] < num[i]
  • 需要进行去重, 不能使用排序后的方法去重
  • 每一层可用 unordered_set 去重
  • 组合问题, for 遍历需要标记起始位置

bug:

  • 一定要先判断元素是否重复, 再将元素插入
    请添加图片描述
//正确步骤
if (used.find(nums[i]) != used.end()) {continue;
} else if (res_tem.empty()) { // 重复元素res_tem.push_back(nums[i]);
} else if (res_tem.back() > nums[i]) { // 非递增continue;
} else {res_tem.push_back(nums[i]);
}//错误步骤
//当res_tem为空时, 会将重复元素也添加, 一定需要先判断元素是否有使用
if (res_tem.size() == 0) { res_tem.push_back(nums[i]);
} else if (used.find(nums[i]) != used.end()) { //重复元素continue;
} else if (!(res_tem.back() <= nums[i])) {  //非递增continue;
} else {res_tem.push_back(nums[i]);
}
class Solution {
public:vector<vector<int>> res;vector<int> res_tem;void myoperator(vector<int>& nums, int index) {if (res_tem.size() >= 2) {res.push_back(res_tem);}unordered_set<int> used;for (int i = index; i < nums.size(); i++) {if (used.find(nums[i]) != used.end()) {continue;} else if (res_tem.empty()) { // 重复元素res_tem.push_back(nums[i]);} else if (res_tem.back() > nums[i]) { // 非递增continue;} else {res_tem.push_back(nums[i]);}// 等效操作// if (!res_tem.empty() && nums[i] < res_tem.back()) {//     continue;// }// if (used.find(nums[i]) != used.end()) {//     continue;// }// res_tem.push_back(nums[i]);used.insert(nums[i]);myoperator(nums, i + 1);res_tem.pop_back();}}vector<vector<int>> findSubsequences(vector<int>& nums) {myoperator(nums, 0);return res;}
};

46.全排列

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
在这里插入图片描述
思路:

  • 不能使用index来跳过元素, 因为与顺序有关, 所以遍历从 i = 0 开始
  • 每个元素都要遍历, 可以使用 used 数组去重
  • 无法用 unordered_set 去重, 每层树枝都有相互关联, 不是去除重复数字操作

请添加图片描述

class Solution {
public:vector<vector<int>> res;vector<int> res_tem;vector<bool> uesed;void myoperator(vector<int>& nums) {if (res_tem.size() == nums.size()) {res.push_back(res_tem);return;}for (int i = 0; i < nums.size(); i++) {if (uesed[i] == true) {continue;}uesed[i] = true;res_tem.push_back(nums[i]);myoperator(nums);uesed[i] = false;res_tem.pop_back();}}vector<vector<int>> permute(vector<int>& nums) {uesed = vector<bool>(nums.size(), 0);myoperator(nums);return res;}
};

47. 全排列 II

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列
在这里插入图片描述
请添加图片描述
思路:

  • 取叶子节点, 中间需要去除, 相同数层之间不能用同样的数值
  • 排列则需要从0开始, 使用used标记使用过的元素
class Solution {
public:vector<vector<int>> res;vector<int> res_tem;vector<bool> flag;void myoperator(vector<int>& nums) {if (res_tem.size() == nums.size()) {res.push_back(res_tem);return;}unordered_set<int> used;for (int i = 0; i < nums.size(); i++) {if (used.find(nums[i]) != used.end()) {continue;}if (flag[i] == true) {continue;}flag[i] = true;used.insert(nums[i]);res_tem.push_back(nums[i]);myoperator(nums);flag[i] = false;res_tem.pop_back();}}vector<vector<int>> permuteUnique(vector<int>& nums) {flag = vector<bool>(nums.size(), false);myoperator(nums);return res;}
};

51. N 皇后
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
在这里插入图片描述
参考
请添加图片描述


37. 解数独
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
参考
请添加图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/353914.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

RabbitMQ实践——在Ubuntu上安装并启用管理后台

大纲 环境安装启动管理后台 RabbitMQ是一款功能强大、灵活可靠的消息代理软件&#xff0c;为分布式系统中的通信问题提供了优秀的解决方案。无论是在大规模数据处理、实时分析还是微服务架构中&#xff0c;RabbitMQ都能发挥出色的性能&#xff0c;帮助开发者构建高效、稳定的系…

Microsoft AI Day:支持开放合作,普及技术应用,推进行业企业智慧化创新

微软在北京举办以“共创AI创新&#xff0c;智启无限可能”为主题的Microsoft AI Day活动&#xff0c;集中展示了在生成式智能技术加速发展普及的过程中&#xff0c;微软取得的最新技术突破与进展&#xff0c;并同步更新了在Microsoft Build 2024全球开发者大会上发布的一系列Az…

基于Java的高校校园点餐系统

开头语&#xff1a; 你好&#xff0c;我是计算机专业的学长&#xff0c;如果你对高校校园点餐系统感兴趣或有相关开发需求&#xff0c;欢迎联系我。 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;JSP技术 工具&#xff1a;Eclipse、Tomcat 系统展示…

安享智慧理财金融测试项目

1. 项目介绍 安享智慧理财金融系统是基于 Java 语言开发&#xff0c;集 PC 端、APP 端、WAP 端为一体的 P2P&#xff08;个人对个人&#xff09;的借贷系统&#xff0c;提供了完整的借款和投资功能。 web用户端 说明&#xff1a;PC 网站&#xff0c;供借款人和投资人使用功能…

PySide(PyQt)的特殊按钮(互锁、自锁、独占模式)

界面图: Qt Designer中创建窗口,放置一个QGroupBox,命名为btnStation,这就是自定义的按钮站,按钮站里放置6个按钮。自锁按钮相当于电器中的自锁功能的按钮,每按一次状态反转并保持不变。独占按钮也是自锁功能的按钮,不同的是当独占按钮为ON时,其余所有按钮均被置为OFF…

大模型“诸神之战”,落地才是赛点

ChatGPT 诞生已经快一年&#xff0c;你还在与它对话吗&#xff1f; 有的人用来写报告、改代码&#xff0c;让它成为得力帮手&#xff1b;有的人却只是“调戏”个两三回&#xff0c;让它创作诗歌或故事&#xff0c;便不再“宠幸”。 根据网站分析工具 SimilarWeb 的数据&#…

基于VSCode和MinGW-w64搭建LVGL模拟开发环境

目录 概述 1 运行环境 1.1 版本信息 1.2 软件安装 1.2.1 下载安装VS Code 1.2.1.1 下载软件 1.2.1.1 安装软件 1.2.2 下载安装MinGW-w64 1.2.2.1 下载软件 1.2.2.2 安装软件 1.2.3 下载安装SDL 1.2.3.1 下载软件 ​1.2.3.2 安装软件 1.2.4 下载安装CMake 1.2.4.…

c#音乐播放器续(联网下载)

音乐播放器 0.前言1.关于本地音乐播放2.使用iTunes Search API进行联网下载歌曲2.1 控件2.2 函数实现2.2.1 控件2&#xff1a;搜索歌曲2.2.2 控件3&#xff1a;下载歌曲 2.3 主界面 3.拓展 0.前言 书接上文&#xff0c;我们已经实现了一个能够播放本地音乐的音乐播放器&#x…

计算机专业毕设-在线商城系统

1 项目介绍 在线商城系统&#xff0c;后端java语言&#xff0c;springboot&#xff0c;SSM框架。前端thymeleaf&#xff0c;前后端不分离。本项目已经隐去作者信息&#xff0c;所有代码文件均没有创建人和创建时间&#xff0c;可以放心使用。 系统用户分为两类&#xff0c;管理…

Spring-JdbcTemplate

了解知道即可 JdbcTemplate环境配置 先加入依赖&#xff1a; 在pom.xml中要引入spring和mysql的依赖&#xff1a; <!--仓库和依赖--><repositories><repository><id>spring-milestones</id><name>Spring Milestones</name><ur…

逻辑蕴含、函数依赖集的闭包、Armstrong公理、属性集闭包

一、引言 Armstrong公理-从给定的函数依赖集得到关系模式的完整依赖集 二、逻辑蕴含 1、定义 设F是关系模式R上的函数依赖集&#xff0c;X、Y是R的属性子集&#xff0c;对于R的每个满足F的关系实例r&#xff0c;若函数 依赖都成立&#xff0c;则称F逻辑蕴含。 记为&#…

2021 hnust 湖科大 C语言课程设计报告+代码+流程图源文件+指导书

2021 hnust 湖科大 C语言课程设计报告代码流程图源文件指导书 目录 报告 下载链接 https://pan.baidu.com/s/14NFsDbT3iS-a-_7l0N5Ulg?pwd1111

LUA移植到STM32F4,移植REPL,通过RTT Viewer交互

概述 站内移植LUA多数是使用C函数调用LUA&#xff0c;并没有移植REPL交互端口 本文将REPL也移植进去&#xff0c;做了简单的适配 LUA源码使用标准C库函数&#xff0c;如fgets&#xff0c;fwrite等&#xff0c;在嵌入式环境中要使用fgets&#xff0c;fwrite等C库函数&#xff…

用c语言实现通讯录

目录 静态简易通讯录 代码&#xff1a; 功能模块展示&#xff1a; 设计思路&#xff1a; 动态简易通讯录&#xff08;本质顺序表&#xff09; 代码&#xff1a; 扩容模块展示&#xff1a; 设计思路&#xff1a; 文件版本通讯录 代码&#xff1a; 文件模块展示&#x…

JAVA开发 PDF文件生成表格,表格根据内容自动调整高度

1、展示效果 2、相关功能实现 JAVA开发 使用Apache PDFBox库生成PDF文件&#xff0c;绘制表格 3、实现代码 import org.apache.pdfbox.pdmodel.PDDocument; import org.apache.pdfbox.pdmodel.PDPage; import org.apache.pdfbox.pdmodel.PDPageContentStream; import org.ap…

傲星一个在线工具箱源码附搭建教程

傲星工具箱源码是一款功能强大的在线工具箱程序&#xff0c;您可以通过安装扩展来增强其功能。同时&#xff0c;该程序还提供了插件模板的功能&#xff0c;让您可以将其作为网页导航使用。 1.PHP版本需不低于7.2.5。 2.Mysql版本需不低于5.7。 3.需要安装fileinfo扩展。 4.…

Python | 使用Matplotlib生成子图的示例

数据可视化在分析和解释数据的过程中起着举足轻重的作用。Python中的Matplotlib库提供了一个强大的工具包&#xff0c;用于制作各种图表和图表。一个突出的功能是它能够在单个图中生成子图&#xff0c;为以组织良好和结构化的方式呈现数据提供了有价值的工具。使用子图可以同时…

北京崇文门中医医院贾英才:中医传承的践行者

贾英才&#xff0c;一位在北京崇文门中医医院出诊的杰出中医执业医师&#xff0c;在中医领域深耕近三十载&#xff0c;以其精湛的医术和独特的诊疗验方体系&#xff0c;赢得了广大患者的信赖与认可。 贾英才自幼便深受家学熏陶&#xff0c;中医的种子早早在他心中扎根。成长于中…

2024 年 Python 基于 Kimi 智能助手 Moonshot Ai 模型搭建微信机器人(更新中)

注册 Kimi 开放平台 Kimi&#xff1a;https://www.moonshot.cn/ Kimi智能助手是北京月之暗面科技有限公司&#xff08;Moonshot AI&#xff09;于2023年10月9日推出的一款人工智能助手&#xff0c;主要为用户提供高效、便捷的信息服务。它具备多项强大功能&#xff0c;包括多…

深入理解计算机系统 CSAPP 家庭作业6.35

第一步先求(S,E,B,m) 题目说共C128个字节,块大小B为16个字节,那就是分为八组:0,1,2,3,4,5,6,7.然后每组存4个int 每个4字节 CB*E*S .B16 ,直接映射的E就是1,所以S8 (S,E,B,m)(8,1,16,7) C128M128s3b4t0 sizeof(int)0100地址(二进制)COCIsrc[0][0]00000000000000组0src[0][1…