当前位置: 首页 > 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; 输…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...

DAY 26 函数专题1

函数定义与参数知识点回顾&#xff1a;1. 函数的定义2. 变量作用域&#xff1a;局部变量和全局变量3. 函数的参数类型&#xff1a;位置参数、默认参数、不定参数4. 传递参数的手段&#xff1a;关键词参数5 题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一…...

字符串哈希+KMP

P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...

Copilot for Xcode (iOS的 AI辅助编程)

Copilot for Xcode 简介Copilot下载与安装 体验环境要求下载最新的安装包安装登录系统权限设置 AI辅助编程生成注释代码补全简单需求代码生成辅助编程行间代码生成注释联想 代码生成 总结 简介 尝试使用了Copilot&#xff0c;它能根据上下文补全代码&#xff0c;快速生成常用…...

GB/T 43887-2024 核级柔性石墨板材检测

核级柔性石墨板材是指以可膨胀石墨为原料、未经改性和增强、用于核工业的核级柔性石墨板材。 GB/T 43887-2024核级柔性石墨板材检测检测指标&#xff1a; 测试项目 测试标准 外观 GB/T 43887 尺寸偏差 GB/T 43887 化学成分 GB/T 43887 密度偏差 GB/T 43887 拉伸强度…...