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

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...