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

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

面试高频问题

文章目录 &#x1f680; 消息队列核心技术揭秘&#xff1a;从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"&#xff1f;性能背后的秘密1.1 顺序写入与零拷贝&#xff1a;性能的双引擎1.2 分区并行&#xff1a;数据的"八车道高速公路"1.3 页缓存与批量处理…...

文件上传漏洞防御全攻略

要全面防范文件上传漏洞&#xff0c;需构建多层防御体系&#xff0c;结合技术验证、存储隔离与权限控制&#xff1a; &#x1f512; 一、基础防护层 前端校验&#xff08;仅辅助&#xff09; 通过JavaScript限制文件后缀名&#xff08;白名单&#xff09;和大小&#xff0c;提…...

C++中vector类型的介绍和使用

文章目录 一、vector 类型的简介1.1 基本介绍1.2 常见用法示例1.3 常见成员函数简表 二、vector 数据的插入2.1 push_back() —— 在尾部插入一个元素2.2 emplace_back() —— 在尾部“就地”构造对象2.3 insert() —— 在任意位置插入一个或多个元素2.4 emplace() —— 在任意…...

用 FFmpeg 实现 RTMP 推流直播

RTMP&#xff08;Real-Time Messaging Protocol&#xff09; 是直播行业中常用的传输协议。 一般来说&#xff0c;直播服务商会给你&#xff1a; ✅ 一个 RTMP 推流地址&#xff08;你推视频上去&#xff09; ✅ 一个 HLS 或 FLV 拉流地址&#xff08;观众观看用&#xff09;…...