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

代码随想录第二十四天| 93.复原IP地址 78.子集 90.子集II

93. 复原IP地址

题目描述

给定一个只包含数字的字符串 s,复原它并返回所有可能的有效 IP 地址格式。

一个有效的 IP 地址 由四个整数部分组成,每部分的取值范围是 0-255,每个部分不能包含前导零。

解题思路

这道题目要求我们将一个数字字符串分割成四个有效的 IP 地址部分。可以使用回溯算法来解决这个问题。回溯法可以帮助我们遍历所有可能的分割方式,然后验证每个分割是否符合有效 IP 地址的规则。

关键点:

  1. 回溯法:从字符串的起始位置开始,递归地尝试分割出每一部分,每一部分必须是一个有效的数字,并且不能超过 255。
  2. 有效 IP 地址的条件
    • 每部分数字的范围是 0 到 255。
    • 每部分不能有前导零,除非部分的值是 “0”。
    • 最终结果必须包含四个部分。
  3. 分割条件:每次递归时,检查当前子串是否符合条件。如果符合条件,递归继续处理剩余的部分。

步骤:

  1. 分割字符串:从字符串的起始位置开始分割,每次分割出一个子串,检查该子串是否有效。
  2. 递归处理:如果当前部分有效,递归处理剩余的部分,直到分割出四个部分。
  3. 回溯:每当分割出一个有效部分后,恢复状态,继续尝试其他可能的分割方式。
  4. 结束条件:当分割出四个部分且整个字符串处理完毕时,将该分割方式保存到结果列表中。

代码实现

class Solution {List<String> result = new ArrayList<>();public List<String> restoreIpAddresses(String s) {if(s.length()>12)return result;treebuilding(s,0,0);return result;}public void treebuilding(String s,int startIndex,int pointSum) {if(pointSum==3){if(check(s,startIndex,s.length()-1)){result.add(s);}return;}for(int i=startIndex;i<s.length();i++){if(check(s,startIndex,i)){s = s.substring(0,i+1)+"."+s.substring(i+1);pointSum++;treebuilding(s,i+2,pointSum);pointSum--;s = s.substring(0,i+1)+s.substring(i+2);}else {break;}}}public boolean check(String s,int start,int end) {if(start>end){return false;}if(s.charAt(start) == '0' && start!=end){return false;}int num = 0;for(int i = start;i<=end;i++){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. 子集

题目描述

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

说明

  • 解集不能包含重复的子集。

解题思路

这道题目要求我们找到数组 nums 的所有可能子集。由于子集的数量为 2^n,其中 n 是数组的长度,因此可以使用回溯算法生成所有可能的子集。

关键点:

  1. 回溯法:通过回溯法可以在每一层递归中选择或不选择当前元素,来生成所有的子集。
  2. 子集生成:每次递归时,都会向当前路径中添加一个新的元素,同时递归生成后续的子集。每次递归结束后,都会移除当前元素,以尝试其他可能性。
  3. 路径管理:使用一个 path 列表来存储当前子集的元素,并在递归过程中进行更新。

步骤:

  1. 从空子集开始,逐渐向路径中添加元素,形成一个新的子集。
  2. 对于每个元素,可以选择加入子集或不加入子集。
  3. 递归处理每个可能的选择,直到遍历完所有元素。
  4. 每次递归时,加入当前路径到结果集 result 中,最终返回所有的子集。

代码实现

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> subsets(int[] nums) {treebuilding(nums,0);return result;}public void treebuilding(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]);treebuilding(nums,i+1);path.removeLast();}}
}

90. 子集 II

题目描述

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

说明

  • 解集不能包含重复的子集。

解题思路

这道题目与第78题“子集”非常相似,但有一个额外的挑战——数组可能包含重复元素,因此我们需要确保生成的子集不会重复。为了处理这个问题,使用 used 数组来避免重复元素的选择。

关键点:

  1. 回溯法:和第78题一样,我们使用回溯法生成所有的子集。区别在于这里我们需要处理重复元素,确保不产生重复的子集。
  2. 重复元素的处理:为了避免重复的子集,我们在回溯过程中通过 used 数组来标记已经被使用过的元素。当遇到重复元素时,只有当前一个相同元素已经被选择过时,才能选择当前元素。
  3. 排序:我们首先对 nums 数组进行排序,这样相同的元素会被放在一起,方便我们在回溯过程中跳过重复的元素。

used 数组的作用:

used 数组是用来标记当前元素是否已经被使用过,以确保我们在回溯的过程中不会选择重复的元素。特别地,used 数组的作用如下:

  • 标记已经使用的元素:在每次递归中,如果我们选择了一个元素,就通过将 used[i] 设置为 true 来标记这个元素已经被使用。然后递归处理后续的元素。
  • 跳过重复元素:当我们遇到重复元素时,used 数组能够确保我们跳过那些“重复的”分支。具体来说,在遍历过程中,如果当前元素 nums[i] 和前一个元素 nums[i-1] 相等,并且前一个元素没有被选过(即 used[i-1] == false),则跳过当前元素 nums[i],防止重复子集的生成。

解决重复子集的核心:

  1. 排序:对数组进行排序,使得相同的元素相邻。这样在回溯过程中,当遇到重复元素时,可以判断它是否已经被处理过。
  2. 跳过重复元素:通过 used 数组来标记每个元素是否被使用过。如果当前元素和前一个元素相同,并且前一个元素没有被使用过,则跳过当前元素,这样可以避免在同一层递归中重复使用相同的元素。

步骤:

  1. 排序:首先对数组进行排序,使得相同的元素相邻,便于跳过重复元素。
  2. 回溯法:递归地生成所有子集,每次选择一个元素加入当前子集。
  3. 跳过重复元素:在遍历元素时,如果当前元素与前一个元素相同,并且前一个元素没有被选择,则跳过当前元素,避免产生重复子集。

代码实现

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<Integer>();boolean[] used;public List<List<Integer>> subsetsWithDup(int[] nums) {if(nums.length==0){result.add(path);return result;}Arrays.sort(nums);used = new boolean[nums.length];treebuilding(nums,0);return result;}public void treebuilding(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;treebuilding(nums,i+1);used[i] = false;path.removeLast();}}
}

相关文章:

代码随想录第二十四天| 93.复原IP地址 78.子集 90.子集II

93. 复原IP地址 题目描述 给定一个只包含数字的字符串 s&#xff0c;复原它并返回所有可能的有效 IP 地址格式。 一个有效的 IP 地址 由四个整数部分组成&#xff0c;每部分的取值范围是 0-255&#xff0c;每个部分不能包含前导零。 解题思路 这道题目要求我们将一个数字字…...

Linux编程:基于 Unix Domain Socket 的进程/线程间通信实时性优化

文章目录 0. 引言1. 使用 epoll 边缘触发模式非不要不选择阻塞模式边缘触发&#xff08;ET&#xff09;模式优点示例 2. 使用实时调度策略3. CPU 绑定4. 使用无锁缓冲区5. 优化消息传递的大小和频率6. 使用 SO_RCVTIMEO 和 SO_SNDTIMEO7. 示例代码其他阅读 0. 引言 前几天被问…...

PET-文件包含-FINISHED

include发生错误报warning&#xff0c;继续执行。require发生错误直接error&#xff0c;不继续执行 无视扩展名&#xff0c;只要能解析&#xff0c;就能当可执行文件执行&#xff0c;哪怕文件后缀或没后缀 1 条件竞争 pass17 只需要知道tmp的路径。把xieshell.jpg上传&…...

《WebGL编程指南》书籍分享

在这个数字化时代&#xff0c;WebGL作为一门前沿的图形渲染技术&#xff0c;为网页带来了前所未有的交互体验。今天&#xff0c;我很荣幸向大家分享一本关于学习WebGL的书籍——《Webgl编程指南》 电子版下载链接: https://pan.baidu.com/s/1eTX2Y5ynYH0pUQRf0Jcbow?...

go T 泛型

目录 1、类型约束 2、泛型函数 3、泛型结构体 4、泛型接口 5、以接口作为类型约束 关键词&#xff1a;泛型、类型参数、类型约束 Go 语言在 1.18 版本引入了泛型&#xff08;Generics&#xff09;特性&#xff0c;可以编写更通用、可复用的代码&#xff0c;泛型可以用于&a…...

React的基础API介绍(二)

目录 useStateuseState 的基本原理1. 状态在函数组件中的引入2. useState 的工作机制3. Hook 状态与组件渲染 useState 的使用方法1. 基本用法2. 多个状态变量3. 更新状态 注意事项与最佳实践1. 状态更新可能是异步的2. 不要直接修改状态3. 更新对象或数组状态4. 避免闭包陷阱 …...

远程开发测试必看:如何在群晖NAS上运行网页版Ubuntu

文章目录 前言1. 下载Docker-Webtop镜像2. 运行Docker-Webtop镜像3. 本地访问网页版Linux系统4. 群晖NAS安装Cpolar工具5. 配置异地访问Linux系统6. 异地远程访问Linux系统7. 固定异地访问的公网地址 前言 本文将详细讲解如何在群晖NAS上部署docker-webtop&#xff0c;并利用c…...

JAVA题目笔记(十五)经典算法题

一、按要求排序 要求&#xff1a;定义数组并存储一些女朋友对象&#xff0c;利用Arrays中的sort方法进行排序 属性包括&#xff1a;姓名&#xff0c;年龄&#xff0c;身高 按照年龄大小进行排序&#xff0c;年龄一样按照身高排序&#xff0c;身高一样按照姓名字母进行排序。…...

「Mac玩转仓颉内测版8」入门篇8 - Cangjie函数与方法

本篇介绍Cangjie编程语言中的函数与方法&#xff0c;帮助理解如何通过函数封装重复操作&#xff0c;提升代码的复用性和可维护性。 关键词 Cangjie函数方法定义参数传递返回值模块化与复用性 一、什么是函数&#xff1f; 函数是一个代码块&#xff0c;用于接收参数、执行操作…...

2024最新版JavaScript逆向爬虫教程-------基础篇之Proxy与Reflect详解

目录 一、监听对象的操作二、Proxy基本使用2.1 创建空代理2.2 定义捕获器2.2.1 Proxy的set和get捕获器2.2.2 Proxy(handler)的13个捕获器 三、Reflect的作用3.1 Reflect的使用3.2 Reflect其余方法(9个)3.3 Proxy与Reflect中的receiver参数3.4 Reflect中的construct方法 ECMAScr…...

代码修改材质参数

1、 如何得到对象使用的材质 获取到对象的渲染器Renderer Mesh Renderer和Skinned Mesh Renderer都继承Renderer&#xff0c;可以用里式替换原则父类获取、装载子类对象 通过渲染器获取到对应材质 可以利用渲染器中的material或者sharedMaterial来获取物体的材质&#xff0…...

[C++11] 包装器 : function 与 bind 的原理及使用

文章目录 functionstd::function 的基本语法使用 std::function 包装不同的可调用对象function包装普通成员函数为什么要传入 this 指针参数&#xff1f;传入对象指针与传入对象实例的区别 例题 &#xff1a;150. 逆波兰表达式求值 - ⼒扣&#xff08;LeetCode&#xff09; bin…...

java项目-jenkins任务的创建和执行

参考内容: jenkins的安装部署以及全局配置 1.编译任务的general 2.源码管理 3.构建里编译打包然后copy复制jar包到运行服务器的路径 clean install -DskipTests -Pdev 中的-Pdev这个参数用于激活 Maven 项目中的特定构建配置&#xff08;Profile&#xff09; 在 pom.xml 文件…...

单片机中的BootLoader(重要的概念讲解)

文章目录 一、链接地址和执行地址1. 链接地址(Load Address)2. 执行地址(Execution Address)链接地址与执行地址的关系实际工作流程总结二、相对跳转和绝对跳转1. 相对跳转(Relative Jump)2. 绝对跳转(Absolute Jump)3. `BX` 和 `BL` 指令总结三、散列文件1. 散列文件的…...

【数据分享】中国食品工业年鉴(1984-2023) PDF

数据介绍 一、《中国食品工业年鉴》(以下简称《年鉴》)是一部全面反映上一年度全国食品工业发展情况纪年性、资料性、权威大型年刊。《年鉴(2023)》系统收录了全国食品行业各专业和 31个省(自治区、直辖市)2022年食品工业经济运行情况的综述&#xff0c;《年鉴》是由中国食品工…...

优选算法 - 1 ( 双指针 移动窗口 8000 字详解 )

一&#xff1a;双指针 1.1 移动零 题目链接&#xff1a;283.移动零 class Solution {public void moveZeroes(int[] nums) {for(int cur 0, dest -1 ; cur < nums.length ; cur){if(nums[cur] 0){}else{dest; // dest 先向后移动⼀位int tmp nums[cur];nums[cur] num…...

FairyGUI和Unity联动(入门篇)

一、FairyGUI编辑器中 1.新建按钮、新建组件 编辑器中界面简易设计如下 2.文件-发布设置-发布路径&#xff1a;自己unity项目Resources所在的路径 二、Unity 使用代码展示UI using FairyGUI; using System.Collections; using System.Collections.Generic; using UnityEngi…...

Go:文件输入输出以及json解析

文章目录 读取用户的输入文件读写读文件写文件 文件拷贝io包中接口的概念JSON 数据格式编码解码任意的数据&#xff1a; 读取用户的输入 从键盘和标准输入 os.Stdin 读取输入&#xff0c;最简单的办法是使用 fmt 包提供的 Scan… 和 Sscan… 开头的函数 看如下的程序 func t…...

编写红绿起爆线指标(附带源码下载)

编写需求&#xff1a; 想问问有没有能标注行情起爆点的指标。 效果展示&#xff1a; 红线上&#xff0c;出现绿柱转红柱做多。 蓝线下&#xff0c;出现红柱转绿柱做空。 源码展示&#xff08;部分源码&#xff0c;完整源码需下载源码文件&#xff09;&#xff1a; IsMainIn…...

设计模式(四)装饰器模式与命令模式

一、装饰器模式 1、意图 动态增加功能&#xff0c;相比于继承更加灵活 2、类图 Component(VisualComponent)&#xff1a;定义一个对象接口&#xff0c;可以给这些对象动态地添加职责。ConcreteComponent(TextView)&#xff1a;定义一个对象&#xff0c;可以给这个对象添加一…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...