每日一题——将数字字符串转化为IP地址
将数字字符串转化为IP地址
- 题目描述
- 解题思路
- 回溯法
- 步骤分解
- 代码实现
- 全局变量
- 有效性验证函数
- 回溯函数
- 主函数
- 完整代码
- 复杂度分析
- 关键点说明
- 总结
这题难度还挺大的,整体上实现并不容易。建议参考视频
和https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html#%E6%80%9D%E8%B7%AF
题目描述
给定一个仅包含数字的字符串,将其转换为所有可能的有效IP地址形式。有效的IP地址由四个整数(0到255之间)构成,各部分用.
分隔,且不能有前导零(除非该段本身为0)。
示例:
-
输入:
"25525522135"
输出:["255.255.22.135", "255.255.221.35"]
-
输入:
"000256"
输出:[]
(因256
超过255)
解题思路
回溯法
- 分割逻辑:IP地址由四段组成,需在字符串中找到三个分割点将字符串分为四段。
- 有效性检查:每段必须满足:
- 值在
0
到255
之间; - 无前导零(除非段本身为
0
); - 仅包含数字。
- 值在
- 递归终止条件:当分割点数量为3时,检查最后一段是否有效。
- 剪枝:若当前分割无效,跳过后续尝试。
步骤分解
- 回溯函数:记录当前分割点位置和已分割段数。
- 有效性验证:检查子串是否合法。
- 生成结果:将合法分割组合成IP地址格式。
代码实现
全局变量
char** result; // 存储结果数组
int resultTop; // 结果数组当前索引
int segments[3]; // 记录三个分割点的位置
有效性验证函数
int isValid(char* s, int start, int end) {if (start > end) return 0;if (s[start] == '0' && start != end) return 0; // 前导零无效int num = 0;for (int i = start; i <= end; i++) {if (s[i] < '0' || s[i] > '9') return 0; // 非数字字符num = num * 10 + (s[i] - '0');if (num > 255) return 0; // 超过255}return 1;
}
回溯函数
void backTracking(char* s, int startIndex, int pointNum) {if (pointNum == 3) { // 分割点已满3个// 检查最后一段是否有效if (isValid(s, startIndex, strlen(s) - 1)) {char* temp = (char*)malloc(strlen(s) + 4); // 分配新字符串内存int count = 0, count1 = 0;for (int j = 0; j < strlen(s); j++) {temp[count++] = s[j];// 在分割点后插入'.'if (count1 < 3 && j == segments[count1]) {temp[count++] = '.';count1++;}}temp[count] = '\0';// 扩展结果数组并保存result = (char**)realloc(result, sizeof(char*) * (resultTop + 1));result[resultTop++] = temp;}return;}for (int i = startIndex; i < strlen(s); i++) {if (isValid(s, startIndex, i)) { // 当前分割有效segments[pointNum] = i; // 记录分割点backTracking(s, i + 1, pointNum + 1); // 递归下一段} else break; // 无效分割,剪枝}
}
主函数
char** restoreIpAddresses(char* s, int* returnSize) {result = (char**)malloc(0);resultTop = 0;backTracking(s, 0, 0);*returnSize = resultTop;return result;
}
完整代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>char** result; // 用于存储所有可能的IP地址
int resultTop; // 当前result数组中的IP地址数量
// 记录应该加入'.'的位置,数组大小为3,因为IP地址有3个分隔点
int segments[3];// 检查字符串是否为合法的IP段
// start和end分别表示当前检查的子字符串的起始和结束位置
int isValid(char* s, int start, int end) {// 如果起始位置大于结束位置,说明子字符串无效if (start > end) {return 0;}// 如果子字符串以0开头且长度大于1,则该子字符串无效(例如01、001等)if (s[start] == '0' && start != end) {return false;}int num = 0; // 用于存储子字符串转换后的数字值// 遍历子字符串,检查是否为合法数字for (int i = start; i <= end; i++) {// 如果字符不是数字,则子字符串无效if (s[i] > '9' || s[i] < '0') {return false;}num = num * 10 + (s[i] - '0'); // 将字符转换为数字并累加// 如果数字大于255,则子字符串无效if (num > 255) {return false;}}return true; // 如果通过所有检查,则子字符串有效
}// 回溯函数,用于生成所有可能的IP地址
// startIndex表示当前处理的字符串起始位置,pointNum表示当前已放置的'.'数量
void backTracking(char* s, int startIndex, int pointNum) {// 如果已放置3个'.',说明已经生成了一个完整的IP地址if (pointNum == 3) {// 检查最后一段字符串是否合法if (isValid(s, startIndex, strlen(s) - 1)) {// 为存储当前IP地址分配内存char* tempString = (char*)malloc(sizeof(char) * (strlen(s) + 4));int count = 0; // 用于记录tempString的当前索引int count1 = 0; // 用于记录已使用的'.'数量// 遍历字符串,根据segments数组插入'.'生成IP地址for (int j = 0; j < strlen(s); j++) {tempString[count++] = s[j]; // 将当前字符添加到tempString// 如果当前索引是'.'的位置,则插入'.'(最多插入3个)if (count1 < 3 && j == segments[count1]) {tempString[count++] = '.';count1++;}}tempString[count] = '\0'; // 添加字符串结束符// 扩容result数组以存储新的IP地址result = (char**)realloc(result, sizeof(char*) * (resultTop + 1));result[resultTop++] = tempString; // 将新生成的IP地址加入result}return;}// 遍历字符串,尝试将当前子字符串作为IP地址的一部分for (int i = startIndex; i < strlen(s); i++) {// 检查当前子字符串是否合法if (isValid(s, startIndex, i)) {// 记录当前'.'的位置segments[pointNum] = i;// 递归处理下一段字符串backTracking(s, i + 1, pointNum + 1);} else {// 如果当前子字符串不合法,则停止当前分支的搜索break;}}
}// 主函数,用于恢复IP地址
char** restoreIpAddresses(char* s, int* returnSize) {// 初始化result数组result = (char**)malloc(0);resultTop = 0;// 开始回溯搜索backTracking(s, 0, 0);*returnSize = resultTop; // 设置返回的IP地址数量return result;
}
复杂度分析
- 时间复杂度:O(n!),回溯尝试所有可能分割方式。
- 空间复杂度:O(n!),存储所有可能的IP地址。
关键点说明
- 回溯终止条件:当分割点数为3时,验证最后一段。
- 剪枝优化:遇到无效分割时立即终止当前循环。
- 动态内存管理:结果字符串需动态分配,并适时扩展结果数组。
总结
通过回溯法遍历所有可能的分割方式,结合有效性剪枝,可高效生成所有合法IP地址。注意处理边界条件(如前导零、数值范围)和内存管理,确保程序健壮性。
相关文章:
每日一题——将数字字符串转化为IP地址
将数字字符串转化为IP地址 题目描述解题思路回溯法步骤分解 代码实现全局变量有效性验证函数回溯函数主函数完整代码 复杂度分析关键点说明总结 这题难度还挺大的,整体上实现并不容易。建议参考视频 和https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%…...
2013年下半年软件设计师上午题考察知识点及其详细解释(附真题及答案解析)
以下是2013年下半年软件设计师上午题的所有题目(从第1题到第75题)的总结,按顺序列出每道题目的考察知识点及其详细解释,供考生背诵记忆: 1. Cache与主存的地址映像 知识点:存储管理解释:Cache与…...
实现可拖拽的 Ant Design Modal 并保持下层 HTML 可操作性
前言 在开发复杂的前端界面时,我们常常需要一个可拖拽的弹窗(Modal),同时又希望用户能够在弹窗打开的情况下操作下层的内容。Ant Design 的 Modal 组件提供了强大的功能,但默认情况下,弹窗会覆盖整个页面&…...
unity学习43:子状态机 sub-state machine
目录 1sub-state machine子状态机 1.1 创建 sub-state machine 1.2 sub-state machine 内容 1.3 子状态机的应用 2 子状态机不同于blend tree的嵌套 3 应用例子:若角色拿不同武器的动画设计,可以使用2种方法 3.1 在1个图层layer里,使用…...
HTML之JavaScript DOM(document)编程处理事件
HTML之JavaScript DOM(document)编程处理事件 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"…...
线性模型 - Logistic 回归
Logistic 回归(Logistic Regression,LR)是一种常用的处理二分类问题的 线性模型。 Logistic 回归是一种用于二分类问题的统计模型,它通过将输入特征的线性组合映射到一个概率值来进行分类决策。 Logistic回归是机器学习中最经典的分类算法之一…...
分割 学习笔记cvpr2024
目录 LiteMedSam 模型37m LightM-Unet 500 str 依赖项: MLWnet 73 star memsam 340M 126 star LiteMedSam 模型37m https://github.com/bowang-lab/MedSAM/blob/LiteMedSAM/README.md LightM-Unet 500 str https://github.com/MrBlankness/LightM-UNet/blob model = Li…...
ShenNiusModularity项目源码学习(9:项目结构)
ShenNiusModularity源码主要有11个project(其实还有officialweb、test两个文件夹,大致有4、5个project,但看着跟主要项目代码没太大关系,暂时不管),这11个project的依赖关系如下图所示,其中最下…...
【复现DeepSeek-R1之Open R1实战】系列6:GRPO源码逐行深度解析(上)
目录 4 GRPO源码分析4.1 数据类 GRPOScriptArguments4.2 系统提示字符串 SYSTEM_PROMPT4.3 奖励函数4.3.1 accuracy_reward函数4.3.2 verify函数4.3.3 format_reward函数 4.4 将数据集格式化为对话形式4.5 初始化GRPO Trainer 【复现DeepSeek-R1之Open R1实战】系列3࿱…...
【LangChain实践开发】如何对大模型I/O封装?
LangChain 的核心组件 模型 I/O 封装 LLMs:大语言模型Chat Models:一般基于 LLMs,但按对话结构重新封装PromptTemple:提示词模板OutputParser:解析输出 数据连接封装 Document Loaders:各种格式文件的加载…...
LangChain4j
LangChain4j 是一个基于 Java 的框架,旨在简化与大型语言模型(LLMs)的集成和应用开发。它类似于 Python 的 LangChain 框架,但专为 Java 开发者设计,提供了构建基于 LLM 的应用程序所需的工具和组件。 主要功能 LLM …...
如何系统成为高级Qt工程师?
要系统性地成为高级Qt工程师,需要从基础到进阶逐步构建知识体系,并结合实战经验、源码分析和架构设计能力的提升。以下是分阶段的系统性学习路径和建议: 一、夯实基础阶段 C++深度掌握 精通C++11/14/17特性(智能指针、lambda、移动语义等)理解面向对象设计、设计模式(如观…...
LLM 架构
LLM 分类 : 自编码模型 (encoder) : 代表模型 : BERT自回归模型 (decoder) : 代表模型 : GPT序列到序列模型 (encoder-decoder) : 代表模型 : T5 自编码模型 (AutoEncoder model , AE) 代表模型 : BERT (Bidirectional Encoder Representation from Transformers)特点 : Enc…...
MVTEC数据集笔记
前言 网上的博客只有从论文里摘出的介绍,没有数据集文件详细的样子,下载数据集之后,对数据集具体的构成做一个补充的笔记。 下载链接:https://ai-studio-online.bj.bcebos.com/v1/7d4a3cf558254bbaaf4778ea336cb14ed8bbb96a7f2a…...
[算法学习笔记]1. 枚举与暴力
一、枚举算法 定义 枚举是基于已有知识来猜测答案的问题求解策略。即在已知可能答案的范围内,通过逐一尝试寻找符合条件的解。 2. 核心思想 穷举验证:对可能答案集合中的每一个元素进行尝试终止条件:找到满足条件的解,或遍历完…...
javacv将mp4视频切分为m3u8视频并播放
学习链接 ffmpeg-demo 当前对应的 gitee代码 Spring boot视频播放(解决MP4大文件无法播放),整合ffmpeg,用m3u8切片播放。 springboot 通过javaCV 实现mp4转m3u8 上传oss 如何保护会员或付费视频?优酷是怎么做的? - HLS 流媒体加密 ffmpe…...
docker 进阶命令(基于Ubuntu)
数据卷 Volume: 目录映射, 目录挂载 匿名绑定: 匿名绑定的 volume 在容器删除的时候, 数据卷也会被删除, 匿名绑定是不能做到持久化的, 地址一般是 /var/lib/docker/volumes/xxxxx/_data 绑定卷时修改宿主机的目录或文件, 容器内的数据也会同步修改, 反之亦然 # 查看所有 vo…...
鸿蒙(HarmonyOS)开发学习路线指南:从零到实战
随着鸿蒙生态的快速发展,HarmonyOS 已成为物联网时代的重要开发平台。其分布式架构和“一次开发、多端部署”的理念吸引了大量开发者。本文将从零开始梳理鸿蒙开发的学习路径,帮助开发者高效掌握核心技能。 一、学习路线概览 总目标:掌握鸿蒙…...
小白win10安装并配置yt-dlp
需要yt-dlp和ffmpeg 注意存放路径最好都是全英文 win10安装并配置yt-dlp 一、下载1.下载yt-dlp2. fffmpeg下载 二、配置环境三、cmd操作四、yt-dlp下视频操作 一、下载 1.下载yt-dlp yt-dlp地址 找到win的压缩包点下载,并解压 2. fffmpeg下载 ffmpeg官方下载 …...
CUBEAI详细使用教程(STM32运行神经网络)---以手写识别为例
系列文章目录 文章目录 系列文章目录前言一、CUBEMX配置步骤二、模型结构及模型存储方式三、常用API函数1.ai_(name)_create()2.ai_(name)_init3.ai_(name)_create_and_init()3.ai_(name)_run()官方提供的示例代码 四、如何获取官方开发文档五、手写识别案例 前言 实验效果&am…...
[NOIP 1998 提高组] 拼数
https://www.luogu.com.cn/problem/P1012 将每个数用字符串的形式读进来,对于任意两个数 x x x, y y y,如果 x y > y x xy>yx xy>yx,对最后的答案来说, x x x一定排在 y y y的前面。 简单证明:假设最后的…...
PHP Web 开发基础
PHP 学习资料 PHP 学习资料 PHP 学习资料 在 PHP Web 开发领域,掌握一些基础概念和技术是构建功能强大、用户体验良好的 Web 应用的基石。接下来,我们将深入探讨 HTTP 协议、表单处理、Cookie 和 Session 的管理、URL 处理等关键内容。 一、HTTP 协议…...
MME-CoT:专为评估大型多模态模型CoT推理能力的基准测试。涵盖了数学、科学、OCR、逻辑、时空和一般场景6个领域。
2025-02-09 ,由CUHK MMLab、CUHK MulLab、字节跳动、、东北大学等机构联合发布MME-CoT数据集,该数据集目的评估大型多模态模型(LMMs)中的思维链(CoT)推理能力,涵盖数学、科学、OCR、逻辑、时空和…...
HDFS应用-后端存储cephfs-java-API
HDFS(Hadoop Distribute FileSystem)是一个适合运行在通用硬件之上,具备高度容错特性,支持高吞吐量数据访问的分布式文件系统,非常适合大规模数据集应用。 HDFS适用于如下场景: • 处理海量数据(TB或PB级别以上) • 需要很高的吞吐量 • 需要高可靠性 • 需要很好的可扩…...
A与B组件自动对齐与组装,无映射直接补偿。
网上针对组装的从视觉到控制动作,要不就是收费,要不就是简单介绍。这么详细的比较难找~ 手下留情,不喜勿喷! Show time~ 分步解决方案: 标定阶段(Calibration) 9点张氏标定(每个位置A1、A2、B1、B2): 使用机械手在相机视野内沿Z字形路径移动,覆盖9个点(XY方…...
SQL知识体系
SQL复习 MySQL SQL介绍 SQL SQL的全拼是什么? SQL全拼:Structured Query Language,也叫结构化查询语言。 SQL92和SQL99有什么区别呢? SQL92和SQL99分别代表了92年和99年颁布的SQL标准。 在 SQL92 中采用(ÿ…...
编译安装php
前置准备 这里的可能不全,每个人安装的模块不一致,依赖也不不相同,按实际情况调整 yum install libxml2 -y yum install libxml2-devel -y yum install openssl-devel -y yum install sqlite-devel -y yum install libcurl-devel -yyum ins…...
【分果果——DP(困难)】
题目 分析 分果果题解参考,下面是补充https://blog.csdn.net/AC__dream/article/details/129431299 关于状态 设f[i][j][k]表示第i个人取到的最后一个糖果编号是j,第i-1个人取到的最后一个糖果编号小于等于k时的最大重量的最小值 关于转移方程 关于 j …...
利用ffplay播放udp组播视频流
ffplay -fs -fflags nobuffer -flags low_delay -analyzeduration 0 -probesize 32 -framedrop -sync ext -strict experimental udp://224.1.1.1:5001 -fs : 全屏显示 -fflags nobuffer : 禁用输入缓冲(减少100-200ms缓冲延迟) -an…...
C++中变量与容器的默认初始化:0的奥秘
在C编程的世界里,初始化是一个至关重要的概念。它决定了变量或容器在程序开始执行时的初始状态。然而,对于不同的数据类型和容器,C标准对于默认初始化的行为有着不同的规定。本文将深入探讨C中变量与容器的默认初始化规则,特别是关…...
VScode内接入deepseek包过程(本地部署版包会)
目录 1. 首先得有vscode软件 2. 在我们的电脑本地已经部署了ollama,我将以qwen作为实验例子 3. 在vscode上的扩展商店下载continue 4. 下载完成后,依次点击添加模型 5. 在这里可以添加,各种各样的模型,选择我们的ollama 6. 选…...
spark
阶段性 阶段一: 单机时代 阶段二: 大数据时代-分布式处理 阶段三: 实时大数据时代 hadoop慢因为她的计算结果保存在磁盘 处理在spark中可解决属于内存 Hadoop特点: 高可靠性 高拓展性 高效性 高容错性...
蓝桥杯---排序数组(leetcode第912题)
文章目录 1.题目重述2.思路分析3.代码解释 1.题目重述 题目的要求是不使用库函数或者是其他的内置的函数(就是已经实现好的函数),也就是这个排序的逻辑需要我们自己进行实现; 2.思路分析 其实这个例子也是很容易理解的ÿ…...
【Javascript Day18】
目录 标签事件绑定的属性参数 阻止默认行为 dialog的实现及组织冒泡(捕获)传递 基于冒泡的事件委托 键盘事件的事件源对象信息 JS的自动触发操作 标签事件绑定的属性参数 <!-- 标签上的事件绑定,事件源对象通过 关键字event传递 --…...
轻量级C通用库Klib解读 —— kalloc
前言 Klib是一个独立的轻量级c通用库,里面大多数组件除了C标准库外不包含外部库,想用对应组件直接拷贝对应文件即可使用。 该库致力于高效和较小的内存占用,其中部分组件(如khash、kbtree、ksort、kvec),无…...
认识HTML的标签结构
一、HTML的基本概念 1.什么是HTML? ①HTML是描述网页的一种标记语言,也被称为超文本标记语言【并不是一种编程语言】 ②HTML包含了HTML标签和文本内容 ③HTML文档也称为web页面 2.HTML的标签 HTML的标签通常成对出现,HTML文档由标签和受…...
C语言 实现一个比较两个整型的函数 / qsort的使用 /qsort排序结构体
一、qsort的一般使用方法 int cmp_int(const void* e1, const void* e2) {return *(int*)e1 - *(int*)e2; } // //使用qsort对数组进行排序,升序 void test1() {int arr[] { 9,8,7,6,5,4,3,2,1,0 };int sz sizeof(arr) / sizeof(arr[0]);//bubble_sort(arr, sz);…...
Arcmap python环境安装sklearn
Arcmap自带的环境为Python2.7,默认安装目录为C:\Python27\ArcGIS10.7 直接安装sklearn会发生兼容性问题,且默认环境不包括pip,因此需要先安装pip 下载 get-pip.py 访问 https://bootstrap.pypa.io/pip/2.7/get-pip.py 并下载 get-pip.py。运…...
FastAdmin后端列表导入表格数据
后台添加数据的时候增加通过表格导入功能 如下图index.html页面增加导入和模板下载按钮代码如下 <div class"panel panel-default panel-intro">{:build_heading()}<div class"panel-body"><div id"myTabContent" class"ta…...
R语言用逻辑回归贝叶斯层次对本垒打数据与心脏移植数据后验预测检验模拟推断及先验影响分析|附数据代码...
全文链接:https://tecdat.cn/?p40152 在统计学领域中,层次建模是一种极为强大且实用的工具。它能够巧妙地处理复杂的数据结构,通过分层的方式对数据进行建模。在贝叶斯统计的框架内,层次建模优势尽显,其可以有效地融合…...
Python基于自然语言处理技术的新闻文本分类系统【附源码、文档说明】
博主介绍:✌Java老徐、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取源码联系🍅 👇🏻 精彩专栏推荐订阅👇&…...
mybatis存储过程返回list
在MyBatis中调用存储过程并返回列表(List)通常涉及以下几个步骤: 定义存储过程:首先,在数据库中定义存储过程,并确保它返回结果集。配置MyBatis映射文件:在MyBatis的映射文件中配置调用存储过程…...
Unity项目实战-订阅者发布者模式
实战订阅者发布者模式详解 下面实例是一个射击类游戏,玩家可以切换枪支,最初的设计如下 public class Player:MonoBehaviour {//......省略代码逻辑//我们以及配置好了Scroll的输入,并配置了Scroll的输入事件,当玩家滚动鼠标滚轮…...
长文档处理痛点:GPT-4 Turbo引文提取优化策略与替代方案讨论
引言 随着GPT-4 Turbo的发布,其支持的128K上下文窗口(约300页文本)被视为处理长文本的突破性升级。然而,实际应用中,用户发现模型在提取长文档中的引文时存在显著缺陷:文档前三分之一的引文数量远多于中间…...
Deepseek 万能提问公式:高效获取精准答案
### **Deepseek 万能提问公式:高效获取精准答案** 在使用 Deepseek 或其他 AI 工具时,提问的质量直接决定了答案的精准度和实用性。以下是一个万能的提问公式回答: --- ### **1. 明确背景(Context)** - **作用**…...
Ubuntu中离线安装Docker
Ubuntu中离线安装Docker 前言 本教程将详细介绍如何在 Ubuntu 22.04 系统上,通过 .deb 包离线安装 Docker CE、Docker CE CLI 和 Docker Compose。 适用于无法访问互联网的环境。 准备工作 下载 .deb 包 在可以访问互联网的机器上,下载 Docker CE、…...
Linux配置SSH公钥认证与Jenkins远程登录进行自动发布
问题描述:在使用jenkins进行自动化部署时,其中一步是使用jenkins向目标服务器推送文件时,需要先在jenkins的系统配置中进行配置(事先安装好对应插件),配置远程服务器时,报错: 检查以…...
【故障处理】- 11g数据泵到19c导致的job不自动执行
【故障处理】- 11g数据泵到19c导致的job不自动执行 一、概述二、报错原因三、解决方法 一、概述 业务正常上线以后,客户反馈大量的job到时间了也不正常运行。 二、报错原因 该报错匹配bug 32249704,导致了迁移之后job的log_user从业务用户变成了sys。JOB…...
WPF8-常用控件
目录 写在前面:1. 按钮控件1.1. Button 按钮1.2. RepeatButton:长按按钮1.3. RadioButton:单选按钮 2. 数据显示控件2.1. TextBlock:只读文本控件2.2. Lable:标签 显示文本控件2.3. ListBox:显示可选择项的列表2.4. DataGrid&…...
电商小程序(源码+文档+部署+讲解)
引言 随着移动互联网的快速发展,电商小程序成为连接消费者与商家的重要桥梁。电商小程序通过数字化手段,为消费者提供了一个便捷、高效的购物平台,从而提升购物体验和满意度。 系统概述 电商小程序采用前后端分离的架构设计,服…...