代码随想录算法训练营第二十八天|LeetCode93 复原IP地址、LeetCode78 子集
题1:
指路:LeetCode93 复原IP地址
思路与代码:
对于这种暴搜出不来的就该用回溯了。对于一个合理的IP地址:有四个字串,每个字串的值的和在[0, 255]中即可(注意不可有前导0)。所以我们用一个计数器pointSum为给定字符串中分割字串的分隔符'.'计数。每当有一个合理的子串时在该子串后面增加一个分隔符,当pointSum等于3时该字符串合理。
class Solution {private:vector<string> result;void backtracking(string& s, int startIndex, int pointSum) {// pointSum 是IP地址中合理分割的分隔符if (pointSum == 3) { // 三个分隔符四个部分是正常的IP地址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)) {s.insert(s.begin() + i + 1, '.'); // 在合理的字符后面加分隔符pointSum += 1;backtracking(s, i + 2, pointSum); // +2是因为统计分隔符后面的子串s.erase(s.begin() + i + 1); // 回溯1:删除分隔符pointSum -= 1; // 回溯2:统计器-1复原}else break;}}// 判断子串是否在[0, 255]范围内bool isValid(const string& s, int begin, int end) {if (begin > end) return false;if (s[begin] == '0' && begin != end) return false;// 有前导0不合法int num = 0;for (int i = begin; 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;}
public:vector<string> restoreIpAddresses(string s) {backtracking(s, 0, 0);return result; }
};
emm……蛮有难度的一个题。题意很好懂,思路也容易理,但是不大好写,我改了蛮久。
题2:
指路:LeetCode78 子集
思路与代码:
标标准准的回溯题,类似于之前的组合。遇到合理的路径加入最终结果集,回溯弹出即可。代码如下:
class Solution {private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& s, int startIndex) {result.push_back(path);if (path.size() > s.size()) return ;for (int i = startIndex; i < s.size(); i++) {path.push_back(s[i]);backtracking(s, i + 1);path.pop_back();}}
public:vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums, 0);return result;}
};
相关文章:
代码随想录算法训练营第二十八天|LeetCode93 复原IP地址、LeetCode78 子集
题1: 指路:LeetCode93 复原IP地址 思路与代码: 对于这种暴搜出不来的就该用回溯了。对于一个合理的IP地址:有四个字串,每个字串的值的和在[0, 255]中即可(注意不可有前导0)。所以我们用一个计数器pointSum为给定字符…...
MongoDB CRUD操作:地理位置应用——通过地理空间查询查找餐厅
MongoDB CRUD操作:地理位置应用——通过地理空间查询查找餐厅 文章目录 MongoDB CRUD操作:地理位置应用——通过地理空间查询查找餐厅地图的扭曲搜索餐厅浏览数据查找当前邻居查找附近所有餐厅查找一定距离内的餐厅使用$geoWithin,不排序使用…...
从C++示例理解开闭原则
开闭原则要求我们在编写代码时,尽量不去修改原先的代码,当出现新的业务需求时,应该通过增加新代码的形式扩展业务而不是对原代码进行修改。 假如我们现在有一批产品,每个产品都具有颜色和大小,产品其定义如下…...
Java线程池execute和submit的区别
前言 ThreadPoolExecutor提供了两种方法来执行异步任务,分别是execute和submit,也是日常开发中经常使用的方法,那么它俩有什么区别呢? 语义不同 首先是语义上的不同。execute声明在Executor接口,它接受一个Runnable…...
什么是json
JSON(JavaScript Object Notation)是一种轻量级的数据交换格式。它基于JavaScript编程语言的一个子集,但是由于其文本格式清晰、易于解析,并且能够以键/值对的形式表示复杂的数据结构,因此它被广泛用于不同的编程语言和…...
基于聚类和回归分析方法探究蓝莓产量影响因素与预测模型研究附录
🌟欢迎来到 我的博客 —— 探索技术的无限可能! 🌟博客的简介(文章目录) 目录 背景数据说明数据来源思考 附录数据预处理导入包以及数据读取数据预览数据处理 相关性分析聚类分析数据处理确定聚类数建立k均值聚类模型 …...
java类型转换
pom <dependency><groupId>com.alibaba</groupId><artifactId>fastjson</artifactId><version>1.2.76</version></dependency>BeanUtils 在这里插入代码片list<Map>转换成List<bean> public static <T> L…...
Unity打包Webgl端进行 全屏幕自适应
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 一:修改 index.html二:将非移动端设备,canvas元素的宽度和高度会设置为100%。三:修改style.css总结 下载地址&#x…...
36. 【Java教程】输入输出流
本小节将会介绍基本输入输出的 Java 标准类,通过本小节的学习,你将了解到什么是输入和输入,什么是流;输入输出流的应用场景,File类的使用,什么是文件,Java 提供的输入输出流相关 API 等内容。 1…...
Visual C++2010学习版详细安装教程(超详细图文)
Visual C 介绍 Visual C(简称VC)是微软公司推出的一种集成开发环境(IDE),主要用于开发C和C语言的应用程序。它提供了强大的编辑器、编译器、调试器、库和框架支持,以及丰富的工具和选项,使得开…...
matlab图像处理入门
matlab在学校科研,仿真及基于模型开发的工作中有重要作用,在图像处理方面由于省去了复杂的上位机开发流程,因此可以让用户快速开发验证算法,下面简要介绍其在图像处理方面的应用。 matlab开发图像处理算法的流程主要是,…...
关于线程池面试题,使用“豆包”训练答案
我提问: 问题描述 下面是一个有关线程池调度的面试真题,来自于疯狂创客圈社群: 一个线程池的核心线程数为10个,最大线程数为20个,阻塞队列的容量为30。现在提交45个 任务,每个任务的耗时为500毫秒。 请问&…...
【WRF理论第二期】模型目录介绍
WRF理论第二期:模型目录介绍 1 WRF主目录2 WPS主目录3 编译后的可执行文件4 运行目录参考 了解 WRF 模型的目录结构有助于有效地管理和操作模型,从而确保模拟和分析工作的顺利进行。以下分解介绍WRF主目录、WPS主目录等。 Github-wrf-model/WRF 1 WRF…...
从了解到掌握 Spark 计算框架(一)Spark 简介与基础概念
文章目录 什么是 Spark?核心特点 Spark 对比 MapReduceSpark 编程模型RDDDataFrameDataset Spark 运行模式Spark 生态 什么是 Spark? Spark 是一个基于内存的分布式计算框架,最初由加州大学伯克利分校的 AMPLab 开发,后来捐赠给了…...
linux bind函数
bind函数的目的是让把客户端对应的端口(port)地址和ip地址绑定到客户端 [参考](Linux之bind 函数(详细篇)_linux bind函数-CSDN博客)...
Flink系列一:flink光速入门 (^_^)
引入 spark和flink的区别:在上一个spark专栏中我们了解了spark对数据的处理方式,在 Spark 生态体系中,对于批处理和流处理采用了不同的技术框架,批处理由 Spark-core,SparkSQL 实现,流处理由 Spark Streaming 实现&am…...
PySpark特征工程(III)--特征选择
有这么一句话在业界广泛流传:数据和特征决定了机器学习的上限,而模型和算法只是逼近这个上限而已。由此可见,特征工程在机器学习中占有相当重要的地位。在实际应用当中,可以说特征工程是机器学习成功的关键。 特征工程是数据分析…...
Mongodb的数据库简介、docker部署、操作语句以及java应用
Mongodb的数据库简介、docker部署、操作语句以及java应用 本文主要介绍了mongodb的基础概念和特点,以及基于docker的mongodb部署方法,最后介绍了mongodb的常用数据库操作语句(增删改查等)以及java下的常用语句。 一、基础概念 …...
七大战略性新兴产业崭露头角:新能源电燃灶或将成为未来厨房新宠
近日,在国家发布的七大战略性新兴产业名单中,新能源产业赫然在列,作为其中的重要组成部分,华火新能源电燃灶凭借其独特的优势,正逐渐走进人们的视野,有望成为未来厨房的新宠。 华火新能源电燃灶作为清洁能源…...
C#进阶-用于Excel处理的程序集
在.NET开发中,处理Excel文件是一项常见的任务,而有一些优秀的Excel处理包可以帮助开发人员轻松地进行Excel文件的读写、操作和生成。本文介绍了NPOI、EPPlus和Spire.XLS这三个常用的.NET Excel处理包,分别详细介绍了它们的特点、示例代码以及…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器
拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件: 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...
