力扣--动态规划/深度优先算法/回溯算法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 命令后&…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
