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

代码随想录算法训练营第二十七天|93.复原IP地址、78.子集、90.子集II

93.复原IP地址

  • 刷题icon-default.png?t=N7T8https://leetcode.cn/problems/restore-ip-addresses/description/
  • 文章讲解icon-default.png?t=N7T8https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html
  • 视频讲解icon-default.png?t=N7T8https://www.bilibili.com/video/BV1XP4y1U73i/?vd_source=af4853e80f89e28094a5fe1e220d9062
  • 回溯树图示:

  • 题解(字符串普通解法):
class Solution {//存储结果List<String> result = new ArrayList<>();public List<String> restoreIpAddresses(String s) {//剪枝,去除非法长度if(s.length() > 12){return result;}restoreIpAddresses1(s, 0, 0);return result;}//startIndex:for循环起始index//pointNum:标记逗点添加的个数,作为递归出口public void restoreIpAddresses1(String s, int startIndex, int pointNum){//递归出口//已添加3个逗点,分割结束if(pointNum == 3){//需要判断最后一段是否合法(区间均为左闭右闭)if(isValid(s, startIndex, s.length() - 1)){result.add(s);}//无论是否合法,此时均需结束,returnreturn;}//递归回溯部分//以startIndex为划分界限for(int i = startIndex; i < s.length(); i++){//若当前划分区间符合要求则往下处理if(isValid(s, startIndex, i)){//加工逗点处理(substring左闭右开)//在i和i+1中间插入逗点s = s.substring(0, i + 1) + "." + s.substring(i + 1);//已添加了一个逗点pointNum++;//递归//需要把已添加逗点的位置空出来,所以是i+2为起始(i+1为逗点)restoreIpAddresses1(s, i + 2, pointNum);//回溯pointNum--;//空出了i+1的逗点位置,删掉逗点s = s.substring(0, i + 1) + s.substring(i + 2);}else{//若当前划分区间不合要求,则结束当前循环返回上一层break;}}}public boolean isValid(String s, int start, int end){//根据区间左闭右闭判断终止条件if(start > end){return false;}//不合法情况;0开头数字不合法,0单独的数字合法if(s.charAt(start) == '0' && start != end){return false;}int num = 0;for(int i = start; i <= end; i++){//字符Ascll码比较if(s.charAt(i) > '9' || s.charAt(i) < '0'){return false;}//计算当前总和是否合法num = num * 10 + (s.charAt(i) - '0');if(num > 255){return false;}}return true;}
}
78.子集
  • 刷题icon-default.png?t=N7T8https://leetcode.cn/problems/subsets/description/
  • 文章讲解icon-default.png?t=N7T8https://programmercarl.com/0078.%E5%AD%90%E9%9B%86.html
  • 视频讲解icon-default.png?t=N7T8https://www.bilibili.com/video/BV1U84y1q7Ci/?vd_source=af4853e80f89e28094a5fe1e220d9062
  • 回溯树图示:

  • 题解:
class Solution {//存放最后符合条件结果的集合List<List<Integer>> result = new ArrayList<>();//每次符合条件的结果LinkedList<Integer> path = new LinkedList<>();//这道题目与之前题目的区别在于://这道题是求子集,回溯树上每一个结点都需要取值//之前的组合问题,回溯树上只取叶子结点的值public List<List<Integer>> subsets(int[] nums) {subsets1(nums, 0);return result;}public void subsets1(int[] nums, int startIndex){//需要先将当前结点放入最后结果集,因为若放在递归出口后面,就会漏掉叶子结点的结果result.add(new ArrayList<>(path));//递归出口if(startIndex >= nums.length){return;}for(int i = startIndex; i < nums.length; i++){path.add(nums[i]);//递归部分//为了防止集合重复,需要startIndex+1subsets1(nums, i + 1);//回溯部分path.removeLast();}}
}

90.子集II

  • 刷题icon-default.png?t=N7T8https://leetcode.cn/problems/subsets-ii/description/
  • 文章讲解icon-default.png?t=N7T8https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html
  • 视频讲解icon-default.png?t=N7T8https://www.bilibili.com/video/BV1vm4y1F71J/?vd_source=af4853e80f89e28094a5fe1e220d9062
     
  •  回溯树图示:

  • 题解:
class Solution {//存储所有的结果List<List<Integer>> result = new ArrayList<>();//存放当前符合条件的结果LinkedList<Integer> path = new LinkedList<>();//标记当前元素是否使用过,用来进行树层去重boolean[] used;//本题与上一个的区别在于去重,其他则同样需要收集回溯树上的每一个结点public List<List<Integer>> subsetsWithDup(int[] nums) {if(nums.length == 0){return result;}Arrays.sort(nums);used = new boolean[nums.length];subsetsWithDup1(nums, 0);return result;}public void subsetsWithDup1(int[] nums, int startIndex){//因为需要添加回溯树上的每个结点,所以需要最先添加//并且为了不漏下叶子结点上的结果,要放在递归出口的前面result.add(new ArrayList<>(path));//递归出口if(startIndex >= nums.length){return;}//递归回溯部分for(int i = startIndex; i < nums.length; i++){//树层去重if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){continue;}path.add(nums[i]);used[i] = true;//递归部分,上下级需要防重复subsetsWithDup1(nums, i + 1);//回溯部分path.removeLast();used[i] = false;}}
}

相关文章:

代码随想录算法训练营第二十七天|93.复原IP地址、78.子集、90.子集II

93.复原IP地址 刷题https://leetcode.cn/problems/restore-ip-addresses/description/文章讲解https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html视频讲解https://www.bilibili.com/video/BV1XP4y1U73i/?vd_sourceaf4853e80f89e28094a5fe1e220d9…...

【蓝桥备赛】字串简写

字串简写 数据范围 字符串的长度为5*10的五次方&#xff0c;on方时间复杂度会很大。 才用动态规划的思想&#xff0c;dp[i]以i开头的的可能性&#xff0c;因为长度必须大于等于k&#xff0c;当i小于k的时候&#xff0c;如果等于第一个字符&#xff0c;s1时&#xff0c;dp[…...

nios ii开发随笔

错误一&#xff1a; d:/intelfpga/17.1/nios2eds/bin/gnu/h-x86_64-mingw32/bin/../lib/gcc/nios2-elf/5.3.0/../../../../../H-x86_64-mingw32/nios2-elf/bin/ld.exe: test.elf section .text will not fit in region ram_oc_xzs d:/intelfpga/17.1/nios2eds/bin/gnu/h-x86_6…...

SpringBoot项目嵌入RabbitMQ

在Spring Boot中嵌入RabbitMQ可以通过添加相应的依赖来完成。首先需要在pom.xml文件中引入spring-boot-starter-amqp依赖&#xff1a; <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-amqp</a…...

提升网络质量:UDPspeeder 实现网络优化与提速

提升网络质量&#xff1a;UDPspeeder 实现网络优化与提速 背景与意义原理与功能使用方法未来展望相关链接服务 在当今高度互联的网络环境下&#xff0c;网络质量的优化和提速对于用户体验至关重要。针对高延迟和丢包率较高的网络链路&#xff0c;UDPspeeder 提供了一种前向纠错…...

为什么前端开发变得越来越复杂了?这可能是我们的错

前端训练营&#xff1a;1v1私教&#xff0c;终身辅导计划&#xff0c;帮你拿到满意的 offer。 已帮助数百位同学拿到了中大厂 offer。欢迎来撩~~~~~~~~ Hello&#xff0c;大家好&#xff0c;我是 Sunday。 最近有很多同学来问我&#xff1a;“Sunday 老师&#xff0c;前端学起…...

VR系统的开发流程

虚拟现实&#xff08;Virtual Reality&#xff0c;VR&#xff09;系统是一种通过计算机技术模拟出的具有三维视角和交互性的虚拟环境&#xff0c;使用户能够沉浸在其中并与虚拟环境进行交互。这种技术通常利用头戴式显示器和手柄等设备&#xff0c;使用户能够感觉到仿佛身临其境…...

前端输入框校验限制不能输入中文

一般我们在做表单的时候都会有表单校验,通常都是用element提供的表单验证的功能&#xff0c;只需要通过 rules 属性传入约定的验证规则&#xff0c;如下面这样 rules: {userName: [{validator: checkUsername,trigger: "blur",},{ validator: this.checkData, trigge…...

强大的文本绘图——PlantUML

PlantUML是一款开源工具&#xff0c;它允许用户通过简单的文本描述来创建UML图&#xff08;统一建模语言图&#xff09;。这种方法可以快速地绘制类图、用例图、序列图、状态图、活动图、组件图和部署图等UML图表。PlantUML使用一种领域特定语言&#xff08;DSL&#xff09;&am…...

ES相关问题

在Elasticsearch&#xff08;ES&#xff09;集群中&#xff0c;节点根据其配置和角色可以分为以下几种主要类型&#xff1a; Master Node&#xff08;主节点&#xff09;&#xff1a; 主节点负责管理整个集群的元数据&#xff0c;如索引的创建、删除、分片分配等。它维护着集群…...

基于Linux直接安装的Nginx版本升级方法

引言 随着版本的迭代和漏洞的发现&#xff0c;Nginx作为一款软件避免不了打补丁的命运。 以下基于Linux直接安装的Nginx版本升级。 以下操作均在本地虚拟机中操作验证&#xff0c;请验证后再线上操作。基于centos7测试。 前置资源 获取nginx的最新源码版本网址&#xff1a…...

探索设计模式的魅力:状态模式揭秘-如何优雅地处理复杂状态转换

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;并且坚持默默的做事。 探索设计模式的魅力&#xff1a;状态模式揭秘-如何优雅地处理复杂状态转换 文章目录 一、案例…...

力扣hot100题解(python版10-12题)

哎- -最近本来就没时间写算法 这算法怎么还这么难。。。 10、和为 K 的子数组 给你一个整数数组 nums 和一个整数 k &#xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。 示例 1&#xff1a; 输入&#xff1a;nums [1,1,1]…...

【算法】复杂度分析

第一章、如何分析代码的执行效率和资源消耗 我们知道&#xff0c;数据结构和算法解决的是“快”和“省”的问题&#xff0c;也就是如何让代码运行得更快&#xff0c;一级如何让代码更节省计算机的存储空间。因此&#xff0c;执行效率是评价算法好坏的一个非常重要的指标。那么&…...

车载电子测试学习内容

搜集了一些车载测试的学习内容&#xff0c;大家可以参考。...

STM32F103x 的时钟源

AHB (Advanced High-performance Bus) 高速总线&#xff0c;用来接高速外设的。 APB (Advanced Peripheral Bus) 低速总线&#xff0c;用来接低速外设的&#xff0c;包含APB1 和 APB2。 APB1&#xff1a;上面连接的是低速外设&#xff0c;包括电源接口、备份接口、 CAN 、 US…...

【电路笔记】-RC放电电路

RC放电电路 文章目录 RC放电电路1、概述2、RC放电电路3、RC放电电路示例当电压源从完全充电的 RC 电路中移除时,电容器 C 将通过电阻 R 放电。 1、概述 RC 放电电路利用电阻器-电容器组合的固有 RC 时间常数以指数衰减率对电容器进行放电。 在之前的 RC 充电电路教程中,我们…...

【C++STL】STL容器详解

创作不易&#xff0c;本篇文章如果帮助到了你&#xff0c;还请点赞 关注支持一下♡>&#x16966;<)!! 主页专栏有更多知识&#xff0c;如有疑问欢迎大家指正讨论&#xff0c;共同进步&#xff01; &#x1f525;c系列专栏&#xff1a;C/C零基础到精通 &#x1f525; 给大…...

缓存篇—缓存雪崩

什么是缓存雪崩 通常我们为了保证缓存中的数据与数据库中的数据一致性&#xff0c;会给 Redis 里的数据设置过期时间&#xff0c;当缓存数据过期后&#xff0c;用户访问的数据如果不在缓存里&#xff0c;业务系统需要重新生成缓存&#xff0c;因此就会访问数据库&#xff0c;并…...

力扣日记2.22-【回溯算法篇】47. 全排列 II

力扣日记&#xff1a;【回溯算法篇】47. 全排列 II 日期&#xff1a;2023.2.22 参考&#xff1a;代码随想录、力扣 47. 全排列 II 题目描述 难度&#xff1a;中等 给定一个可包含重复数字的序列 nums &#xff0c;按任意顺序 返回所有不重复的全排列。 示例 1&#xff1a; 输…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...