当前位置: 首页 > 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…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !

我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...