秋招算法备战第28天 | 93.复原IP地址、78.子集、90.子集II
93. 复原 IP 地址 - 力扣(LeetCode)
这个问题可以通过深度优先搜索(DFS)的方法来解决。我们要做的就是在字符串的每个可能位置插入点,然后检查生成的每一部分是否在 0-255 的范围内,以及是否没有前导零(除非这一部分本身就是零)。以下是解决这个问题的 Python 代码示例。
def restoreIpAddresses(s):def dfs(s, part, path, res):if part == 4:if s == "":res.append(path[:-1])returnfor i in range(1, 4):if i <= len(s):if int(s[:i]) <= 255:dfs(s[i:], part + 1, path + s[:i] + ".", res)if s[0] == '0':breakres = []dfs(s, 0, "", res)return res# Test the function
s = "25525511135"
print(restoreIpAddresses(s))
上述代码的运行结果应该是 ['255.255.11.135', '255.255.111.35'],这是字符串 “25525511135” 可能形成的所有有效 IP 地址。
注意,以上代码默认你正在使用 Python 3.如果你正在使用其他语言,转换这段代码时需要保持算法的主体思想不变,但可能需要进行一些语法或者函数的调整。
下面是代码随想录的参考代码
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. 子集 - 力扣(LeetCode)
这是一个经典的回溯问题。基本思路是,从空子集开始,然后每次向子集中添加一个新的元素,创建一个新的子集,直到所有元素都被考虑过。对于包含n个元素的集合,其幂集包含2^n个元素,因为每个元素都可以在子集中出现或不出现。
在Python中,可以使用深度优先搜索的方式实现。下面是一个可能的解决方案:
def subsets(nums):def backtrack(first = 0, curr = []):# 如果当前组合达到了有效长度if len(curr) == k:output.append(curr[:])returnfor i in range(first, n):# 添加 nums[i] 进入当前组合curr.append(nums[i])# 使用下一个整数来完成组合backtrack(i + 1, curr)# 回溯,移除 nums[i] 从当前组合curr.pop()output = []n = len(nums)for k in range(n + 1):# 对于从0到n个数字的所有可能组合backtrack()return output
这个函数首先定义了一个递归的回溯函数,用于生成所有长度为k的可能组合。然后,函数为每个可能的组合长度(从0到n)调用了回溯函数。在回溯函数中,我们遍历nums中的所有元素,并在每一步中,都将当前元素添加到当前组合中,然后调用回溯函数来完成剩余的组合。最后,我们从当前组合中移除当前元素,以便在下一次迭代中尝试下一个元素。
90. 子集 II - 力扣(LeetCode)
这是一个带有重复元素的子集问题,它可以通过一种叫做"回溯法"的算法来解决。关键是需要在添加子集时检查这个子集是否已经在结果中了。
首先,为了方便比较,我们可以将输入数组排序。然后,我们使用递归函数backtrack来生成所有可能的子集。在backtrack中,我们添加当前的子集到结果中,然后对于当前位置之后的每一个元素,我们尝试把它添加到子集中,并递归调用backtrack。
这里是Python的实现:
def subsetsWithDup(nums):def backtrack(start, end, tmp):res.append(tmp[:])for i in range(start, end):if i > start and nums[i] == nums[i-1]: # 处理重复的元素continuetmp.append(nums[i])backtrack(i + 1, end, tmp)tmp.pop()nums.sort()res = []backtrack(0, len(nums), [])return res
在这个代码中,我们首先对nums进行排序,然后定义了回溯函数backtrack,最后调用了backtrack来生成所有的子集。在backtrack中,首先我们添加了当前的子集到结果中,然后从start位置开始,遍历到数组的末尾。对于每一个位置,我们首先检查是否有重复的元素,如果有就跳过。然后我们把当前元素加到当前的子集中,调用backtrack生成包含这个元素的所有子集,然后再把这个元素从子集中移除。通过这种方式,我们能够生成所有的子集,并且避免了重复的子集。
总结
Summary
🔍 93. 复原 IP 地址 - 力扣(LeetCode)
这个问题可以通过深度优先搜索(DFS)的方法来解决。我们要做的就是在字符串的每个可能位置插入点,然后检查生成的每一部分是否在 0-255 的范围内,以及是否没有前导零(除非这一部分本身就是零)。
🔍 78. 子集 - 力扣(LeetCode)
这是一个经典的回溯问题。基本思路是,从空子集开始,然后每次向子集中添加一个新的元素,创建一个新的子集,直到所有元素都被考虑过。对于包含n个元素的集合,其幂集包含2^n个元素,因为每个元素都可以在子集中出现或不出现。在Python中,可以使用深度优先搜索的方式实现。
🔍 90. 子集 II - 力扣(LeetCode)
这是一个带有重复元素的子集问题,它可以通过一种叫做"回溯法"的算法来解决。关键是需要在添加子集时检查这个子集是否已经在结果中了。首先,为了方便比较,我们可以将输入数组排序。然后,我们使用递归函数backtrack来生成所有可能的子集。
Facts
- [💻 Python] 使用深度优先搜索(DFS)的方法来解决复原 IP 地址问题,逐个位置插入点,检查生成的每一部分是否在 0-255 的范围内,且没有前导零(除非该部分本身就是零)。
- [💻 Python] 经典回溯问题,找出集合的所有子集。子集的幂集包含2^n个元素,每个元素可以在子集中出现或不出现。
- [💻 Python] 带有重复元素的子集问题,使用"回溯法"算法解决。需要检查添加的子集是否已经在结果中,可以通过排序数组来避免重复。
相关文章:
秋招算法备战第28天 | 93.复原IP地址、78.子集、90.子集II
93. 复原 IP 地址 - 力扣(LeetCode) 这个问题可以通过深度优先搜索(DFS)的方法来解决。我们要做的就是在字符串的每个可能位置插入点,然后检查生成的每一部分是否在 0-255 的范围内,以及是否没有前导零(除非这一部分本…...
Mongodb空间索引的使用以及与Django的对接
Mongodb的空间索引 Mongodb数据库大家都非常熟悉,是一个基于分布式文件存储的开源数据库系统,在高负载的情况下,添加更多的节点,可以保证服务器性能,数据结构由键值(key>value)对组成。MongoDB 文档类似于 JSON 对…...
Windows安装MySQL数据库
MySQL数据库安装 MySQL下载 下载地址:https://dev.mysql.com/downloads/mysql/ 可以选择下载msi或zip,以下为zip模式安装步骤 下载了mysql的zip安装包之后解压即可; Windows安装步骤 初始化MySQL,并记录生成的用户密码root的随机…...
聊聊函数式编程中的“式”
当谈到函数式编程的“式”时,通常指的是函数的组合、转换和应用,以及处理数据的方式和风格。在函数式编程中,式是用来构建程序逻辑的基本单元。 下面更详细解释函数式编程中的几个关键式: 函数的组合: 函数式编程中…...
ubuntu目录分析
在Ubuntu根目录下,以下是一些常见文件夹的含义: /bin:存放可执行文件,包含一些基本的命令和工具。 /boot:存放启动时所需的文件,如内核和引导加载程序。 /dev:包含设备文件,用于与硬…...
Python 进阶(三):正则表达式(re 模块)
❤️ 博客主页:水滴技术 🌸 订阅专栏:Python 入门核心技术 🚀 支持水滴:点赞👍 收藏⭐ 留言💬 文章目录 1. 导入re模块2. re模块中的常用函数2.1 re.search()2.2 re.findall()2.3 re.sub()2.4…...
Vue2 第六节 key的作用与原理
(1)虚拟DOM (2)v-for中的key的作用 一.虚拟DOM 1.虚拟DOM就是内存中的数据 2.原生的JS没有虚拟DOM: 如果新的数据和原来的数据有重复数据,不会在原来的基础上新加数据,而是重新生成一份 3. Vue会有虚拟…...
React之组件的生命周期
React之组件的生命周期 一、概述二、整体说明三、挂载阶段四、更新阶段五、卸载阶段 一、概述 生命周期:一个事务从创建到最后消亡经历的整个过程组件的生命周期:组件从被创建到挂载到页面中运行,再到组件不用时卸载的过程意义:理解组件的生…...
linux -网络编程-多线程并发服务器
目录 1.三次握手和四次挥手 2 滑动窗口 3 函数封装思想 4 高并发服务器 学习目标: 掌握三次握手建立连接过程掌握四次握手关闭连接的过程掌握滑动窗口的概念掌握错误处理函数封装实现多进程并发服务器实现多线程并发服务器 1.三次握手和四次挥手 思考: 为什么…...
Golang之路---02 基础语法——字典
字典 字典(Map 类型),是由若干个 key:value 这样的键值对映射组合在一起的数据结构。 key 不能是切片,不能是字典,不能是函数。 字典初始化 方式:map[KEY_TYPE]VALUE_TYPE //1.var map1 map[string]int…...
Pytorch(三)
一、经典网络架构图像分类模型 数据预处理部分: 数据增强数据预处理DataLoader模块直接读取batch数据 网络模块设置: 加载预训练模型,torchvision中有很多经典网络架构,可以直接调用注意别人训练好的任务跟咱们的并不完全一样,需要把最后…...
Linux——进程控制
目录 1. 进程创建 1.1 fork函数 1.2 fork系统调用内部宏观流程 1.3 fork后子进程执行位置分析 1.4 fork后共享代码分析 1.5 fork返回值 1.6 写时拷贝 1.7 fork常规用法 1.8 fork调用失败的原因 2.进程终止 2.1 进程退出场景 2.2 strerror函数—返回描述错误号的字符…...
剑指 Offer 59 - I. 滑动窗口的最大值 / LeetCode 239. 滑动窗口最大值(优先队列 / 单调队列)
题目: 链接:剑指 Offer 59 - I. 滑动窗口的最大值;LeetCode 239. 滑动窗口最大值 难度:困难 下一篇:剑指 Offer 59 - II. 队列的最大值(单调队列) 给你一个整数数组 nums,有一个大…...
【Linux后端服务器开发】IP协议
目录 一、IP协议概述 二、协议头格式 三、网段划分 四、IP地址的数量限制 五、路由 六、分片和组装 一、IP协议概述 主机:配有IP地址,但是不进行路由控制的设备 路由器:即配有IP地址,又能进行路由控制 节点:主…...
React组件进阶之children属性,props校验与默认值以及静态属性static
React组件进阶之children属性,props校验与默认值以及静态属性static 一、children属性二、props校验2.1 props说明2.2 prop-types的安装2.3 props校验规则2.4 props默认值 三、静态属性static 一、children属性 children 属性:表示该组件的子节点,只要组…...
ceph集群中RBD的性能测试、性能调优
文章目录 rados benchrbd bench-write测试工具Fio测试ceph rbd块设备的iops性能测试ceph rbd块设备的带宽测试ceph rbd块设备的延迟 性能调优 rados bench 参考:https://blog.csdn.net/Micha_Lu/article/details/126490260 rados bench为ceph自带的基准测试工具&am…...
texshop mac中文版-TeXShop for Mac(Latex编辑预览工具)
texshop for mac是一款可以在苹果电脑MAC OS平台上使用的非常不错的Mac应用软件,texshop for mac是一个非常有用的工具,广泛使用在数学,计算机科学,物理学,经济学等领域的合作,这些程序的标准tetex分布特产…...
简单认识redis高可用实现方法
文章目录 一、redis群集三种模式二、 Redis 主从复制1、简介2、作用:3、流程:4.配置主从复制 三、Redis 哨兵模式1、简介2、原理:3、作用:4、哨兵结构由两部分组成,哨兵节点和数据节点:5、故障转移机制:6、…...
搭建git服务器
1.创建linux账户,创建文件 adduser git passwd gitpsw su git pwd cd ~/ mkdir .ssh cd ~/.ssh touch authorized_keys 2.特别重要(单独起一行),给文件设权限 chmod 700 /home/git/.ssh chmod 600 /home/git/.ssh/authorized_keys 3.本地生产密钥并把…...
线程中断机制
如何中断一个线程? 首先一个线程不应该由其他线程来强制中断或者停止,而是应该由线程自己自行停止。所以我们看到线程的stop()、resume()、suspend()等方法已经被标记为过时了。 其次在java中没有办法立即停止一个线程,然而停止线程显得尤为重…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
在 Spring Boot 项目里,MYSQL中json类型字段使用
前言: 因为程序特殊需求导致,需要mysql数据库存储json类型数据,因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...
ZYNQ学习记录FPGA(一)ZYNQ简介
一、知识准备 1.一些术语,缩写和概念: 1)ZYNQ全称:ZYNQ7000 All Pgrammable SoC 2)SoC:system on chips(片上系统),对比集成电路的SoB(system on board) 3)ARM:处理器…...
【向量库】Weaviate 搜索与索引技术:从基础概念到性能优化
文章目录 零、概述一、搜索技术分类1. 向量搜索:捕捉语义的智能检索2. 关键字搜索:精确匹配的传统方案3. 混合搜索:语义与精确的双重保障 二、向量检索技术分类1. HNSW索引:大规模数据的高效引擎2. Flat索引:小规模数据…...
