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

代码随想录二刷 | 回溯 |复原IP地址

代码随想录二刷 | 回溯 |复原IP地址

  • 题目描述
  • 解题思路
  • 代码实现

题目描述

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 仅由数字组

解题思路

递归三部曲

  • 递归函数的参数
    startIndex一定是需要的,因为不能重复分割,记录下一层递归分割的起始位置。

    本题我们还需要一个变量pointNum,记录添加逗点的数量。

    vector<string> result;
    void backtracking(string& s, int startIndex, int pointNum) 
    
  • 递归终止条件
    本题明确要求只会分成4段,所以不能用切割线切到最后作为终止条件,而是分割的段数作为终止条件。

    pointNum表示逗点数量,pointNum为3说明字符串分成了4段了。

    然后验证一下第四段是否合法,如果合法就加入到结果集里

    if (pointNum == 3) {if (isValid(s, startIndex, s.size() - 1)) {result.push_back(s);}return;
    }
    
  • 单层搜索的逻辑
    for (int i = startIndex; i < s.size(); i++)循环中 [startIndex, i] 这个区间就是截取的子串,需要判断这个子串是否合法。

    如果合法就在字符串后面加上符号.表示已经分割,如果不合法就结束本层循环。

    然后就是递归和回溯的过程:

    递归调用时,下一层递归的startIndex要从i+2开始(因为需要在字符串中加入了分隔符.),同时记录分割符的数量pointNum 要 +1。

    回溯的时候,就将刚刚加入的分隔符. 删掉就可以了,pointNum也要-1。

    for (int i = startIndex; i < s.size(); i++) {if (isValid(s, startIndex, i)) {s.insert(s.begin() + i + 1, '.');pointNum++;backtracking(s, i + 2, pointNum);pointNum--;s.erase(s.begin() + i + 1);} else break;
    } 
    

    最后就是在写一个判断段位是否是有效段位了。

    主要考虑到如下三点:

  • 段位以0为开头的数字不合法

  • 段位里有非正整数字符不合法

  • 段位如果大于255了不合法

// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
bool isValid(const string& s, int start, int end) {if (start > end) {return false;}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');if (num > 255) {return false;}}return true;
}

代码实现

class Solution {
private:vector<string> result;// 记录结果// startIndex: 搜索的起始位置,pointNum:添加逗点的数量void backtracking(string& s, int startIndex, int pointNum) {if (pointNum == 3) { // 逗点数量为3时,分隔结束// 判断第四段子字符串是否合法,如果合法就放进result中if (isValid(s, startIndex, s.size() - 1)) {result.push_back(s);}return;}for (int i = startIndex; i < s.size(); i++) {if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一个逗点pointNum++;backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2pointNum--;                         // 回溯s.erase(s.begin() + i + 1);         // 回溯删掉逗点} else break; // 不合法,直接结束本层循环}}// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法bool isValid(const string& s, int start, int end) {if (start > end) {return false;}if (s[start] == '0' && start != end) { // 0开头的数字不合法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');if (num > 255) { // 如果大于255了不合法return false;}}return true;}
public:vector<string> restoreIpAddresses(string s) {result.clear();if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了backtracking(s, 0, 0);return result;}
};

相关文章:

代码随想录二刷 | 回溯 |复原IP地址

代码随想录二刷 &#xff5c; 回溯 &#xff5c;复原IP地址 题目描述解题思路代码实现 题目描述 93.复原IP地址 给定一个只包含数字的字符串&#xff0c;复原它并返回所有可能的 IP 地址格式。 有效的 IP 地址 正好由四个整数&#xff08;每个整数位于 0 到 255 之间组成&am…...

windows资源管理器占用过高CPU的问题

最近&#xff0c;笔者的电脑在进行文件操作时变得异常的卡顿&#xff0c;打开任务管理器发现windows资源管理器占用了50%-80%的CPU。这里指的文件操作包括但不限于解压&#xff0c;复制&#xff0c;粘贴&#xff0c;甚至重命名一个文件夹都会引起50%的CPU占用。起初笔者认为可能…...

redis的常见数据类型和应用场景(非八股)------大总结(学了要会用-------教你如何使用)

Redis的数据类型 Redis 提供了丰富的数据类型&#xff0c;常见的有五种&#xff1a; String&#xff08;字符串&#xff09;&#xff0c;Hash&#xff08;哈希&#xff09;&#xff0c;List&#xff08;列表&#xff09;&#xff0c;Set&#xff08;集合&#xff09;、Zset&am…...

UE 可靠UDP实现原理

发送 我们的消息发送都是通过 UChannel 来处理的&#xff0c;通过调用 UChannel::SendBunch 统一处理。 发送的 Bunch 是以 FOutBunch 的形式存在的。当 bReliable 为 True 的时候&#xff0c;表示 Bunch 是可靠的。 发送逻辑直接从UChannel::SendBunch处开始分析 1、大小限…...

智慧博物馆信息化系统建设(1)

博物馆RFID藏品管理系统 博物馆藏品保管是一项十分复杂又繁琐的工作。从事保管工作除了经常、及时地进行藏品的登记、分类、编目、保养和修复等一系列工作外,还需要把有关藏品的信息迅速、正确地提供给利用者。要提高保管工作的效率,达到现代化的科学管理,从发展趋势看,进…...

【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

目录 一、二叉树的创建(伪)二、二叉树的遍历2.1 前序遍历2.2 中序遍历2.3 后序遍历 三、二叉树节点个数及高度3.1 二叉树节点个数3.2 二叉树叶子节点个数3.3二叉树第k层节点个数3.4 二叉树查找值为x的节点 四、二叉树的创建(真) 一、二叉树的创建(伪) 在学习二叉树的基本操作前…...

Cesium for Unity包无法加载

太上老君急急如律⚡令⚡ &#x1f959;关闭UnityHub&#x1f9c0;启动梯子&#x1f96a;cmd 启动UnityHub &#x1f959;关闭UnityHub &#x1f9c0;启动梯子 &#x1f96a;cmd 启动UnityHub 把批处理启动文件&#x1f448;中的exe的路径换成自己的安装目录&#xff01;保存…...

Leetcode—40.组合总和II【中等】

2023每日刷题&#xff08;七十七&#xff09; Leetcode—40.组合总和II 算法思想 实现代码 class Solution { public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<vector<int>> ans;vector<int…...

vscode连不上虚拟机,一直密码错误

最近在做毕设&#xff0c;但是vscode使用连接不上虚拟机&#xff0c;我以为是网络配置的问题&#xff0c;一顿查阅没找到原因。 后来查了一下ssh的日志&#xff0c;发现ssh有消息&#xff0c;但是也提示密码错误。 没找到密码配置格式什么的&#xff0c;经查看sshd配置文件发现…...

力扣每日一题 --- 972. 相等的有理数

本题中的一个难点是怎么判断是否相等&#xff0c;如果自己写判断的话是不是很麻烦&#xff0c;判断整数之后再去判断小数部分&#xff0c;那么我们这题的另一个难点就要登场了&#xff0c;第一个难点让本题的情况变得复杂&#xff0c;第二个难点让本题变得很难想到怎么判断&…...

EXECL 单元格字符串链接 CONCAT :应用:将一行数据转为json

源&#xff1a; 目标 函数表示 CONCAT("data", CHAR(10), "{", CHAR(10), " ", "ulAlarmId : ", A5, CHAR(10), " ", "ulAlarmLevel : ", D5, CHAR(10)," ", "bBo…...

基于Python实现人脸识别相似度对比

目录 引言背景介绍目的和意义 人脸识别的原理人脸图像获取人脸检测与定位人脸特征提取相似度计算 基于Python的人脸相似度对比实现数据集准备人脸图像预处理特征提取相似度计算 引言 背景介绍 人脸识别技术是一种通过计算机对人脸图像进行分析和处理&#xff0c;从而实现自动识…...

CSS 蜡烛效果

<template><view class="holder"><!-- 身子 --><view class="candle"><!-- 光源 --><view class="blinking-glow"></view><!-- 火星子 --><view class="thread"></view>…...

渗透测试之Kali如何利用CVE-2019-0708漏洞渗透Win7

环境: 1.攻击者IP:192.168.1.10 系统: KALI2022(vmware 16.0) 2.靶机IP:192.168.1.8 系统:Windows 7 6.1.7601 Service Pack 1 Build 7601 已开启远程协助RDP服务开启了3389端口 问题描述: KALI 如何利用CVE-2019-0708漏洞渗透Win7 解决方案: 1.打开kali,msf搜索…...

Docker(二)安装指南:主要介绍在 Linux 、Windows 10 和 macOS 上的安装

作者主页&#xff1a; 正函数的个人主页 文章收录专栏&#xff1a; Docker 欢迎大家点赞 &#x1f44d; 收藏 ⭐ 加关注哦&#xff01; 安装 Docker Docker 分为 stable test 和 nightly 三个更新频道。 官方网站上有各种环境下的 安装指南&#xff0c;这里主要介绍 Docker 在…...

LeetCode 410. 分割数组的最大值

一、题目 1、题目描述 给定一个非负整数数组 nums 和一个整数 k &#xff0c;你需要将这个数组分成 k 个非空的连续子数组。 设计一个算法使得这 k 个子数组各自和的最大值最小。 2、接口描述 ​ class Solution { public:int splitArray(vector<int>& nums, int …...

linux shell脚本 基础认识

Linux 系统中的 Shell 是一个特殊的应用程序&#xff0c;它介于操作系统内核与用户之间&#xff0c;充当 了一个“命令解释器”的角色&#xff0c;负责接收用户输入的操作指令&#xff08;命令&#xff09;并进行解释&#xff0c;将需要执行的操作传递给内核执行&#xff0c;并…...

一文(10图)了解Cornerstone3D核心概念(万字总结附导图)

Cornerstone3D介绍 Cornerstone3D是一个专门为处理三维医学影像而设计的JavaScript库。 它是Cornerstone项目的一部分&#xff0c;旨在为医学影像社区提供高性能、可扩展且易于使用的开源Web工具&#xff0c;专注于提供交互式的3D医学图像浏览体验&#xff0c;适用于多种医学…...

牛客网-----跳石头

题目描述&#xff1a; 一年一度的“跳石头”比赛又要开始了! 这项比赛将在一条笔直的河道中进行&#xff0c;河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间&#xff0c;有N块岩石(不含起点和终点的岩石)。在比赛过程中&#xff0…...

用ChatGPT教学、科研!大学与OpenAI合作

亚利桑那州立大学&#xff08;简称“ASU”&#xff09;在官网宣布与OpenAI达成技术合作。从2024年2月份开始&#xff0c;为所有学生提供ChatGPT企业版访问权限&#xff0c;主要用于学习、课程作业和学术研究等。 为了帮助学生更好地学习ChatGPT和大语言模型产品&#xff0c;AS…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

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

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

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...