【算法训练 day30 复原IP地址、子集、子集Ⅱ】

目录

  • 一、复原IP地址-LeetCode 93
    • 思路
    • 实现代码
    • 个人问题
    • 总结
  • 二、子集-LeetCode 78
    • 思路
    • 实现代码
    • 个人问题
  • 三.子集Ⅱ-LeeCode 90
    • 思路
    • 实现代码
    • 个人问题


一、复原IP地址-LeetCode 93

Leecode链接: leetcode 93
文章链接: 代码随想录
视频链接: B站

有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 ‘.’ 分隔。

例如:“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址,但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。

给定一个只包含数字的字符串 s ,用以表示一个 IP 地址,返回所有可能的有效 IP 地址,这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例:

输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]

思路

这道题是一个分割问题,可以用回溯穷举出所有结果。主要分为三个部分:切割ip段、验证ip段是否合法、插入结果到res中。ip切割这里不是使用substr函数,只需要使用insert成员函数即可,因为结果只需要一个完整的ip段,而不是一段一段。验证ip写一个自定义函数即可,插入结果到res这一步使用index来判断已经不适用了,因为ip有四个段,所以判断依据只需要改为是否使用了三个点即可。

实现代码

//cpp
class Solution {
public:vector<string>res;bool isvalid(const string& s,int begin,int end){if(begin > end) return false;if(s[begin] == '0' && begin != end) return false;int num = 0;for(int i = begin;i<=end;i++){if(s[i]<'0' || s[i]>'9') return false;num = num*10+(s[i]-'0');if(num>255) return false;}return true;}void restor(int pointnum,string&s,int index){if(pointnum==3){if(isvalid(s,index,s.size()-1)){res.push_back(s);}return;}for(int i = index;i<s.size();i++){if(isvalid(s,index,i)){pointnum++;s.insert(s.begin()+i+1,'.');restor(pointnum,s,i+2);pointnum--;s.erase(s.begin()+i+1);}else{break;}}}vector<string> restoreIpAddresses(string s) {res.clear();restor(0,s,0);return res;}
};

个人问题

没有想到怎么在字符串中插入字符’.',对insert用的比较少。

总结

难度中等,与分割回文串那题类似,需要注意的点有:插入结果的条件不再依靠index,而是依据段数;递归时不能传入i+1,因为插入字符后,前面的字符都往后移动一位;插入结果时需要对最后一段进行额外的一次判断,因为会有这种情况:192.168.1.399,这显然是不对的。


二、子集-LeetCode 78

Leecode链接: LeetCode 78
文章链接: 代码随想录
视频链接: B站

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的
子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例:

输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

思路

题目与求组和类似,但有一个地方不同,在插入数据到res中时,组合需要进行一个判定,而子集不需要进行判断,每次进入一层递归就将结果插入到res中。至于为什么不需要判断,因为题目要求所有子集,任意一个数或者他们的组合都是子集,也就不要条件判断。

实现代码

//cpp
class Solution {
public:vector<vector<int>>res;vector<int>path;void sub(vector<int>& nums,int index){res.push_back(path);for(int i = index;i<nums.size();i++){path.push_back(nums[i]);sub(nums,i+1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {res.clear();path.clear();sub(nums,0);return res;}
};

个人问题

无。


三.子集Ⅱ-LeeCode 90

Leecode链接: LeetCode 90
文章链接: 代码随想录
视频链接: B站

给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的
子集(幂集)。

解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。

示例:

输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]

思路

题目有重复元素,需要去重,不能包含重复的子集。解题思路与与组合总和Ⅱ类似。个人没有使用数组来判断是否使用相同的元素,感觉这样比较方便。

实现代码

//cpp
class Solution {
public:vector<int>path;vector<vector<int>>res;void sub(int index,vector<int>& nums){res.push_back(path);for(int i = index;i<nums.size();i++){if(i>index && nums[i] == nums[i - 1]){continue;}path.push_back(nums[i]);sub(i+1,nums);path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {res.clear();path.clear();sort(nums.begin(),nums.end());sub(0,nums);return res;}
};

个人问题

无。

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

沉钒废水回收钒

沉钒废水处理与钒回收的重要性 沉钒废水是含钒元素的特殊废水&#xff0c;钒在工业生产中广泛应用&#xff0c;但其排放造成资源浪费与环境威胁。为实现钒的有效回收&#xff0c;研究和实践了多种处理技术。 沉钒废水处理技术 1. 化学沉淀法&#xff1a;添加沉淀剂&#xff…

【Linux】linux | 配置系统日志 | 安全日志 | 操作日志 | 登录日志

一、诉求 1、linux服务器开启日志功能&#xff0c;并记录10个月的登录 二、操作 1、进入目录 cd /etc 2、编辑配置 vi logrotate.conf 3、复制配置 /var/log/wtmp {monthlycreate 0664 root utmpminsize 1Mrotate 10 }/var/log/btmp {missingokmonthlycreate 0600 root …

【动态规划】子序列问题II|最长定差子序列|最长的斐波那契数列的长度|最长等差数列|等差数列的划分

一、最长定差子序列 1218. 最长定差子序列 算法原理&#xff1a; &#x1f4a1;细节&#xff1a; 1.正常创建dp表&#xff0c;分析状态转移方程&#xff1a;可能b存在于多个不同的位置&#xff0c;那么要用哪个下标的dp呢&#xff1f; 用最后一个b的&#xff0c;因为用前面的可…

C++ 将字符串解析为argc、argv

文章目录 前言一、如何实现&#xff1f;1、实现split2、split双引号3、奇数下标元素加入结果4、偶数下标元素split空格 二、完整代码三、使用示例1、解析命令行2、构造argc、argv 总结 前言 一般开启子进程的时候&#xff0c;需要传参数&#xff0c;通常直接传输命令行字符串&…

怎么做微信在线预约

在快节奏的现代生活中&#xff0c;我们总是追求更高效、更便捷的服务体验。而微信&#xff0c;这个拥有数亿用户的社交平台&#xff0c;早已不仅仅是一个聊天工具&#xff0c;它更是一个融合了多种功能的综合性服务平台。今天&#xff0c;就让我们一起探讨如何通过微信在线预约…

软考--试题六--中介者模式(Mediator)

中介者模式(Meditor) 意图 用一个中介对象来封装一系列的对象交互。中介者使各对象不需要显式地相互引用&#xff0c;从而使其耦合松散&#xff0c;而且可以独立地改变它们之间的交互 结构 适用性 1、一组对象以定义良好但是复杂的方式进行通信&#xff0c;产生的相互依赖关…

机房、配电室可视化运维这么卷?不搞3D,出门没法打招呼。

机房和配电室的可视化运维确实可以非常复杂和卷。通过使用3D技术&#xff0c;可以更加直观地展示机房和配电室的布局、设备分布和运行状态。 以下是一些与机房和配电室可视化运维相关的关键点&#xff1a; 3D建模&#xff1a;使用计算机图形学和3D建模软件&#xff0c;可以创建…

亚马逊测评真人号与自养号:如何选择?区别与作用全面解析

亚马逊卖家都希望能打造出热销产品的产品列表&#xff0c;因为评论对于列表的曝光和流量有着巨大的影响。然而&#xff0c;获取有效的产品评论并不容易&#xff0c;许多卖家为了提高自己产品在同类别中的竞争力&#xff0c;选择进行测评。测评可以快速提高产品的排名、权重和销…

AGV小车有什么优点?后期将在各行业逐渐取代人工物料搬运

AGV 随着工厂自动化、计算机集成制造系统技术的逐步发展、及柔性制造系统、自动化立体仓库的广泛应用&#xff0c;AGV作为连接和调节离散型物流管理系统使作业连续化的必要自动化搬运装卸手段&#xff0c;其应用范围和技术水平有了更为迅猛的发展。 AGV立体仓库 随着AGV自动化技…

WebGL软件的开发框架

WebGL&#xff08;Web Graphics Library&#xff09;是一种用于在网页浏览器中实现3D图形渲染的JavaScript API。它允许开发者利用图形处理单元&#xff08;GPU&#xff09;来实时渲染复杂的3D场景&#xff0c;从而创建出令人惊叹的交互式体验。在WebGL开发中&#xff0c;有一些…

记PLSQL链接Oracle数据库

一、环境 Windows环境安装plsql工具 Oracle部署在服务器上面。 由于我之前在本地Windows安装了一个Oracle数据库&#xff0c;结果导致之前已经在连接的PLSQL链接不上。 二、操作 PLSQL工具正常安装&#xff0c;主要就是一些Oracle的一些配置&#xff0c;和oracle客户端。 o…

农林科学SCI期刊,IF=6+,影响力高,对国人非常友好!

一、期刊名称 Crop Journal 二、期刊简介概况 期刊类型&#xff1a;SCI 学科领域&#xff1a;农林科学 影响因子&#xff1a;6.6 中科院分区&#xff1a;1区 出版方式&#xff1a;开放出版 版面费&#xff1a;$900 三、期刊征稿范围 《作物杂志》是一份双月刊、国际、同…

Pikachu 靶场敏感信息泄露通关解析

前言 Pikachu靶场是一种常见的网络安全训练平台&#xff0c;用于模拟真实世界中的网络攻击和防御场景。它提供了一系列的实验室环境&#xff0c;供安全专业人士、学生和爱好者练习和测试他们的技能。 Pikachu靶场的目的是帮助用户了解和掌握网络攻击的原理和技术&#xff0c;…

RTMP低延迟推流

人总是需要压力才能进步, 最近有个项目, 需要我在RK3568上, 推流到公网, 最大程度的降低延迟. 废话不多说, 先直接看效果: 数据经过WiFi发送到Inenter的SRS服务器, 再通过网页拉流的. 因为是打金任务, 所以逼了自己一把, 把RTMP推流好好捋一遍. 先说说任务目标, 首先是MPP编码…

Docker部署nacos集群

前提&#xff1a; 购买一台服务器 虚拟机也行 &#xff0c;无论是哪一个内存都要足够 阿里&#xff1a;https://ecs-buy.aliyun.com/ecs?spm5176.8789780.J_4267641240.2.1e7e39fbopfoRn#/custom/prepay/cn-hangzhou 腾讯 、华为。。。。我目前只使用过这三个。 下载 Xshell …

第十节:Vue指令:v-for列表循环

1. 数组的循环 用 v-for 指令根据一组数组的选项列表进行渲染。 1.1 通过索引渲染数组内容 通过数组的索引获取数组的数据 <div id"app"><ul><li>{{ fruites[0] }}</li><li>{{ fruites[1] }}</li><li>{{ fruites[2] …

Spring:了解@Import注解的三种用法

一、前言 在 Spring 框架中&#xff0c;Import 注解用于导入配置类&#xff0c;使得你可以在一个配置类中引入另一个或多个配置类&#xff0c;从而实现配置的模块化。这对于组织大型应用程序的配置非常有用&#xff0c;因为它允许你将配置分散到多个类中&#xff0c;然后再将它…

C语言如何创建⼀个动态链表?

一、问题 创建动态链表就是指在程序执⾏过程中&#xff0c;从⽆到有&#xff0c;按照需求开辟结点和输⼊各结点数据&#xff0c;并建⽴起前后相连接的关系。那么&#xff0c;如何创建动态链表呢&#xff1f; 二、解答 以建⽴⼀个有任意名学⽣数据的单向动态链表为例&#xff0…

好用的Tipard 蓝光转换器 (Tipard Blu-ray Converter) mac&win

Tipard Blu-ray Converter 是一款令人惊叹的蓝光解决方案软件&#xff0c;可将蓝光光盘/文件夹转换为 1:1 质量的数字格式&#xff0c;速度提高 30 倍&#xff0c;用于 4K UHD 和 1080p 高清视频。它可以将蓝光光盘和文件夹中的蓝光电影转换为MKV、MP4、WMV、MOV、AVI、FLV、VO…

0.98T优于10米高程DEM数据

我们在《全球30米100%水陆覆盖高程》一文中&#xff0c;为大家分享了全球100%覆盖&#xff0c;且包括海底高程的30米DEM数据。 该数据虽然全球无死角覆盖&#xff0c;但分辨率只有30米。 这里&#xff0c;再为大家分享一个优于10米的高程数据&#xff0c;但目前仅覆盖全国范围…