力扣--动态规划/深度优先算法/回溯算法93.复原IP地址

这题主要用了动态规划和回溯算法。
-
动态规划数组初始化(DP数组):
- 首先,创建一个二维数组
dp,用于记录字符串中哪些部分是合法的IP地址。 - 对字符串进行遍历,同时考虑每个可能的IP地址部分(每部分由1到3个字符组成,对应0-255),并根据IPv4地址的规则进行判断,更新
dp数组。
- 首先,创建一个二维数组
-
深度优先搜索(DFS):
- 定义DFS函数,用于递归生成合法的IPv4地址。该函数采用回溯法,遍历每一部分可能的范围,将符合条件的部分添加到当前路径中。
- 如果已经形成四个部分且遍历到字符串末尾,将路径转为字符串,并加入结果集。
- 否则,继续递归生成下一部分。
- 在生成下一部分之前,将路径中的当前部分标记为一个点号('.'),以区分IPv4地址的各个部分。
-
返回结果:
- 在主函数
restoreIpAddresses中,首先初始化dp数组,然后调用DFS函数,开始生成合法的IPv4地址。 - 最后,返回生成的IPv4地址结果集。
- 在主函数
class Solution {vector<string> result; // 存储结果的容器vector<char> path; // 存储当前路径的容器// 深度优先搜索函数,用于生成合法的IPv4地址void dfs(vector<vector<bool>>& dp, string s, int start, int num) {num++;if (num >= 5) // 如果已经有四个部分了,结束递归return;// 遍历当前部分的可能范围for (int i = start; i - start <= 2 && i < s.size(); i++) {if (dp[start][i] == true) {// 将当前部分加入路径for (int j = start; j <= i; j++)path.push_back(s[j]);// 如果已经是最后一部分且遍历到字符串末尾,将路径转为字符串加入结果集if (i == s.size() - 1 && num == 4) {string str;str.assign(path.begin(), path.end());result.push_back(str);}// 否则,继续递归生成下一部分else {path.push_back('.');dfs(dp, s, i + 1, num);path.pop_back();}// 回溯,将当前部分从路径中移除for (int j = start; j <= i; j++)path.pop_back();}}return;}public:// 主函数,生成合法IPv4地址的入口vector<string> restoreIpAddresses(string s) {int n = s.size();// dp数组用于记录字符串中哪些部分是合法的vector<vector<bool>> dp(n, vector<bool>(n, false));// 遍历字符串,初始化dp数组for (int i = 0; i < n; i++) {for (int j = i; j <= i + 2 && j < n; j++) {if (i == j)dp[i][j] = true;else if (i == j - 1) {if (s[i] == '0')dp[i][j] = false;elsedp[i][j] = true;} else {if (s[i] == '0' || s[i] >= '3')dp[i][j] = false;else if (s[i] == '1')dp[i][j] = true;else {if (s[i + 1] <= '4' || (s[i + 1] == '5' && s[j] <= '5'))dp[i][j] = true;}}}}// 调用深度优先搜索函数,开始生成合法IPv4地址dfs(dp, s, 0, 0);// 返回最终结果return result;}
};
相关文章:
力扣--动态规划/深度优先算法/回溯算法93.复原IP地址
这题主要用了动态规划和回溯算法。 动态规划数组初始化(DP数组): 首先,创建一个二维数组dp,用于记录字符串中哪些部分是合法的IP地址。对字符串进行遍历,同时考虑每个可能的IP地址部分(每部分由1到3个字符组…...
第一次Python小练习题目
1.打印某学校的校训,具体内容如下所示: ****************************** 勤奋 严谨 求实 创新 ****************************** 注意: 第一行和最后一行各有 30 个*号。 答案: school_strs "勤奋 严谨 求实 创新&q…...
[BUG] docker运行Java程序时配置代理-Dhttp.proxyHost后启动报错
[BUG] docker运行Java程序时配置代理-Dhttp.proxyHost后启动报错 bug现象描述 版本:2.0.4(客户端和服务端都是) 环境:私有云环境,只有少量跳板机器可以访问公网,其他机器均通过配置代理方式访问公网 bug现…...
Python网站的搭建和html基础
1.Python网站代码及讲解 一般我们搭建小型的网站就用flask库就行了。 (1)安装flask库 安装完python后,按住windows徽标键和r,弹出“运行”,在里面输入cmd。 回车打开,输入“pip install flask”。 (2&am…...
SpringCloud(21)之SpringCloud Alibaba Nacos实战应用
一、Nacos安装 1.1 Nacos概述 Nacos是Alibaba微服务生态组件中的重要组件之一,主要用它实现应用的动态服务发现、配置管理、 服务管理。Nacos discovery alibaba/spring-cloud-alibaba Wiki GitHub Nacos 致力于帮助您发现、配置和管理微服务。Nacos 提供了一组简…...
Python 基础语法:基本数据类型(元组)
1 元组(Tuples)概述 1.1 元组的定义与特点 元组(Tuples)是Python中的一个内置数据类型,用于存储一系列有序的元素。元组中的元素可以是任何类型,包括数字、字符串、列表等,且元素之间用逗号…...
vuepress-theme-vdoing博客搭建教程
搭建流程 前言 这是笔者搭建个人博客所经历的流程,特附上笔记 笔者个人博客地址:沉梦听雨的编程指南 一、主题介绍 本博客使用的主题为:vuepress-theme-vdoing,相关介绍和使用方法可以参考该主题的官方文档 官方文档快速上手…...
ICC2:create terminal参考脚本
我正在「拾陆楼」和朋友们讨论有趣的话题,你⼀起来吧? 拾陆楼知识星球入口 set list "" set i 0 ; set length xx set width xx foreach port $list { if {$i == 0} { set startx 0 set starty 0 } else { set sta…...
并行计算CUDA DEMO
//并行计算CUDA DEMO #include "cuda_runtime.h" #include "device_launch_parameters.h" #include <stdio.h> cudaError_t addWithCuda(int *c, const int *a, const int *b, unsigned int size); __global__ void addKernel(int *c, const int …...
【linux线程(一)】什么是线程?怎样操作线程?
💓博主CSDN主页:杭电码农-NEO💓 ⏩专栏分类:Linux从入门到精通⏪ 🚚代码仓库:NEO的学习日记🚚 🌹关注我🫵带你学更多操作系统知识 🔝🔝 Linux线程 1. 前言2. 什么是线…...
python-0002-linux安装pycharm
下载软件包 下载地址:https://download.csdn.net/download/qq_41833259/88944791 安装 # 解压 tar -zxvf 你的软件包 # 进入软件解压后的路径,如解压到了/home/soft/pycharm cd /home/soft/pycharm cd bin # 执行启动命令 sh pycharm.sh # 等待软件启…...
扭蛋机小程序,扭蛋与互联网结合下的商机
扭蛋机作为一种娱乐消费模式,受众群体不再局限于儿童,也吸引了众多的年轻消费者。扭蛋机具有较大的随机性,玩具商品随机掉落,在购买前消费者完全不知道扭蛋中的商品是什么,这种未知性带来的惊喜感是吸引众多消费者的主…...
pytorch CV入门3-预训练模型与迁移学习
专栏链接:https://blog.csdn.net/qq_33345365/category_12578430.html 初次编辑:2024/3/7;最后编辑:2024/3/8 参考网站-微软教程:https://learn.microsoft.com/en-us/training/modules/intro-computer-vision-pytorc…...
Swift SwiftUI 学习笔记 2024
Swift SwiftUI 学习笔记 2024 一、资源 视频资源 StanfordUnivercity 公开课 2023: https://cs193p.sites.stanford.edu/2023 教程 Swift 初识:基础语法:https://docs.swift.org/swift-book/documentation/the-swift-programming-language/guidedtour/…...
【Stable Diffusion】入门:原理简介+应用安装(Windows)+生成步骤
【Stable Diffusion】入门:原理简介应用安装(Windows)生成步骤 原理简介应用安装 原理简介 稳定扩散生成模型(Stable Diffusion)是一种潜在的文本到图像扩散模型,能够在给定任何文本输入的情况下生成照片般逼真的图像。 应用安…...
【栈】第十二届蓝桥杯省赛第一场C++ B组/研究生组《双向排序》(c++)
【题目描述】 给定序列 (a1,a2,⋅⋅⋅,an)(1,2,⋅⋅⋅,n),即 aii。 小蓝将对这个序列进行 m 次操作,每次可能是将 a1,a2,⋅⋅⋅,aqi 降序排列,或者将 aqi,aqi1,⋅⋅⋅,an 升序排列。 请求出操作完成后的序列。 【输入格式】 输入的第一行…...
Gitea 安装和配置
Gitea 安装和配置: http://coffeelatte.vip.cpolar.top/post/software/applications/gitea/gitea_安装和配置/ 文章目录 Gitea 安装和配置: <http://coffeelatte.vip.cpolar.top/post/software/applications/gitea/gitea_%E5%AE%89%E8%A3%85%E5%92%8C%E9%85%8D%E7%BD%AE/>…...
CEF JS与c++能够交互的原理 以及 JS 调用C++的流程分析
相关章节:CEF 之 Render进程 与 Browser进程通信 目录 一、JS与c++能够交互的原理 二、JS调用C++ 流程梳理...
关于比特币的AI对话
【ChatGPT】 比特币源码开源吗? 是的,比特币的源码是开源的。比特币项目是在MIT许可证下发布的,这意味着任何人都可以查看、修改、贡献和分发代码。比特币的源码托管在GitHub上,可以通过下面的链接进行访问: https://g…...
Linux查看磁盘命令df-h详解
df -h 是一个常用的 Linux 命令,用于查看文件系统的磁盘使用情况并以易于阅读的方式显示。以下是 df -h 命令的详细解释: -h:以人类可读的格式显示磁盘空间大小。例如,使用 GB、MB、KB 等单位代替字节。 执行 df -h 命令后&…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
LRU 缓存机制详解与实现(Java版) + 力扣解决
📌 LRU 缓存机制详解与实现(Java版) 一、📖 问题背景 在日常开发中,我们经常会使用 缓存(Cache) 来提升性能。但由于内存有限,缓存不可能无限增长,于是需要策略决定&am…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
yaml读取写入常见错误 (‘cannot represent an object‘, 117)
错误一:yaml.representer.RepresenterError: (‘cannot represent an object’, 117) 出现这个问题一直没找到原因,后面把yaml.safe_dump直接替换成yaml.dump,确实能保存,但出现乱码: 放弃yaml.dump,又切…...
DAY 45 超大力王爱学Python
来自超大力王的友情提示:在用tensordoard的时候一定一定要用绝对位置,例如:tensorboard --logdir"D:\代码\archive (1)\runs\cifar10_mlp_experiment_2" 不然读取不了数据 知识点回顾: tensorboard的发展历史和原理tens…...
【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架
文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理:检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目:RankRAG:Unifying Context Ranking…...
