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

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

这题主要用了动态规划和回溯算法。

  1. 动态规划数组初始化(DP数组):

    • 首先,创建一个二维数组dp,用于记录字符串中哪些部分是合法的IP地址。
    • 对字符串进行遍历,同时考虑每个可能的IP地址部分(每部分由1到3个字符组成,对应0-255),并根据IPv4地址的规则进行判断,更新dp数组。
  2. 深度优先搜索(DFS):

    • 定义DFS函数,用于递归生成合法的IPv4地址。该函数采用回溯法,遍历每一部分可能的范围,将符合条件的部分添加到当前路径中。
    • 如果已经形成四个部分且遍历到字符串末尾,将路径转为字符串,并加入结果集。
    • 否则,继续递归生成下一部分。
    • 在生成下一部分之前,将路径中的当前部分标记为一个点号('.'),以区分IPv4地址的各个部分。
  3. 返回结果:

    • 在主函数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地址

这题主要用了动态规划和回溯算法。 动态规划数组初始化&#xff08;DP数组&#xff09;: 首先&#xff0c;创建一个二维数组dp&#xff0c;用于记录字符串中哪些部分是合法的IP地址。对字符串进行遍历&#xff0c;同时考虑每个可能的IP地址部分&#xff08;每部分由1到3个字符组…...

第一次Python小练习题目

1.打印某学校的校训&#xff0c;具体内容如下所示&#xff1a; ****************************** 勤奋 严谨 求实 创新 ****************************** 注意: 第一行和最后一行各有 30 个*号。 答案&#xff1a; school_strs "勤奋 严谨 求实 创新&q…...

[BUG] docker运行Java程序时配置代理-Dhttp.proxyHost后启动报错

[BUG] docker运行Java程序时配置代理-Dhttp.proxyHost后启动报错 bug现象描述 版本&#xff1a;2.0.4&#xff08;客户端和服务端都是&#xff09; 环境&#xff1a;私有云环境&#xff0c;只有少量跳板机器可以访问公网&#xff0c;其他机器均通过配置代理方式访问公网 bug现…...

Python网站的搭建和html基础

1.Python网站代码及讲解 一般我们搭建小型的网站就用flask库就行了。 &#xff08;1&#xff09;安装flask库 安装完python后&#xff0c;按住windows徽标键和r,弹出“运行”&#xff0c;在里面输入cmd。 回车打开&#xff0c;输入“pip install flask”。 &#xff08;2&am…...

SpringCloud(21)之SpringCloud Alibaba Nacos实战应用

一、Nacos安装 1.1 Nacos概述 Nacos是Alibaba微服务生态组件中的重要组件之一&#xff0c;主要用它实现应用的动态服务发现、配置管理、 服务管理。Nacos discovery alibaba/spring-cloud-alibaba Wiki GitHub Nacos 致力于帮助您发现、配置和管理微服务。Nacos 提供了一组简…...

Python 基础语法:基本数据类型(元组)

1 元组&#xff08;Tuples&#xff09;概述 1.1 元组的定义与特点 元组&#xff08;Tuples&#xff09;是Python中的一个内置数据类型&#xff0c;用于存储一系列有序的元素。元组中的元素可以是任何类型&#xff0c;包括数字、字符串、列表等&#xff0c;且元素之间用逗号…...

vuepress-theme-vdoing博客搭建教程

搭建流程 前言 这是笔者搭建个人博客所经历的流程&#xff0c;特附上笔记 笔者个人博客地址&#xff1a;沉梦听雨的编程指南 一、主题介绍 本博客使用的主题为&#xff1a;vuepress-theme-vdoing&#xff0c;相关介绍和使用方法可以参考该主题的官方文档 官方文档快速上手…...

ICC2:create terminal参考脚本

我正在「拾陆楼」和朋友们讨论有趣的话题&#xff0c;你⼀起来吧&#xff1f; 拾陆楼知识星球入口 set list "" set i 0 ; set length xx set width xx foreach port $list { if {$i &#xff1d;&#xff1d; 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线程(一)】什么是线程?怎样操作线程?

&#x1f493;博主CSDN主页:杭电码农-NEO&#x1f493;   ⏩专栏分类:Linux从入门到精通⏪   &#x1f69a;代码仓库:NEO的学习日记&#x1f69a;   &#x1f339;关注我&#x1faf5;带你学更多操作系统知识   &#x1f51d;&#x1f51d; Linux线程 1. 前言2. 什么是线…...

python-0002-linux安装pycharm

下载软件包 下载地址&#xff1a;https://download.csdn.net/download/qq_41833259/88944791 安装 # 解压 tar -zxvf 你的软件包 # 进入软件解压后的路径&#xff0c;如解压到了/home/soft/pycharm cd /home/soft/pycharm cd bin # 执行启动命令 sh pycharm.sh # 等待软件启…...

扭蛋机小程序,扭蛋与互联网结合下的商机

扭蛋机作为一种娱乐消费模式&#xff0c;受众群体不再局限于儿童&#xff0c;也吸引了众多的年轻消费者。扭蛋机具有较大的随机性&#xff0c;玩具商品随机掉落&#xff0c;在购买前消费者完全不知道扭蛋中的商品是什么&#xff0c;这种未知性带来的惊喜感是吸引众多消费者的主…...

pytorch CV入门3-预训练模型与迁移学习

专栏链接&#xff1a;https://blog.csdn.net/qq_33345365/category_12578430.html 初次编辑&#xff1a;2024/3/7&#xff1b;最后编辑&#xff1a;2024/3/8 参考网站-微软教程&#xff1a;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 初识&#xff1a;基础语法&#xff1a;https://docs.swift.org/swift-book/documentation/the-swift-programming-language/guidedtour/…...

【Stable Diffusion】入门:原理简介+应用安装(Windows)+生成步骤

【Stable Diffusion】入门&#xff1a;原理简介应用安装&#xff08;Windows&#xff09;生成步骤 原理简介应用安装 原理简介 稳定扩散生成模型(Stable Diffusion)是一种潜在的文本到图像扩散模型&#xff0c;能够在给定任何文本输入的情况下生成照片般逼真的图像。 应用安…...

【栈】第十二届蓝桥杯省赛第一场C++ B组/研究生组《双向排序》(c++)

【题目描述】 给定序列 (a1,a2,⋅⋅⋅,an)(1,2,⋅⋅⋅,n)&#xff0c;即 aii。 小蓝将对这个序列进行 m 次操作&#xff0c;每次可能是将 a1,a2,⋅⋅⋅,aqi 降序排列&#xff0c;或者将 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】 比特币源码开源吗&#xff1f; 是的&#xff0c;比特币的源码是开源的。比特币项目是在MIT许可证下发布的&#xff0c;这意味着任何人都可以查看、修改、贡献和分发代码。比特币的源码托管在GitHub上&#xff0c;可以通过下面的链接进行访问&#xff1a; https://g…...

Linux查看磁盘命令df-h详解

df -h 是一个常用的 Linux 命令&#xff0c;用于查看文件系统的磁盘使用情况并以易于阅读的方式显示。以下是 df -h 命令的详细解释&#xff1a; -h&#xff1a;以人类可读的格式显示磁盘空间大小。例如&#xff0c;使用 GB、MB、KB 等单位代替字节。 执行 df -h 命令后&…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...