【算法训练记录——Day28】

Day28——回溯算法Ⅳ

  • 1.复原IP地址
  • 2.[全排列](https://leetcode.cn/problems/permutations/submissions/539240290/)
  • 3.[全排列Ⅱ](https://leetcode.cn/problems/permutations-ii/description/)

● 93.复原IP地址
● 78.子集
● 90.子集II

1.复原IP地址

在这里插入图片描述
思路:相当于还是求所有子集,只是在这个基础上加了层判断

	vector<string> res;bool isValid(const string& s, int start, int end) {if(start > end) return false;	// 越界无效if(start != end && s[start] == '0') return false; // 初0以外首字符为0无效int num = 0;for(int i = start; i <= end; i++) {if(s[i] > '9' || s[i] < '0') return false;num = num * 10 + s[i] - '0';if(num > 255) return false;}return true;}void backtracking(string& s, int startIndex, int pointNum) {if(pointNum == 3) {if(isValid(s, startIndex, s.size() - 1)) {res.push_back(s);}return;}for(int i = startIndex; i < s.size(); i++) {if(isValid(s, startIndex, i)) {s.insert(s.begin() + i + 1, '.');		// 有效ip后面加上.backtracking(s, i + 2, pointNum + 1);	// 回溯 左闭右闭s.erase(s.begin() + i + 1);				// 回溯,删掉加上的.} else return;								// 无效ip直接剪枝}return;}vector<string> restoreIpAddresses(string s) {res.clear();if(s.size() < 4 || s.size() > 12) return res; // 剪枝backtracking(s, 0, 0);return res;}

2.全排列

在这里插入图片描述
思路:刚开始认为把startIndex换成0不就是遍历全部了,但是写了一下发现,换成0 递归的逻辑应该是什么呢,从下一个开始,然后每次遍历全部元素,那不就有很多重复的?怎么过滤呢?卡住了,不会了。
用used数组标记当前已使用元素。

	vector<int> num;vector<bool> used;vector<vector<int>> res;void backtracking(const vector<int>& nums) {if(num.size() >= nums.size()) {res.push_back(num);return;}for(int i = 0; i < nums.size(); i++) {if(used[i] == true) continue;used[i] = true;num.push_back(nums[i]);backtracking(nums);num.pop_back();used[i] = false;}return;}vector<vector<int>> permute(vector<int>& nums) {used.resize(nums.size());backtracking();return res;}

3.全排列Ⅱ

在这里插入图片描述
思路:可包含重复元素。好熟悉,但是想不起来了。。应该是要排序,然后跳过一些重复元素。

void backtracking(const vector<int>& nums) {if(num.size() >= nums.size()) {res.push_back(num);return;}for(int i = 0; i < nums.size(); i++) {// 此处有疑问if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false) continue;if(used[i] == true) continue;used[i] = true;num.push_back(nums[i]);backtracking(nums);used[i] = false;num.pop_back();}return;}vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());used.resize(nums.size(), false);backtracking(nums);return res;}

在写这段代码时,考虑到需要对重复字符的控制 写成了这种

 if(i > 0 && nums[i] == nums[i-1]) continue;

按照我的想法,当 i>0 时,表示当前已经进行了一次回溯,开始遍历下一个元素,此时如果当前元素和前一元素相同,那么本次以当前元素为根的回溯就是不必要的,因为已经有相同元素进行了一次回溯。,这两次的结果应该是相同的。但是突然想到每次回溯时,这个代码也会运行,所以需要再加限制,保证在开始回溯时就剪枝。代码中在每次回溯前都把used[i] = true,因此当 used[i] == false时,即表示本次不是处于递归之中。但写代码的时候把 == false 写成了 == true,结果也能运行,但是没明白为什么。

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

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

相关文章

SSM情侣购物系统 -计算机毕业设计源码02387

目 录 摘要 1 绪论 1.1 开发背景与意义 1.2开发意义 1.3Vue.js 主要功能 1.3论文结构与章节安排 2 情侣购物系统系统分析 2.1 可行性分析 2.2 系统流程分析 2.2.1 数据流程 3.3.2 业务流程 2.3 系统功能分析 2.3.1 功能性分析 2.3.2 非功能性分析 2.4 系统用例分…

细说MCU串口函数及使用printf函数实现串口发送数据的方法

目录 1、硬件及工程 2、串口相关的库函数 &#xff08;1&#xff09;串口中断服务函数&#xff1a; &#xff08;2&#xff09;串口接收回调函数&#xff1a; &#xff08;3&#xff09;串口接收中断配置函数&#xff1a; &#xff08;4&#xff09;非中断发送&#xff…

[linux]如何跟踪linux 内核运行的流程呢

前面已经可以把内核编译出来&#xff0c;但是作为技术狗想看到内核是怎么运行的怎么办&#xff1f; 内核很多代码都是C语言写的&#xff0c;那简单&#xff0c;添加2行代码&#xff1a; include/linux/printk.h 529和530原来的&#xff1a; #define pr_info(fmt, ...) \ …

IIoT(智能物联网)的现状、应用及安全

近年来&#xff0c;物联网&#xff08;IoT&#xff09;作为推动现代公司和智能城市发展的一个范式&#xff0c;已经取得了显著的发展。IoT使得分布式设备&#xff08;如手机、平板电脑和计算机&#xff09;能够感知并从外部环境传输数据&#xff0c;以服务于最终用户。IoT的概念…

TcpClient 服务器、客户端连接

TcpClient 服务器 TcpListener 搭建tcp服务器的类&#xff0c;基于socket套接字通信的 1 创建服务器对象 TcpListener server new TcpListener(IPAddress.Parse("127.0.0.1"), 3000); 2 开启服务器 设置最大连接数 server.Start(1000); 3 接收客户端的链接,只能…

华为昇腾异构计算架构CANN及AI芯片简介

异构计算架构CANN 异构计算架构CANN&#xff08;Compute Architecture for Neural Networks&#xff09;是华为针对AI场景推出的异构计算架构&#xff0c;向上支持多种AI框架&#xff0c;包括MindSpore、PyTorch、TensorFlow等&#xff0c;向下服务AI处理器与编程&#xff0c;…

Open vSwitch 中 upcall 消息的类型

一、upcall 调用的流程 在 Open vSwitch 的数据包转发流程中&#xff0c;如果数据包在内核空间无法完全处理&#xff08;比如匹配不到流表项&#xff09;&#xff0c;就会发生 upcall 调用&#xff0c;将数据包从内核空间的 Datapath 模块传输至用户空间的 ovs-vswitchd 守护进…

UML类图之间的关系与对应的代码关系

UML类图之间的关系与对应的代码关系 1. 依赖关系1.1 图解1.2代码实现 2. 关联关系2.1图解2.2代码实现 3. 聚合关系3.1图解3.2代码实现 4. 组合关系4.1图解4.2代码实现 5. 泛化关系5.1图解5.2代码实现 6. 实现关系6.1图解6.2代码实现 在UML中&#xff0c;共有四种关系&#xff1…

Docker与Docker-Compose详解

1、Docker是什么&#xff1f; 在计算机中&#xff0c;虚拟化(英语: Virtualization) 是一种资源管理技术&#xff0c;是将计算机的各种实体资源&#xff0c;如服务器、网络、内存及存储等&#xff0c;予以抽象、转换后呈现出来&#xff0c;打破实体结构间的不可切割的障碍&…

学习笔记——路由网络基础——缺省(默认)路由

3、缺省(默认)路由 1、定义 缺省路由(默认路由)&#xff1a;是目的地址和掩码都为全0的特殊路由。全0代表任意网络。缺省路由在路由表中的形式为&#xff1a;0.0.0.0/0缺省路由也被叫默认路由。缺省路由优先级比直连路由低 缺省路由是一种特殊的路由&#xff0c;当报文没有在…

API工具--Apifox和Postman对比(区别)

&#x1f525; 交流讨论&#xff1a;欢迎加入我们一起学习&#xff01; &#x1f525; 资源分享&#xff1a;耗时200小时精选的「软件测试」资料包 &#x1f525; 教程推荐&#xff1a;火遍全网的《软件测试》教程 &#x1f4e2;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1…

【SkiaSharp绘图03】SKPaint详解(一)BlendMode混合模式、ColorFilter颜色滤镜

文章目录 SKPaintSKPaint属性BlendMode获取或设置混合模式SKBlendMode 枚举成员效果预览 Color/ColorF获取或设置前景色ColorFilter 颜色滤镜CreateBlendMode 混合模式CreateColorMatrix 颜色转换CreateCompose 组合滤镜CreateHighContrast 高对比度滤镜CreateLighting 照明滤镜…

eNSP学习——配置高级的访问控制列表

目录 主要命令 原理概述 实验目的 实验内容 实验拓扑 实验编址 实验步骤 1、基本配置 2、搭建OSPF网络 3、配置Telnet 4、配置高级ACL控制访问 需要eNSP各种配置命令的点击链接自取&#xff1a;华为&#xff45;NSP各种设备配置命令大全PDF版_ensp配置命令大全资源-…

AcWing 477:神经网络 ← 拓扑排序+链式前向星

【题目来源】https://www.acwing.com/problem/content/479/【题目描述】 人工神经网络&#xff08;Artificial Neural Network&#xff09;是一种新兴的具有自我学习能力的计算系统&#xff0c;在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。 对神经网络的研究…

致 粉丝de信

致 粉丝 -本文呢看不下去别看&#xff0c;但是学业是真的重要&#xff08;平常有信奥&#x1f62b;&#xff09;&#xff0c;电脑没收……更新可能得到暑假&#xff0c; 同学&#xff1a;小没苯agoe &#xff08;aaa&#xff0c;学霸&#xff01;&#xff01;&#xff01;&…

排序-快排算法对数组进行排序

目录 一、问题描述 二、解题思路 1.初始化 2.将右侧小于基准元素移到左边 3.将左侧大于基准元素移到右边 4.重复执行上面的操作 5.对分好的左、右分区再次执行分区操作 6.最终排序结果 三、代码实现 四、刷题链接 一、问题描述 二、解题思路 快排算法实现数组排序&am…

【Spring EL<二>✈️✈️ 】SL 表达式结合 AOP 注解实现鉴权

目录 &#x1f37b;前言 &#x1f378;一、鉴权&#xff08;Authorization&#xff09; &#x1f37a;二、功能实现 2.1 环境准备 2.2 代码实现 2.3 测试接口 &#x1f379;三、测试功能 3.1 传递 admin 请求 ​ 3.2 传递普通 user 请求 &#x1f37b;四、章末 &a…

【智能算法应用】基于混合粒子群-蚁群算法的多机器人多点送餐路径规划问题

目录 1.算法原理2.数学模型3.结果展示4.参考文献5.代码获取 1.算法原理 【智能算法】粒子群算法&#xff08;PSO&#xff09;原理及实现 配餐顺序&#xff1a; 采用混合粒子群算法 || 路径规划&#xff1a; 采用蚁群算法 2.数学模型 餐厅送餐多机器人多点配送路径规划&…

美创科技入选“2024网络安全提供商创新排行榜”

近日&#xff0c;DBC德本咨询公布了“2024网络安全提供商创新排行榜”&#xff0c;美创科技凭借近20年的数据安全创新耕耘&#xff0c;荣誉上榜。 此次&#xff0c;与360、华为、腾讯等互联网、网络安全头部厂商并肩上榜&#xff0c;是行业对美创的再次认可。 数据安全的发展离…

景芯SoC A72的时钟树分析

innovus的ctslog中的Clock DAG信息可以报出来CTS主要运行步骤的关键信息&#xff0c;比如clustering&#xff0c;balancing做完后的clock tree的长度&#xff0c;clock tree上所用的buffer、inverter&#xff0c;icg cell数量&#xff0c;clock skew等信息。我们以景芯SoC A72 …