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

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

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 地址。

示例 1:

  • 输入:s = "25525511135"
  • 输出:["255.255.11.135","255.255.111.35"]

示例 2:

  • 输入:s = "0000"
  • 输出:["0.0.0.0"]

示例 3:

  • 输入:s = "1111"
  • 输出:["1.1.1.1"]

示例 4:

  • 输入:s = "010010"
  • 输出:["0.10.0.10","0.100.1.0"]

示例 5:

  • 输入:s = "101023"
  • 输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示:

  • 0 <= s.length <= 3000
  • s 仅由数字组成

思路:

本题和其他字符串切割的题目类似,只是在切割点处应该用“.”连接起来得到一个IP地址,需要注意的是每个分割后的字段转换为数字后应该保持在0-255的范围内,此处注意点也是可以作为剪枝的方向。另外一个需要注意的点是前导0,如果在切割的时候发现存在前导0,此时不应该继续扩大字段,存在0的字段只能为0。

代码实现如下:

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:self.result = []if len(s) > 12:     # IP最长长度为3*4(255.255.255.255),此处可剪枝return self.resultself.backtracking(s, 0, [])return self.resultdef backtracking(self, s:str, start:int, path:List):if len(path)==4 and start>=len(s):self.result.append(".".join(path))cur = 0#zero = False      # 本来想判断是否存在前导0,但是如果存在并不需要进一步判断,如果cur*10+s[i]等于0说明只能做切割for i in range(start, len(s)):cur = cur * 10 + int(s[i])#if zero==False and cur==0:if cur == 0:#zero = Truepath.append(str(cur))self.backtracking(s, i+1, path)path.pop()returnif cur>0 and cur<=255:path.append(str(cur))self.backtracking(s, i+1, path)path.pop()if cur>255:         #一个段最大为255,大于则剪枝return

规范代码:

回溯(版本一)

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:result = []self.backtracking(s, 0, 0, "", result)return resultdef backtracking(self, s, start_index, point_num, current, result):if point_num == 3:  # 逗点数量为3时,分隔结束if self.is_valid(s, start_index, len(s) - 1):  # 判断第四段子字符串是否合法current += s[start_index:]  # 添加最后一段子字符串result.append(current)returnfor i in range(start_index, len(s)):if self.is_valid(s, start_index, i):  # 判断 [start_index, i] 这个区间的子串是否合法sub = s[start_index:i + 1]self.backtracking(s, i + 1, point_num + 1, current + sub + '.', result)else:breakdef is_valid(self, s, start, end):if start > end:return Falseif s[start] == '0' and start != end:  # 0开头的数字不合法return Falsenum = 0for i in range(start, end + 1):if not s[i].isdigit():  # 遇到非数字字符不合法return Falsenum = num * 10 + int(s[i])if num > 255:  # 如果大于255了不合法return Falsereturn True

回溯(版本二)

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:results = []self.backtracking(s, 0, [], results)return resultsdef backtracking(self, s, index, path, results):if index == len(s) and len(path) == 4:results.append('.'.join(path))returnif len(path) > 4:  # 剪枝returnfor i in range(index, min(index + 3, len(s))):if self.is_valid(s, index, i):sub = s[index:i+1]path.append(sub)self.backtracking(s, i+1, path, results)path.pop()def is_valid(self, s, start, end):if start > end:return Falseif s[start] == '0' and start != end:  # 0开头的数字不合法return Falsenum = int(s[start:end+1])return 0 <= num <= 255

78.子集

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

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

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

思路:

将本题问题可以归结为分别对0~len(nums)个数组长度的切割,所以在回溯函数backtracking中加入length参数,并且从0~len(nums)循环输入进这个参数来进行调用,最后得到的结果数组即可。

代码实现如下:

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:self.result = []for i in range(len(nums)+1):self.backtracking(nums, 0, [], i)return self.resultdef backtracking(self, nums:List[int], start:int, path:List, length:int):if length == 0:self.result.append(path[:])returnfor i in range(start, len(nums)):path.append(nums[i])self.backtracking(nums, i+1, path, length-1)path.pop()

规范代码:(简洁很多,需学习)

class Solution:def subsets(self, nums):result = []path = []self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):result.append(path[:])  # 收集子集,要放在终止添加的上面,否则会漏掉自己# if startIndex >= len(nums):  # 终止条件可以不加#     returnfor i in range(startIndex, len(nums)):path.append(nums[i])self.backtracking(nums, i + 1, path, result)path.pop()

90.子集II

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

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

示例:

  • 输入: [1,2,2]
  • 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

思路:

与上一题相比,多了一个去重步骤,和昨天的题目类似,在开始一个for循环的时候,判断遍历的元素是否与for循环中前一个元素相同,如果相同,说明此时在相同位置出现了同样的元素,所得到的结果必然也是相同的,所以此时应该忽略,寻找下一个不相同的元素。

代码实现如下:

class Solution:def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:self.result = []nums.sort()for i in range(len(nums)+1):       # i代表子集的长度(0~len(nums))self.backtracking(nums, 0, [], i)return self.resultdef backtracking(self, nums: List[int], start:int, path:List, length:int):if length == 0:self.result.append(path[:])returnfor i in range(start, len(nums)):if i>start and nums[i]==nums[i-1]: # 避免重复结果,一个循环内同元素可跳过,相当于起点是相同元素,不会得到不同结果continuepath.append(nums[i])self.backtracking(nums, i+1, path, length-1)path.pop()

规范代码:

回溯 利用used数组去重

class Solution:def subsetsWithDup(self, nums):result = []path = []used = [False] * len(nums)nums.sort()  # 去重需要排序self.backtracking(nums, 0, used, path, result)return resultdef backtracking(self, nums, startIndex, used, path, result):result.append(path[:])  # 收集子集for i in range(startIndex, len(nums)):# used[i - 1] == True,说明同一树枝 nums[i - 1] 使用过# used[i - 1] == False,说明同一树层 nums[i - 1] 使用过# 而我们要对同一树层使用过的元素进行跳过if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:continuepath.append(nums[i])used[i] = Trueself.backtracking(nums, i + 1, used, path, result)used[i] = Falsepath.pop()

回溯 利用集合去重

class Solution:def subsetsWithDup(self, nums):result = []path = []nums.sort()  # 去重需要排序self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):result.append(path[:])  # 收集子集uset = set()for i in range(startIndex, len(nums)):if nums[i] in uset:continueuset.add(nums[i])path.append(nums[i])self.backtracking(nums, i + 1, path, result)path.pop()

回溯 利用递归的时候下一个startIndex是i+1而不是0去重

class Solution:def subsetsWithDup(self, nums):result = []path = []nums.sort()  # 去重需要排序self.backtracking(nums, 0, path, result)return resultdef backtracking(self, nums, startIndex, path, result):result.append(path[:])  # 收集子集for i in range(startIndex, len(nums)):# 而我们要对同一树层使用过的元素进行跳过if i > startIndex and nums[i] == nums[i - 1]:continuepath.append(nums[i])self.backtracking(nums, i + 1, path, result)path.pop()

相关文章:

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

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

【mysql】使用AbstractRoutingDataSource实现多数据源 与 获取mapper上注解

使用AbstractRoutingDataSource实现多数据源 与 获取mapper上注解 背景 随着业务发展速度越来越快&#xff0c;数据的增长也呈现倍数级别增长&#xff0c;数据库的压力&#xff0c;对于查询和写入等所有操作&#xff0c;都依赖于主库&#xff0c;其实有一些对于时效性要求不高…...

希沃冰点还原

要取消希沃冰点还原&#xff0c;可以按照以下步骤进行&#xff1a; 打开希沃冰点还原的应用或程序。 在应用或程序的界面上&#xff0c;寻找设置选项或菜单。 点击或选择设置选项或菜单&#xff0c;进入设置界面。 在设置界面上&#xff0c;查找“取消”或“停止”等相关选项…...

Hadoop服务端口号、Spark端口号、Hive端口号以及启动命令

文章目录 1. 服务端口号1.1 Hadoop相关的服务端口号1.2 Spark相关的服务端口号1.3 Hive的连接端口 2. 服务启动指令 1. 服务端口号 1.1 Hadoop相关的服务端口号 HDFS的web页面访问端口 9870HDFS 的程序访问端口 8020Yarn的访问端口 8088历史日志访问端口 19888 1.2 Spark相关…...

【C++】--类和对象(3)

&#x1f911;个人主页: 起名字真南 &#x1f911;个人专栏:【数据结构初阶】 【C语言】 【C】 目录 1 深入构造函数2 类型转换3 static成员4 友元函数5 内部类6 匿名对象 1 深入构造函数 之前我们实现构造函数的时候&#xff0c;初始化成员变量都是在函数体内赋值&#xff0c…...

国外电商系统开发-运维系统文件上传-高级上传

如果您要上传文件到10台服务器中&#xff0c;有3台服务器的路径不是一样的&#xff0c;那么在这种情况下您就可以使用本功能&#xff0c;单独执行不一样的路径 点击【高级】上传...

【MongoDB】mongodb | 部署 | 常用命令

一、概述 基于mongodb的tcp连接无数据上报&#xff0c;服务器强踢监测。 物联网项目&#xff0c;tcp协议&#xff0c;基于4G卡&#xff0c;设备由于某些原因会断开重连&#xff0c;但是tcp没有断开&#xff0c;导致tcp持续累加&#xff0c;浪费资源。 建立机制&#xff1a; 当t…...

【Chrome浏览器插件--资源嗅探猫抓】

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、资源嗅探插件---猫抓二、使用步骤总结 一、资源嗅探插件—猫抓 猫抓是一个浏览器插件&#xff0c;可以检测当前网页中的一些资源文件&#xff0c;可设置嗅探的…...

2.4Mybatis——缓存机制

2.4Mybatis——缓存机制 缓存配置一二级缓存一级缓存二级缓存 合集总览&#xff1a;Mybatis框架梳理 讲真&#xff0c;Mybatis缓存这块的记忆已经模糊了。刚好此时写测试用例出现一个BUG&#xff0c;就以这个问题作为切入点来梳理一下。 Testpublic void test(){Address ad…...

移动技术开发:文件的读取

1 实验名称 文件的读写 2 实验目的 掌握Android中读写文件的实现方法。 3 实验源代码 布局文件代码&#xff1a; <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas.android.com/apk/res/android&quo…...

Linux 中的 Makefile 伪目标详解

在 Linux 环境中&#xff0c;Makefile 是构建项目的重要工具&#xff0c;它通过定义规则&#xff0c;指导 make 工具如何编译和链接程序。通常我们会在 Makefile 中定义目标&#xff08;target&#xff09;&#xff0c;这些目标通常对应文件名。然而&#xff0c;有一种特殊类型…...

Java基础(中)

变量 成员变量与局部变量的区别 语法形式&#xff1a;从语法形式上看&#xff0c;成员变量是属于类的&#xff0c;而局部变量是在代码块或方法中定义的变量或是方法的参数&#xff1b;成员变量可以被 public,private,static 等修饰符所修饰&#xff0c;而局部变量不能被访问控…...

Leetcode热题100-200 岛屿数量

Leetcode热题100-200 岛屿数量 1. 题目描述2. 代码实现1. dfs算法2. bfs算法 1. 题目描述 200 岛屿数量 2. 代码实现 1. dfs算法 class Solution { public:int numIslands(vector<vector<char>>& grid) {int m grid.size(), n grid[0].size();int res 0…...

大数据新视界 --大数据大厂之 GraphQL 在大数据查询中的创新应用:优化数据获取效率

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…...

swift使用代码结构解析

多模态模型的训练llamafactory也可以训练&#xff0c;但是总的来说&#xff0c;llamafactory对多模态模型的支持还是不太多&#xff0c;ms-swift支持的多模态模型更多&#xff0c;因此有时候去找框架是否够支持相应的模型时会有所困难&#xff0c;所以对这些框架的代码也要稍微…...

五、Python基础语法(程序的输入和输出)

一、输入 输入&#xff1a;输入就是获取键盘输入的数据&#xff0c;使用input()函数。代码会从上往下执行&#xff0c;当遇到input()函数&#xff0c;就会暂停执行&#xff0c;输入内容后&#xff0c;敲回车键&#xff0c;表示本次的输入结束。input函数得到的数据类型都是字符…...

【C语言】常见概念

文章目录 库函数关键字字符和ASCll编码字符串与\0转义字符语句和语句分类注释 库函数 为了不再重复实现常见的代码&#xff0c;让程序员提升开发效率&#xff0c;C语言标准规定了一组函数&#xff0c;这些函数再由不同的编译器厂商根据标准进行实现&#xff0c;提供给程序员使…...

Electron应用创建和打包

一、创建项目目录 创建NodeJs项目目录&#xff0c;项目有关的文件、依赖包都将在本目录创建和安装。 mkdir hello_electron & cd hello_electronCMD执行以上命令将在用户目录下创建hello_electron并进入该目录。当然也可以手动在任何地方创建目录&#xff0c;cmd中cd 路径…...

代码随想录算法训练营第五六天| 99. 岛屿数量 100. 岛屿的最大面积

今日任务 99. 岛屿数量 深度搜搜 99. 岛屿数量 广度搜索 100. 岛屿的最大面积 99. 岛屿数量 题目链接&#xff1a; 99. 岛屿数量 import java.util.Scanner;public class Main {public static int[][] dir {{0, 1},{1, 0},{-1, 0},{0, -1}};public static void dfs(boolean…...

图解 微信开发者工具 小程序源码 调试、断点标记方法 , 微信小程序调试器,真机调试断点调试方法,小程序网络API请求调试方法 总结

在我们使用微信开发者工具进行微信小程序开发的时候&#xff0c;在这个微信开发者工具的代码编辑框里面我们是无法像使用vscode, idea等IDE工具时那样直接对代码打断点进行调试&#xff0c; 原因是小程序实际上他就是一个web浏览器应用的包装, 在其内部使用的还是类似chrome的…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道

文/法律实务观察组 在债务重组领域&#xff0c;专业机构的核心价值不仅在于减轻债务数字&#xff0c;更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明&#xff0c;合法债务优化需同步实现三重平衡&#xff1a; 法律刚性&#xff08;债…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...