当前位置: 首页 > news >正文

算法训练第二十三天|93. 复原 IP 地址 78. 子集 90. 子集 II

93. 复原 IP 地址--分割

题目

有效 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 中的任何数字。你可以按 任何 顺序返回答案。

示例 1:

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

示例 2:

输入:s = "0000"
输出:["0.0.0.0"]

示例 3:

输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示:

  • 1 <= s.length <= 20
  • s 仅由数字组成

题目解析

  • 主函数 restoreIpAddresses

    • 初始化输入字符串 str
    • 调用 backtrace 方法,从索引0开始递归生成所有可能的IP地址组合。
  • 回溯函数 backtrace

    • 如果 path(存储当前路径的IP段)中正好有4段,且字符串已完全处理完:
      • 将路径拼接成IP地址,加入结果列表 result
    • 如果超过4段或字符串处理完但不足4段,则直接返回。
    • 遍历字符串,从当前位置 start 开始切分长度为1到3的子串:
      • 检查子串是否是有效IP段(用 isValid 函数)。
      • 如果有效,加入路径并继续递归。
      • 递归完成后回溯,将最后一个加入的段移除。
  • 有效性检查 isValid

    • 检查一个子串是否为合法IP段:
      • 长度为1时,直接合法。
      • 长度大于1时,不能以0开头,且必须在0~255范围内。
class Solution {List<String> result = new ArrayList<>();List<String> path = new LinkedList<>();String str;// 递归回溯方法public void backtrace(int start) {// 如果路径已经有4个段,并且已经处理完字符串,则记录结果if (path.size() == 4 && start == str.length()) {StringBuilder end = new StringBuilder();for (int i = 0; i < path.size(); i++) {end.append(path.get(i));if (i != path.size() - 1) {end.append(".");}}result.add(end.toString());return;}// 如果路径长度大于4段或者已经到达字符串末尾,停止递归if (path.size() > 4 || start == str.length()) {return;}// 尝试从当前位置切分1到3位长度的子字符串for (int i = start + 1; i <= Math.min(start + 3, str.length()); i++) {String segment = str.substring(start, i);// 检查段的有效性if (isValid(segment)) {path.add(segment);backtrace(i); // 递归调用处理下一个段path.remove(path.size() - 1); // 回溯,去掉当前段}}}// 检查一个字符串是否是有效的IP段private boolean isValid(String segment) {// 不能以"0"开头的多位数字,且必须在0到255之间if (segment.length() > 1 && segment.charAt(0) == '0') {return false;}int num = Integer.parseInt(segment);return num >= 0 && num <= 255;}public List<String> restoreIpAddresses(String s) {str = s;backtrace(0); // 从字符串的第一个字符开始return result;}
}

78. 子集

题目

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

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

示例 1:

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

示例 2:

输入:nums = [0]
输出:[[],[0]]

提示:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

题目解析

以示例中nums = [1,2,3]为例把求子集抽象为树型结构,如下:

从图中红线部分,可以看出遍历这个树的时候,把所有节点都记录下来,就是要求的子集集合

这道题就是一道非常标准的回溯法遍历得出结果集的题目

没什么好说的,直接看代码

class Solution {List<List<Integer>> result=new ArrayList<>();List<Integer>path =new LinkedList<>();public void backtrace(int[]nums,int start){result.add(new ArrayList<>(path));if(start>=nums.length){return;}for(int i=start;i<nums.length;i++){path.add(nums[i]);backtrace(nums,i+1);path.removeLast();}}public List<List<Integer>> subsets(int[] nums) {backtrace(nums,0);return result;}
}

90. 子集 II

题目

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

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

示例 1:

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

示例 2:

输入:nums = [0]
输出:[[],[0]]

题目解析

大体思路和上一题相同,但是多了一个去重的步骤

具体可以看我之前的文章的第二题所用的方法,用一个标记数组在树层进行去重

算法训练第二十二天|39. 组合总和 40. 组合总和 II 131. 分割回文串-CSDN博客

Java代码如下:

class Solution {List<List<Integer>> result=new ArrayList<>();List<Integer>path =new LinkedList<>();boolean []used;public void backtrace(int[]nums,int start){result.add(new ArrayList<>(path));if(start>=nums.length){return;}for(int i=start;i<nums.length;i++){if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false){continue;}used[i]=true;path.add(nums[i]);backtrace(nums,i+1);used[i]=false;path.removeLast();}}public List<List<Integer>> subsetsWithDup(int[] nums) {used=new boolean[nums.length];Arrays.fill(used,false);Arrays.sort(nums);backtrace(nums,0);return result;}
}

相关文章:

算法训练第二十三天|93. 复原 IP 地址 78. 子集 90. 子集 II

93. 复原 IP 地址--分割 题目 有效 IP 地址 正好由四个整数&#xff08;每个整数位于 0 到 255 之间组成&#xff0c;且不能含有前导 0&#xff09;&#xff0c;整数之间用 . 分隔。 例如&#xff1a;"0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址&…...

imu相机EKF

ethzasl_sensor_fusion/Tutorials/Introductory Tutorial for Multi-Sensor Fusion Framework - ROS Wiki https://github.com/ethz-asl/ethzasl_msf/wiki...

【杂谈】虚拟机与EasyConnect运行巧设:Reqable助力指定应用流量专属化

场景 公司用的是EasyConnect&#xff0c;这个软件非常好用&#xff0c;也非常稳定&#xff0c;但是有个缺点&#xff0c;就是会无条件拦截本机所有流量&#xff0c;而且会加入所有运行的exe程序&#xff0c;实现流量全部走代理。 准备材料 一个windows/Linux 桌面版虚拟机Ea…...

【AI系列】Paddle Speech安装指南

文章目录 环境依赖1. 安装Python1.1 下载Python安装包1.2 安装gcc1.3 安装依赖库1.4 编译和安装Python1.5 配置环境变量 2. 安装PaddlePaddle3. 安装PaddleSpeech4. 运行PaddleSpeech5. 解决常见问题5.1 错误&#xff1a;libssl.so.1.1解决方法&#xff1a; 5.2 错误&#xff1…...

【AI学习】OpenAI推出o3,向AGI迈出关键一步

2024年12月21日&#xff0c;OpenAI在其为期12天发布会活动的最后一天&#xff0c;正式发布了备受期待的o3系列模型&#xff0c;包括o3和o3-mini。 o3 是一个非常强大的模型&#xff0c;在编码、数学以及 ARC-AGI 基准测试等多个基准上超过了 OpenAI 此前的 o1 模型&#xff08…...

深度学习0-前置知识

一、背景 AI最大&#xff0c;它的目的是通过让机器模仿人类进而超越人类&#xff1b; ML次之&#xff0c;它是AI的一个分支&#xff0c;是让机器模仿人类的一种方法。开发人员用大量数据和算法“训练”机器&#xff0c;让机器自行学会如何执行任务&#xff0c;它的成功取决于…...

Elasticsearch-分词器详解

什么是分词器 1、分词器介绍 对文本进行分析处理的一种手段&#xff0c;基本处理逻辑为按照预先制定的分词规则&#xff0c;把原始文档分割成若干更小粒度的词项&#xff0c;粒度大小取决于分词器规则。 常用的中文分词器有ik按照切词的粒度粗细又分为:ik_max_word和ik_smart&…...

Android-相对布局RelativeLayout

相对布局在摆放子视图位置时&#xff0c;按照指定的参考系来摆放子视图的位置&#xff0c;默认以屏幕左上角(0,0)位置作为参考系摆放位置 了解一下接下来都会以代码的方式可视化出来 属性 可选值 说明 layout_alignParentTop true/false 是否让控件相对于父容器顶部对齐 …...

Centos7, 使用yum工具,出现 Could not resolve host: mirrorlist.centos.org

在 CentOS 7 中使用 yum 工具时&#xff0c;如果出现 "Could not resolve host: mirrorlist.centos.org" 的错误&#xff0c;通常是因为默认的镜像源无法访问。以下是一些常用的解决方法&#xff1a; 检查网络连接&#xff1a;首先使用 ping 命令测试网络连接是否正常…...

在Linux中使用`scp`进行远程目录文件复制

在Linux系统中&#xff0c;scp&#xff08;安全复制协议&#xff09;是一个使用SSH&#xff08;安全外壳协议&#xff09;进行文件和目录安全传输的命令。它允许在远程主机之间复制文件和目录&#xff0c;具有很强的安全性&#xff0c;是一种常用的文件传输工具。以下是如何使用…...

VisionPro 机器视觉案例 之 连接件测量

第十八篇 机器视觉案例 之 连接件测量 文章目录 第十八篇 机器视觉案例 之 连接件测量1.案例要求2.实现思路2.1 测量圆心到直线的距离2.2 测量圆心到直线起点的连线和直线的夹角 3.使用控件3.1 模板匹配工具 —— CogPMAlignTool3.2 定位工具 —— CogFixtureTool3.3 卡尺工具 …...

C++ 中面向对象编程中对象的状态存储与恢复的处理

1.对象存储 1)栈存储&#xff1a; 对于局部对象&#xff0c;它们存储在栈上。当进入包含对象定义的代码块时&#xff0c;对象被创建并压入栈中。 例如&#xff1a; class fun { public: int a; }; void func() { fun A; // 对象存储在栈上&#xff0c;随着函数结束自动销毁…...

ip_output函数

ip_output函数是Linux内核(特别是网络子系统)中用于发送IPv4数据包的核心函数。以下是一个示例实现,并附上详细的中文讲解: int ip_output(struct net *net, struct sock *sk, struct sk_buff *skb) {struct iphdr *iph; /* 构建IP头部 */iph = ip_hdr(skb);/* 设置服务…...

【win10+RAGFlow+Ollama】搭建本地大模型助手(教程+源码)

一、RAGFlow简介 RAGFlow是一个基于对文档深入理解的开源RAG&#xff08;Retrieval-augmented Generation&#xff0c;检索增强生成&#xff09;引擎。 主要作用&#xff1a; 让用户创建自有知识库&#xff0c;根据设定的参数对知识库中的文件进行切块处理&#xff0c;用户向大…...

现代风格VUE3易支付用户控制中心

适用系统 彩虹易支付 技术栈 vitevue3elementuiplusphp 亮点 独立前端代码,扩展开发,不改动系统文件,不影响原版升级 支持功能订制 界面预览...

CentOS 7 上自动安装 Python 3.9 脚本

安装 在 CentOS 7 上安装 Python 3.9 可以通过编写一个 Shell 脚本来自动化这一过程。以下是一个示例脚本&#xff0c;它将帮助你在 CentOS 7 上安装 Python 3.9&#xff1a; #!/bin/bash# 脚本设置失败终止 set -e# 更新系统 # sudo yum update -y# 安装依赖 sudo yum insta…...

Spring(二)---基于注解的方式实现Bean管理和注入属性

目录 引入 什么是注解 Spring针对Bean管理中创建对象提供的注解 用注解的方式创建对象 ①&#xff1a;编写接口和实现类 ②&#xff1a;在需要管理的类上添加Component注解&#xff08;上边四个都可以&#xff09; ③&#xff1a;编写配置文件&#xff0c;重点是开启注解…...

采购管理系统的设计与实现【文档+源码】

目录 摘 要 Abstract 第一章 引言 1.1研究现状 1.2主要研究的目的及内容 1.3研究方法及设计思路 1.3.1 研究方法 1.3.2 设计思路 1.4.相关技术简介 1.4.1 JSP技术简介 1.4.2 Struts 框架 1.4.3 Hibernate数据访问框架 1.4.4 B/S模式分析 1.5 系统开发步骤 第二…...

Overleaf编译运行时间太长,国内如何支付升级Overleaf高级账户?

大家好&#xff0c;我是『扑扑特桔』 最近为了赶论文&#xff0c;我一直在 Overleaf 上忙活。 但是因为论文里面图片比较多&#xff0c;因此在某一次编译的时候&#xff0c;突然就提示编译超时。 主要是因为用的是免费版本的Overleaf&#xff0c;对编译时长有限制&#xff0c…...

UE5喷涂功能

许多FPS/TPS 游戏都有喷涂、涂鸦功能 其实原理很简单&#xff0c;就是利用了延迟贴花实现的 我们从网上随便找一张图 创建一个材质&#xff0c;材质域选择延迟贴花 混合模式选择半透明&#xff0c;自发光强度可以看感觉调整 材质做好之后编译保存&#xff0c;新建一个Actor…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...

麒麟系统使用-进行.NET开发

文章目录 前言一、搭建dotnet环境1.获取相关资源2.配置dotnet 二、使用dotnet三、其他说明总结 前言 麒麟系统的内核是基于linux的&#xff0c;如果需要进行.NET开发&#xff0c;则需要安装特定的应用。由于NET Framework 是仅适用于 Windows 版本的 .NET&#xff0c;所以要进…...

LUA+Reids实现库存秒杀预扣减 记录流水 以及自己的思考

目录 lua脚本 记录流水 记录流水的作用 流水什么时候删除 我们在做库存扣减的时候&#xff0c;显示基于Lua脚本和Redis实现的预扣减 这样可以在秒杀扣减的时候保证操作的原子性和高效性 lua脚本 // ... 已有代码 ...Overridepublic InventoryResponse decrease(Inventor…...

多模态大语言模型arxiv论文略读(110)

CoVLA: Comprehensive Vision-Language-Action Dataset for Autonomous Driving ➡️ 论文标题&#xff1a;CoVLA: Comprehensive Vision-Language-Action Dataset for Autonomous Driving ➡️ 论文作者&#xff1a;Hidehisa Arai, Keita Miwa, Kento Sasaki, Yu Yamaguchi, …...

【学习记录】使用 Kali Linux 与 Hashcat 进行 WiFi 安全分析:合法的安全测试指南

文章目录 &#x1f4cc; 前言&#x1f9f0; 一、前期准备✅ 安装 Kali Linux✅ 获取支持监听模式的无线网卡 &#x1f6e0; 二、使用 Kali Linux 进行 WiFi 安全测试步骤 1&#xff1a;插入无线网卡并确认识别步骤 2&#xff1a;开启监听模式步骤 3&#xff1a;扫描附近的 WiFi…...