算法训练第二十三天|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
。
- 将路径拼接成IP地址,加入结果列表
- 如果超过4段或字符串处理完但不足4段,则直接返回。
- 遍历字符串,从当前位置
start
开始切分长度为1到3的子串:- 检查子串是否是有效IP段(用
isValid
函数)。 - 如果有效,加入路径并继续递归。
- 递归完成后回溯,将最后一个加入的段移除。
- 检查子串是否是有效IP段(用
- 如果
-
有效性检查
isValid
:- 检查一个子串是否为合法IP段:
- 长度为1时,直接合法。
- 长度大于1时,不能以
0
开头,且必须在0~255
范围内。
- 检查一个子串是否为合法IP段:
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 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 . 分隔。 例如:"0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址&…...
JS,递归,处理树形数据组件,模糊查询树形结构数据字段
JS递归如何模糊查询树形结构数据,根据数据中的某一个字段值,模糊匹配 直接拿去使用就行 function filterTreeLabel(arr, label) {let result []arr.forEach((item) > {// if (String(item.POBJECT_NAME).toLowerCase().indexOf(label)!-1) {if (String(item.P…...
前端大数字精度丢失?Choerodon UI 大数字解决方案:精确性与灵活性的结合!
01 引言 在企业项目开发中,数据的精确性是关键。Choerodon UI 的大数字解决方案,通过其高精度计算、数据一致性维护、灵活的数据交互、国际化支持、兼容性保障、定制化格式化等优势,为开发人员提供了一个强大的武器库,以确保在处…...
matlab凸包检测
% 创建一个3D点集 points [1 2 3; 4 5 6; 7 8 9; 10 11 12; 13 14 15]; % 使用convhull函数计算凸包 hull convhull(points); % 输出凸包点的索引 disp(Convex Hull Indices:); disp(hull); % 绘制点集和凸包 figure; scatter3(points(:,1), points(:,2), points(:,3),…...
单节点calico性能优化
在单节点上部署calicov3273后,发现资源占用 修改calico以下配置是资源消耗降低 1、因为是单节点,没有跨节点pod网段组网需要,禁用overlay方式网络(ipip,vxlan),使用route方式网络 配置calico-node的环境变量 CALICO_IPV4POOL_I…...
【芯片设计- RTL 数字逻辑设计入门 番外篇 7.1 -- 基于ATE的IC测试原理】
文章目录 ATE 测试概述Opens/Shorts测试Leakage测试AC测试转自:漫谈大千世界 漫谈大千世界 2024年10月23日 23:17 湖北 ATE 测试概述 ATE(Automatic Test Equipment)是用于检测集成电路(IC)功能完整性的自动测试设备。它在半导体产业中扮演着至关重要的角色,主要用于检…...
oracle 导入数据提示跳过表
imp system/orclorcl fileD:\oracle_back.dmp fully showy logD:\oracle_log.log 今天用上面的命令往 oracle 中导入数据出现一个奇怪的问题 就是所有导入的表都提示 正在跳过表XXX 最后提示成功终止导入, 没有出现警告。 最后select一个表也没导入进来 怪哉怪哉!…...
鸿蒙开发(15)案例 排行榜
排行榜 准备图片 定义案例需要的数据模型 创建Models文件, //定义app需要的数据模型export class FruitData{name:string;vote:string;id:string;constructor(id:string,name:string,vote:string,) {this.id idthis.name namethis.vote vote}}排行榜头部 创…...
【Java Web】Axios实现前后端数据异步交互
目录 一、Promise概述 二、Promise基本用法 三、async和await关键字 四、Axios介绍 4.1 Axios基本用法 4.2 Axios简化用法之get和post方法 五、Axios拦截器 六、跨域问题处理 一、Promise概述 axios是代替原生的ajax实现前后端数据交互的一套新解决方案,而…...
SLAAC如何工作?
SLAAC如何工作? IPv6无状态地址自动配置(SLAAC)-常见问题 - 苍然满关中 - 博客园 https://support.huawei.com/enterprise/zh/doc/EDOC1100323788?sectionj00shttps://www.zhihu.com/question/6691553243/answer/57023796400 主机在启动或接口UP后,发…...
微信小程序UI自动化测试实践 !
微信小程序UI自动化测试实践 引言: 随着微信小程序的快速发展,越来越多的企业和开发者开始开发小程序来满足用户的需求。而在开发小程序的过程中,UI自动化测试是一个必不可少的环节,可以帮助开发者减少人工测试的工作量ÿ…...
代码随想录-笔记-其七
我们来到了贪心算法的章节。 贪心算法和其他部分不太一样的是,他更多的是突出一种思路:通过求局部最优解来求全局最优解。因为只是一个大的思想逻辑,针对不同题型总是有不同的解决方案,所以贪心算法也不想其他算法那样有一个很经…...
react身份证回显
1. 处理身份证号的函数 function getAgeSexAndBirthdate(idCard: string): { sex: 男 | 女 | null; birthdate: Date | null } {if (idCard.length ! 18) {console.error(身份证号码必须是18位。);return { sex: null, birthdate: null };}// 提取出生年月日const year parse…...
Hibernate、JPA、Spring DATA JPA、Hibernate 代理和架构
大家好,今天,我们将讨论 Hibernate 和 JPA 架构。 在开始我们的文章之前,我想回答一个重要的问题:为什么我们需要使用 Hibernate、Eclipse Link、EF core 等 ORM 工具? 事实上,这是一个非常好的问题。我们…...
leetcode----mysql
1179. 重新格式化部门表 - 力扣(LeetCode) 表 Department: ------------------------ | Column Name | Type | ------------------------ | id | int | | revenue | int | | month | varchar | ----…...
盛元广通畜牧与水产品检验技术研究所LIMS系统
一、系统概述 盛元广通畜牧与水产品检验技术研究所LIMS系统集成了检测流程管理、样品管理、仪器设备管理、质量控制、数据记录与分析、合规性管理等功能于一体,能够帮助实验室实现全流程的数字化管理。在水产、畜牧产品的质检实验室中,LIMS系统通过引入…...
EXCEL文件解析
[Excel文件名].xlsx (解压后) │ ├── _rels │ └── .rels (定义关系文件) ├── docProps │ ├── app.xml (应用程序属性) │ └── core.xml (核心文档属性) ├── xl │ ├── _rels │ │ └── workbook.xml.rels (工作簿关系文件) │ ├── …...
【C++】- 掌握STL List类:带你探索双向链表的魅力
文章目录 前言:一.list的介绍及使用1. list的介绍2. list的使用2.1 list的构造2.2 list iterator的使用2.3 list capacity2.4 list element access2.5 list modifiers2.6 list的迭代器失效 二.list的模拟实现1. list的节点2. list的成员变量3.list迭代器相关问题3.1…...
开源 AI 智能名片 S2B2C 商城小程序中运营与产品的关系剖析
摘要:本文聚焦于开源 AI 智能名片 S2B2C 商城小程序,深入探讨其中运营与产品之间的关系。通过分析运营与产品的多种关系认知,阐述在该特定小程序情境下运营与产品相互依存、相互作用的机制,包括运营对产品的需求以及产品对运营的依…...
flask_socketio 以继承 Namespace方式实现一个网页聊天应用
点击进入上一篇,可作为参考 实验环境 python 用的是3.11.11 其他环境可以通过这种方式一键安装: pip install flask3.1.0 Flask-SocketIO5.4.1 gevent-websocket0.10.1 -i https://mirrors.tuna.tsinghua.edu.cn/pypi/web/simple pip list 详情如下&am…...
DePIN潜力项目Spheron解读:激活闲置硬件,赋能Web3与AI
DePIN赛道作为今年加密资本关注的热点之一,不仅吸引了大量资金涌入,还凭借其灵活的资源调配、高效的运作方式和可靠的安全性能,逐渐渗透到多个领域和项目中。例如,Helium的无线网络协议、IoTeX的去中心化物联网、IO NET的去中心化…...
《Vue进阶教程》第十六课:深入完善响应式系统之单例模式
往期内容: 《Vue进阶教程》第五课:ref()函数详解(重点) 《Vue进阶教程》第六课:computed()函数详解(上) 《Vue进阶教程》第七课:computed()函数详解(下) 《Vue进阶教程》第八课:watch()函数的基本使用 《Vue进阶教…...
C++ —— const修饰指针
C —— const修饰指针 常量指针(实际开发中用的很多)指针常量(了解即可)常指针常量(了解即可) 常量指针(实际开发中用的很多) 语法:const 数据类型 *变量名; 不能通过解…...
【学习笔记】数据结构(八)
动态存储管理 文章目录 动态存储管理8.1 概述8.2 可利用空间表及分配方法8.3 边界标识法8.3.1 可利用空间表的结构8.3.2 分配算法8.3.3 回收算法 8.4 伙伴系统8.4.1 可利用空间表的结构8.4.2 分配算法8.4.3 回收算法 8.5 无用单元收集 - 垃圾回收机制8.6 存储紧缩 - 内存碎片化…...
maven-resources-production:ratel-fast: java.lang.IndexOutOfBoundsException
Maven生产环境中遇到java.lang.IndexOutOfBoundsException的问题,尝试了重启电脑、重启IDEA等常规方法无效,最终通过直接重建工程解决了问题。 Rebuild Project 再启动OK...
建投数据与腾讯云数据库TDSQL完成产品兼容性互认证
近日,经与腾讯云联合测试,建投数据自主研发的人力资源信息管理系统V3.0、招聘管理系统V3.0、绩效管理系统V2.0、培训管理系统V3.0通过腾讯云数据库TDSQL的技术认证,符合腾讯企业标准的要求,产品兼容性良好,性能卓越。 …...
后端-添加购物车和查看购物车
...
【HarmonyOS NEXT】Web 组件的基础用法以及 H5 侧与原生侧的双向数据通讯
关键词:鸿蒙、ArkTs、Web组件、通讯、数据 官方文档Web组件用法介绍:文档中心 Web 组件加载沙箱中页面可参考我的另一篇文章:【HarmonyOS NEXT】 如何将rawfile中文件复制到沙箱中_鸿蒙rawfile 复制到沙箱-CSDN博客 目录 如何在鸿蒙应用中加…...
7-2 排序
输入一批未排序的数据,数量不超过30个,请使用选择法或者冒泡法对其排序,并按照规定的要求输出。 输入格式: 先输入待排序的整形数的个数;然后输入所有的待排序的数据。 输出格式: 在一行中按照由大到小的顺序输出排序好的数据…...
Java通过反射破坏单例模式
有个第三方工具类,不支持多例模式。但是又不能直接改第三方工具类的代码,因此可以通过反射破坏第三方工具类的单例。 第三方工具类反编译如下 可以看到构造函数进行了私有化,不允许外部new,只能通过newInstance进行实例化。并且…...
FFmpeg第一话:FFmpeg 简介与环境搭建
FFmpeg 探索之旅 一、FFmpeg 简介与环境搭建 二、FFmpeg 解码详解 第一话:FFmpeg 简介与环境搭建 FFmpeg 探索之旅一、前言二、FFmpeg 是什么?三、简单介绍其历史背景四、为什么用 C学习 FFmpeg?(一)高性能优势&#…...
C++并发编程: std::atomic对指针进行操作
std::atomic 对指针进行运算的用途 std::atomic 提供了一种在多线程环境中安全地操作指针的方法。这对于实现线程安全的指针管理、动态内存分配、链表操作等场景非常有用。通过使用std::atomic对指针进行运算,可以确保指针操作的原子性和多线程安全性。 常见用途 …...
工业大数据分析算法实战-day08
文章目录 day08模型评价聚类算法基于距离的聚类基于层次的聚类基于密度的聚类基于分布的聚类聚类结果的评价 day08 今天是第8天,昨日阐述了概率图模型和集成学习的分类,主要讲解了有向图和无向图,生成式模型和判断式模型,以及集成…...
在 C# 中实现的目录基础操作
前言 在开发应用程序过程中,对操作系统上的文件夹存储文件和子文件夹操作是常见的需求。.NET中的Directory类提供了处理文件目录的功能。本文介绍如何读取文件夹的属性、获取文件夹的大小及文件个数、创建文件夹、遍历文件夹中的所有文件、移动文件夹和删除文件夹等…...
Python 标识符是啥?
Python 的标识符就是我们写代码时用来给变量、函数、类等取名字的东西。 你写的 my_variable 是个标识符, 定义的 add_numbers 函数名也是个标识符, 甚至你写的 Cat 类名,也是标识符。 一句话总结:标识符就是代码里给“东西”起…...
WEB开发: 全栈工程师起步 - Python Flask +SQLite的管理系统实现
一、前言 罗马不是一天建成的。 每个全栈工程师都是从HELLO WORLD 起步的。 之前我们分别用NODE.JS 、ASP.NET Core 这两个框架实现过基于WebServer的全栈工程师入门教程。 今天我们用更简单的来实现: Python。 我们将用Python来实现一个学生管理应用࿰…...
将 Matplotlib 图形转换为 PIL 图像并返回
将 Matplotlib 图形转换为 PIL 图像并返回 前言完整代码Matplotlib 中 fig 和 ax 的关系示例: 问题分析常见错误及解决方案总结 前言 Matplotlib 是 Python 里最流行的图表展示库,PIL (Python Imaging Library)则是一个强大的图像处理库。在开发过程中&…...
F5中获取客户端ip地址(client ip)
当F5设备对其原始设置上的所有IP地址使用NAT时,连接到poo成员(nodes、backend servers)的出站连接将是NAT IP地址。 pool 成员(nodes、backend servers)将无法看到真实的客户端 ip地址,因为看到的是F5上的…...
点焊机器人维修-ABB-KUKA-FANUC-YASKAWA
在正式启用点焊机器人之前,一项至关重要的预备步骤便是进行焊枪的全面设置操作。以FANUC机器人为例,其焊枪的设置流程涵盖了多个关键环节,如焊枪运动方向的精确规划、焊枪规格的选择以及零点标定的细致执行等。这些设置均须严格依据实际所采用…...
springboot448教学辅助系统(论文+源码)_kaic
摘 要 互联网发展至今,无论是其理论还是技术都已经成熟,而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播,搭配信息管理工具可以很好地为人们提供服务。针对信息管理混乱,出错率高,信息安全性差&#x…...
网络地址转换(NAT)和端口映射
1. 网络地址转换(NAT) 1.1 NAT的应用场景 (1)应用场景:允许将私有IP地址映射到公网地址,以减缓IP地址空间的消耗 ①需要连接Internet,但主机没有公网IP地址 ②更换了一个新的ISP,需要重新组织网络时&…...
iClent3D for Cesium 实现无人机巡检飞行效果
作者:gaogy 1、背景 随着地理信息技术的发展,三维地球技术逐渐成为了许多领域中的核心工具,尤其是在城市规划、环境监测、航空航天以及军事领域。三维地图和场景的应用正在帮助人们更加直观地理解空间数据,提供更高效的决策支持。…...
低比特语言模型 是一种利用较少比特数进行语言建模的技术
Vanilla LLM: 基础的全精度语言模型,通常在较高比特数下运作 Vanilla LLM,或称为“基础的全精度语言模型”,是指使用标准的浮点数(通常是16位或32位)进行训练和推理的语言模型。这些模型依赖于经典的神经网络结构&…...
ES6中的map和set
Set ES6 提供了新的数据结构 Set。它类似于数组,但是成员的值都是唯一的,没有重复的值。 Set本身是一个构造函数,用来生成 Set 数据结构。 以下代码 const s new Set();[2, 3, 5, 4, 5, 2, 2].forEach(x > s.add(x));for (let i of s…...
【WRF安装】WRF编译错误总结1:HDF5库包安装
目录 1 HDF5库包安装有误:HDF5 not set in environment. Will configure WRF for use without.HDF5的重新编译 错误原因1:提示 overflow 错误1. 检查系统是否缺少依赖库或工具2. 检查和更新编译器版本3. 检查 ./configure 报错信息4. 检查系统环境变量5.…...
MyBatis常见面试题总结
#{} 和 ${} 的区别是什么? 注:这道题是面试官面试我同事的。 答: ${}是 Properties 文件中的变量占位符,它可以用于标签属性值和 sql 内部,属于原样文本替换,可以替换任意内容,比如${driver}…...
Qt生成随机数的方法
后台接口要求传个流水单号,流水号的格式是:“设备序列号”“设备MAC地址”“20位的随机数”。 具体的是: “设备序列号”:就是烧录工具写入设备的序列编号,这就不多说了,读出来就行; “设备MAC地…...
深入探索Vue.js中的v-if指令:条件渲染的高级技巧
深入探索Vue.js中的v-if指令:条件渲染的高级技巧 引言 在现代Web开发中,根据条件动态地渲染或移除DOM元素是一个常见的需求。Vue.js提供了一种简洁而强大的方法来实现这一目标,即通过v-if指令来根据表达式的值来控制元素的渲染。本文将详细…...
【记录50】uniapp安装uview插件,样式引入失败分析及解决
SassError: Undefined variable: "$u-border-color". 表示样式变量$u-border-color没定义,实际是定义的 首先确保安装了scss/sass 其次,根目录下 app.vue中是否全局引入 <style lang"scss">import /uni_modules/uview-ui/in…...