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

代码随想录 || 回溯算法93 78 90

Day24

93.复原IP地址


力扣题目链接

给定一个只包含数字的字符串,复原它并返回所有可能的 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 地址。

思路

  • 其实还是切割问题

  • 递归参数

  • startIndex一定是需要的,因为不能重复分割,记录下一层递归分割的起始位置。

本题我们还需要一个变量pointNum,记录添加逗点的数量。

  • 递归终止条件

  • 本题明确要求只会分成4段,所以不能用切割线切到最后作为终止条件,而是分割的段数作为终止条件。

pointNum表示逗点数量,pointNum为3说明字符串分成了4段了。

然后验证一下第四段是否合法,如果合法就加入到结果集里

  • 单层搜索的逻辑

  • for (int i = startIndex; i < s.size(); i++)循环中 [startIndex, i] 这个区间就是截取的子串,需要判断这个子串是否合法。

如果合法就在字符串后面加上符号.表示已经分割。

如果不合法就结束本层循环

然后就是递归和回溯的过程:

递归调用时,下一层递归的startIndex要从i+2开始(因为需要在字符串中加入了分隔符.),同时记录分割符的数量pointNum 要 +1。

回溯的时候,就将刚刚加入的分隔符. 删掉就可以了,pointNum也要-1。

代码

class Solution {List<String> res = new ArrayList<>();int pointNum = 0;//记录加入的.数量public List<String> restoreIpAddresses(String s) {if (s.length() > 12) return res;//进行剪枝操作,如果长度大于12,直接返回backtracking(s, 0);return res;}private void backtracking(String s, int startIndex) {if (pointNum == 3) {//递归终止条件是加入了三个.if (isValid(s, startIndex, s.length() - 1)) {//看最后一个串是否合法res.add(s);}return;}for (int i = startIndex; i < s.length(); i++) {if (isValid(s, startIndex, i)) {//合法,就加入.s = s.substring(0, i + 1) + "." + s.substring(i + 1);pointNum++;backtracking(s, i + 2);//加入了一个.递归是i+2s = s.substring(0, i + 1) + s.substring(i + 2);pointNum--;}else break;//如果这段不合法直接break}}private boolean isValid(String str, int head, int end) {//判断传入字符串的子串是否合法if (head > end || end - head > 2) return false;//注意head可能越界if (str.charAt(head) == '0' && end > head) return false;//多位数且首位为0不合法int sum = 0;for (int i = head; i <= end; i++) {if (str.charAt(i) < '0' || str.charAt(i) > '9') return false;//特殊字符不合法sum = sum * 10 + (str.charAt(i) - '0');if (sum > 255) return false;//数大于255不合法}return true;}
}

78.子集


力扣题目链接

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

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

思路

  • 这个题目重点在于,子集没有固定长度,所以每一次递归都加入res中即可

  • 先加入空,然后path中加入1,进入递归;加入1,然后path中加入2,进入递归;加入12...直到加入123,结束这层递归,弹出3,结束这层递归;弹出2,加入3,加入13...

代码

class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> subsets(int[] nums) {if (nums == null || nums.length == 0) return res;backtracking(nums, 0);return res;}private void backtracking(int[] nums, int startIndex) {res.add(new ArrayList<>(path));if (startIndex == nums.length) return;for (int i = startIndex; i < nums.length; i++) {path.addFirst(nums[i]);backtracking(nums, i + 1);path.removeFirst();}}
}

90.子集II


力扣题目链接

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

说明:解集不能包含重复的子集。

思路

  • 和上题的区别是加上了去重的逻辑

  • 先对数组进行排序,排序之后注意

  • 循环的时候,如果是上层递归进来的第一次循环,就直接加元素,因为是第一个,元素数量改变了,如果不是第一个还和前一位一样,那这个子集之前考虑过了,就不用再看了

代码

class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {if (nums == null || nums.length == 0) return res;Arrays.sort(nums);backtracking(nums, 0);return res;}private void backtracking(int[] nums, int startIndex) {res.add(new ArrayList<>(path));if (startIndex == nums.length) return;for (int i = startIndex; i < nums.length; i++) {if (i > startIndex && nums[i] == nums[i - 1]) continue;//去重的逻辑在这里path.addFirst(nums[i]);backtracking(nums, i + 1);path.removeFirst();}}
}

相关文章:

代码随想录 || 回溯算法93 78 90

Day2493.复原IP地址力扣题目链接给定一个只包含数字的字符串&#xff0c;复原它并返回所有可能的 IP 地址格式。有效的 IP 地址 正好由四个整数&#xff08;每个整数位于 0 到 255 之间组成&#xff0c;且不能含有前导 0&#xff09;&#xff0c;整数之间用 . 分隔。例如&#…...

界面组件Kendo UI for Angular——让网格数据信息显示更全面

Kendo UI致力于新的开发&#xff0c;来满足不断变化的需求&#xff0c;通过React框架的Kendo UI JavaScript封装来支持React Javascript框架。Kendo UI for Angular是专用于Angular开发的专业级Angular组件&#xff0c;telerik致力于提供纯粹的高性能Angular UI组件&#xff0c…...

【Linux】进程状态|优先级|进程切换|环境变量

文章目录1. 运行队列和运行状态2. 进程状态3. 两种特殊的进程僵尸进程孤儿进程4. 进程优先级5. 进程切换进程特性进程切换6. 环境变量的基本概念7. PATH环境变量8. 设置和获取环境变量9. 命令行参数1. 运行队列和运行状态 &#x1f495; 运行队列&#xff1a; 进程是如何在CP…...

合宙Air780E|FTP|内网穿透|命令测试|LuatOS-SOC接口|官方demo|学习(18):FTP命令及应用

1、FTP服务器准备 本机为win11系统&#xff0c;利用IIS搭建FTP服务器。 搭建方式可参考博文&#xff1a;windows系统搭建FTP服务器教程 windows系统搭建FTP服务器教程_程序员路遥的博客-CSDN博客_windows服务器安装ftp 设置完成后&#xff0c;测试FTP&#xff08;已正常访问…...

大规模 IoT 边缘容器集群管理的几种架构-4-Kubeedge

前文回顾 大规模 IoT 边缘容器集群管理的几种架构-0-边缘容器及架构简介大规模 IoT 边缘容器集群管理的几种架构-1-RancherK3s大规模 IoT 边缘容器集群管理的几种架构-2-HashiCorp 解决方案 Nomad大规模 IoT 边缘容器集群管理的几种架构-3-Portainer &#x1f4da;️Reference…...

Spring底层核心原理解析

Spring简介 ClassPathXmlApplicationContext context new classPathXmlApplicationContext("spring.xml"); UserService userService (UserService) context.getBean("userService"); userService.test();上面一段代码是我们开始学习spring时看到的&…...

OpenStack手动分布式部署Glance【Queens版】

目录 Glance简介 1、登录数据库配置&#xff08;在controller执行&#xff09; 1.1登录数据库 1.2数据库里创建glance 1.3授权对glance数据库的正确访问 1.4退出数据库 1.5创建glance用户密码为000000 1.6增加admin角色 1.7创建glance服务 1.8创建镜像服务API端点 2、安装gla…...

谈一谈你对View的认识和View的工作流程

都2023年了&#xff0c;不会还有人不知道什么是View吧&#xff0c;不会吧&#xff0c;不会吧。按我以往的面试经验来看&#xff0c;View被问到的概率不比Activity低多少哦&#xff0c;个人感觉View在Android中的重要性也和Activity不相上下&#xff0c;所以这篇文章将介绍下Vie…...

Redis集群的脑裂问题

集群脑裂导致数据丢失怎么办&#xff1f; 什么是脑裂&#xff1f; 先来理解集群的脑裂现象&#xff0c;这就好比一个人有两个大脑&#xff0c;那么到底受谁控制呢&#xff1f; 那么在 Redis 中&#xff0c;集群脑裂产生数据丢失的现象是怎样的呢&#xff1f; 在 Redis 主从架…...

互斥信号+任务临界创建+任务锁

普通信号量 1、信号量概念 2、创建信号量函数 3、互斥信号量 创建互斥信号量函数 等待信号量函数 释放互斥信号量 4、创建任务临界区 5、任务锁 任务上锁函数 ​编辑 任务结束函数 效果 普通信号量 1、信号量概念 信号量像是一种上锁机制&#xff0c;代码必须获…...

Elasticsearch7.8.0版本进阶——文档搜索

目录一、文档搜索的概述二、倒排索引不可变的优点三、倒排索引不可变的优点一、文档搜索的概述 早期的全文检索会为整个文档集合建立一个很大的倒排索引并将其写入到磁盘。 一旦新的索引就绪&#xff0c;旧的就会被其替换&#xff0c;这样最近的变化便可以被检索到。倒排索引被…...

spring security权限问题

org.springframework.boot spring-boot-starter-security 引入jar extends WebSecurityConfigurerAdapter 用来配置登陆和权限 configure(HttpSecurity http) 覆盖这个方法 //配置授权相关的 .authorizeRequests () //任何请求 .anyRequest() //要求授权后可以访问 .authen…...

mysql 8.0.22安装

mysql8.0.22安装1. 配置my.ini2. 添加环境变量3. 安装mysql3.1 mysql初始化3.2 安装mysql服务3.3 启动mysql服务4. 连接数据库修改连接数据库的密码前提&#xff1a;已经从官网下载mysql8.0.22安装包并解压&#xff08;下载地址&#xff1a;https://dev.mysql.com/downloads/in…...

Mysql系列:Mysql5.7编译安装

系统环境&#xff1a;Centos7 1&#xff1a;下载mysql源码包 https://dev.mysql.com/downloads/mysql/5.7.html downloads 选择MySQL Community Server>source_code>Generic Linux (Architecture Independent), Compressed TAR Archive -> 选择需要的mysql版本&…...

设备树(配合LED驱动说明)

目录 一、起源 二、基本组成 三、基本语法 四、特殊节点 4.1 根节点 4.2 /memory 4.3 /chosen 4.4 /cpus 多核CPU支持 五、常用属性 5.1 phandle 5.2 地址 --------------- 重要 5.3 compatible --------------- 重要 5.4 中断 --------------- 重要 5.5 …...

(二十六)大白话如何从底层原理解决生产的Too many connections故障?

今天我们继续讲解昨天的那个案例背景&#xff0c;其实就是经典的Too many connections故障&#xff0c;他的核心就是linux的文件句柄限制&#xff0c;导致了MySQL的最大连接数被限制&#xff0c;那么今天来讲讲怎么解决这个问题。 其实核心就是一行命令&#xff1a; ulimit -H…...

ASEMI高压MOS管60R380参数,60R380特征,60R380应用

编辑-Z ASEMI高压MOS管60R380参数&#xff1a; 型号&#xff1a;60R380 漏极-源极电压&#xff08;VDS&#xff09;&#xff1a;600V 栅源电压&#xff08;VGS&#xff09;&#xff1a;20V 漏极电流&#xff08;ID&#xff09;&#xff1a;11A 功耗&#xff08;PD&#x…...

Python期末试卷

《Python程序设计基础》期末试题 班级 学号 姓名 一&#xff0e;选择题(须知:答案写到下方的表格中,其它一律无效.每题2分&#xff0c;共40分) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 1.在Python交互…...

Linux | 网络通信 | http协议介绍 | cookie策略讲解

文章目录url统一资源定位符http协议介绍GET vs POSThttp状态码http常见headercookie session上篇博客定制了一个协议&#xff0c;该协议用来进行简单的计算&#xff0c;其包含了数据的序列化和反序列化&#xff0c;编码和解码的定制&#xff0c;并且该协议基于TCP通信&#xf…...

招投标系统简介 招投标系统源码 java招投标系统 招投标系统功能设计

项目说明 随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大&#xff0c;公司对内部招采管理的提升提出了更高的要求。在企业里建立一个公平、公开、公正的采购环境&#xff0c;最大限度控制采购成本至关重要。符合国家电子招投标法律法规及相关规范&#xff0c;以及…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

【Veristand】Veristand环境安装教程-Linux RT / Windows

首先声明&#xff0c;此教程是针对Simulink编译模型并导入Veristand中编写的&#xff0c;同时需要注意的是老用户编译可能用的是Veristand Model Framework&#xff0c;那个是历史版本&#xff0c;且NI不会再维护&#xff0c;新版本编译支持为VeriStand Model Generation Suppo…...

跨平台商品数据接口的标准化与规范化发展路径:淘宝京东拼多多的最新实践

在电商行业蓬勃发展的当下&#xff0c;多平台运营已成为众多商家的必然选择。然而&#xff0c;不同电商平台在商品数据接口方面存在差异&#xff0c;导致商家在跨平台运营时面临诸多挑战&#xff0c;如数据对接困难、运营效率低下、用户体验不一致等。跨平台商品数据接口的标准…...