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

代码随想录算法训练营第二十八天|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&#xff1a; 指路&#xff1a;LeetCode93 复原IP地址 思路与代码&#xff1a; 对于这种暴搜出不来的就该用回溯了。对于一个合理的IP地址&#xff1a;有四个字串&#xff0c;每个字串的值的和在[0, 255]中即可(注意不可有前导0)。所以我们用一个计数器pointSum为给定字符…...

MongoDB CRUD操作:地理位置应用——通过地理空间查询查找餐厅

MongoDB CRUD操作&#xff1a;地理位置应用——通过地理空间查询查找餐厅 文章目录 MongoDB CRUD操作&#xff1a;地理位置应用——通过地理空间查询查找餐厅地图的扭曲搜索餐厅浏览数据查找当前邻居查找附近所有餐厅查找一定距离内的餐厅使用$geoWithin&#xff0c;不排序使用…...

从C++示例理解开闭原则

开闭原则要求我们在编写代码时&#xff0c;尽量不去修改原先的代码&#xff0c;当出现新的业务需求时&#xff0c;应该通过增加新代码的形式扩展业务而不是对原代码进行修改。 假如我们现在有一批产品&#xff0c;每个产品都具有颜色和大小&#xff0c;产品其定义如下&#xf…...

Java线程池execute和submit的区别

前言 ThreadPoolExecutor提供了两种方法来执行异步任务&#xff0c;分别是execute和submit&#xff0c;也是日常开发中经常使用的方法&#xff0c;那么它俩有什么区别呢&#xff1f; 语义不同 首先是语义上的不同。execute声明在Executor接口&#xff0c;它接受一个Runnable…...

什么是json

JSON&#xff08;JavaScript Object Notation&#xff09;是一种轻量级的数据交换格式。它基于JavaScript编程语言的一个子集&#xff0c;但是由于其文本格式清晰、易于解析&#xff0c;并且能够以键/值对的形式表示复杂的数据结构&#xff0c;因此它被广泛用于不同的编程语言和…...

基于聚类和回归分析方法探究蓝莓产量影响因素与预测模型研究附录

&#x1f31f;欢迎来到 我的博客 —— 探索技术的无限可能&#xff01; &#x1f31f;博客的简介&#xff08;文章目录&#xff09; 目录 背景数据说明数据来源思考 附录数据预处理导入包以及数据读取数据预览数据处理 相关性分析聚类分析数据处理确定聚类数建立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端进行 全屏幕自适应

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一&#xff1a;修改 index.html二&#xff1a;将非移动端设备&#xff0c;canvas元素的宽度和高度会设置为100%。三&#xff1a;修改style.css总结 下载地址&#x…...

36. 【Java教程】输入输出流

本小节将会介绍基本输入输出的 Java 标准类&#xff0c;通过本小节的学习&#xff0c;你将了解到什么是输入和输入&#xff0c;什么是流&#xff1b;输入输出流的应用场景&#xff0c;File类的使用&#xff0c;什么是文件&#xff0c;Java 提供的输入输出流相关 API 等内容。 1…...

Visual C++2010学习版详细安装教程(超详细图文)

Visual C 介绍 Visual C&#xff08;简称VC&#xff09;是微软公司推出的一种集成开发环境&#xff08;IDE&#xff09;&#xff0c;主要用于开发C和C语言的应用程序。它提供了强大的编辑器、编译器、调试器、库和框架支持&#xff0c;以及丰富的工具和选项&#xff0c;使得开…...

matlab图像处理入门

matlab在学校科研&#xff0c;仿真及基于模型开发的工作中有重要作用&#xff0c;在图像处理方面由于省去了复杂的上位机开发流程&#xff0c;因此可以让用户快速开发验证算法&#xff0c;下面简要介绍其在图像处理方面的应用。 matlab开发图像处理算法的流程主要是&#xff0c…...

关于线程池面试题,使用“豆包”训练答案

我提问&#xff1a; 问题描述 下面是一个有关线程池调度的面试真题&#xff0c;来自于疯狂创客圈社群&#xff1a; 一个线程池的核心线程数为10个&#xff0c;最大线程数为20个&#xff0c;阻塞队列的容量为30。现在提交45个 任务&#xff0c;每个任务的耗时为500毫秒。 请问&…...

【WRF理论第二期】模型目录介绍

WRF理论第二期&#xff1a;模型目录介绍 1 WRF主目录2 WPS主目录3 编译后的可执行文件4 运行目录参考 了解 WRF 模型的目录结构有助于有效地管理和操作模型&#xff0c;从而确保模拟和分析工作的顺利进行。以下分解介绍WRF主目录、WPS主目录等。 Github-wrf-model/WRF 1 WRF…...

从了解到掌握 Spark 计算框架(一)Spark 简介与基础概念

文章目录 什么是 Spark&#xff1f;核心特点 Spark 对比 MapReduceSpark 编程模型RDDDataFrameDataset Spark 运行模式Spark 生态 什么是 Spark&#xff1f; Spark 是一个基于内存的分布式计算框架&#xff0c;最初由加州大学伯克利分校的 AMPLab 开发&#xff0c;后来捐赠给了…...

linux bind函数

bind函数的目的是让把客户端对应的端口(port)地址和ip地址绑定到客户端 [参考](Linux之bind 函数&#xff08;详细篇&#xff09;_linux bind函数-CSDN博客)...

Flink系列一:flink光速入门 (^_^)

引入 spark和flink的区别&#xff1a;在上一个spark专栏中我们了解了spark对数据的处理方式&#xff0c;在 Spark 生态体系中&#xff0c;对于批处理和流处理采用了不同的技术框架&#xff0c;批处理由 Spark-core,SparkSQL 实现&#xff0c;流处理由 Spark Streaming 实现&am…...

PySpark特征工程(III)--特征选择

有这么一句话在业界广泛流传&#xff1a;数据和特征决定了机器学习的上限&#xff0c;而模型和算法只是逼近这个上限而已。由此可见&#xff0c;特征工程在机器学习中占有相当重要的地位。在实际应用当中&#xff0c;可以说特征工程是机器学习成功的关键。 特征工程是数据分析…...

Mongodb的数据库简介、docker部署、操作语句以及java应用

Mongodb的数据库简介、docker部署、操作语句以及java应用 本文主要介绍了mongodb的基础概念和特点&#xff0c;以及基于docker的mongodb部署方法&#xff0c;最后介绍了mongodb的常用数据库操作语句&#xff08;增删改查等&#xff09;以及java下的常用语句。 一、基础概念 …...

七大战略性新兴产业崭露头角:新能源电燃灶或将成为未来厨房新宠

近日&#xff0c;在国家发布的七大战略性新兴产业名单中&#xff0c;新能源产业赫然在列&#xff0c;作为其中的重要组成部分&#xff0c;华火新能源电燃灶凭借其独特的优势&#xff0c;正逐渐走进人们的视野&#xff0c;有望成为未来厨房的新宠。 华火新能源电燃灶作为清洁能源…...

C#进阶-用于Excel处理的程序集

在.NET开发中&#xff0c;处理Excel文件是一项常见的任务&#xff0c;而有一些优秀的Excel处理包可以帮助开发人员轻松地进行Excel文件的读写、操作和生成。本文介绍了NPOI、EPPlus和Spire.XLS这三个常用的.NET Excel处理包&#xff0c;分别详细介绍了它们的特点、示例代码以及…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...