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

day28回溯算法part04| 93.复原IP地址 78.子集 90.子集II

**93.复原IP地址 **

本期本来是很有难度的,不过 大家做完 分割回文串 之后,本题就容易很多了
题目链接/文章讲解 | 视频讲解

class Solution {
public:vector<string> result;// pointNum记录加入的点的数量,其等于3的时候停止void backtracking(string& s, int startindex, int pointNum) {// 终止条件,逗号为3说明已经切割完了if (pointNum == 3) {// 只要分了三次,也就是有三个点之后// 直接判断最后一段,如果是的话就加入if (isvalid(s, startindex, s.size() - 1)) {result.push_back(s);}return;}for (int i = startindex; i < s.size(); i++) {// 判断[startindex, i]这个区间的子串是否合法if (isvalid(s, startindex, i)) {s.insert(s.begin() + i + 1, '.');pointNum++;backtracking(s, i + 2, pointNum);pointNum--;s.erase(s.begin() + i + 1);} else {// 不合法直接结束本层循环break;}}}bool isvalid(string& s, int start, int end) {// 1.段位以0开头的数字不合法// 2.段位里有非正整数字符不合法// 3.段位如果大于255不合法if (start > end)return false;// 0.0.0.0是合法的,start != end指的是01 0123这种情况if (s[start] == '0' && start != end) {return false;}int num = 0;for (int i = start; i <= end; i++) {if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法return false;}num = num * 10 + (s[i] - '0');if (num > 255) { // 如果大于255了不合法return false;}}return true;}vector<string> restoreIpAddresses(string s) {backtracking(s, 0, 0);return result;}
};

**78.子集 **

子集问题,就是收集树形结构中,每一个节点的结果。 整体代码其实和 回溯模板都是差不多的。
题目链接/文章讲解 | 视频讲解

class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums, int startindex) {result.push_back(path);// 确定结束条件if (startindex >= nums.size()) {return;}// 单层的处理逻辑for (int i = startindex; i < nums.size(); i++) {path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums, 0);return result;}
};

还是要熟悉这个回溯解题模板

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果}
}

**90.子集II **

大家之前做了 40.组合总和II 和 78.子集 ,本题就是这两道题目的结合,建议自己独立做一做,本题涉及的知识,之前都讲过,没有新内容。
题目链接/文章讲解 | 视频讲解

这题就是使用了之前的去重策略,在树层上进行去重,如果前一个数已经使用过了,就跳过一个树枝。
去重的时候要对数组进行排序,别忘记了

class Solution {
public:vector<int> path;vector<vector<int>> result;vector<bool> used;void backtracking(vector<int>& nums, int startindex) {result.push_back(path);if (startindex >= nums.size()) {return ;}for (int i = startindex; i < nums.size(); i++) {// 树层上去重,树层上进行跳过重复的if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false) {continue;}used[i] = true;path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();used[i] = false;}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {// 初始化used = vector<bool>(nums.size(), false);// 去重需要排序sort(nums.begin(), nums.end());backtracking(nums, 0);return result;}
};

相关文章:

day28回溯算法part04| 93.复原IP地址 78.子集 90.子集II

**93.复原IP地址 ** 本期本来是很有难度的&#xff0c;不过 大家做完 分割回文串 之后&#xff0c;本题就容易很多了 题目链接/文章讲解 | 视频讲解 class Solution { public:vector<string> result;// pointNum记录加入的点的数量&#xff0c;其等于3的时候停止void b…...

SpringBoot项目启动时“jar中没有主清单属性”异常

资料参考 Spring Boot 启动时 “jar中没有主清单属性” 异常 - spring 中文网 (springdoc.cn) 实际解决 更详细的参考以上&#xff0c;我这边的话只需要在 pom文件 中加上 spring-boot-maven-plugin 插件就能解决该异常&#xff0c;具体如下&#xff1a; <build><p…...

vAttention:用于在没有Paged Attention的情况下Serving LLM

文章目录 0x0. 前言&#xff08;太长不看版&#xff09;0x1. 摘要0x2. 介绍&背景0x3. 使用PagedAttention模型的问题0x3.1 需要重写注意力kernel0x3.2 在服务框架中增加冗余0x3.3 性能开销0x3.3.1 GPU上的运行时开销0x3.3.2 CPU上的运行时开销 0x4. 对LLM服务系统的洞察0x5…...

Python实现Stack

你好&#xff0c;我是悦创。 Python 中的栈结构是一种后进先出&#xff08;LIFO, Last In, First Out&#xff09;的数据结构&#xff0c;这意味着最后添加到栈中的元素将是第一个被移除的。栈通常用于解决涉及到反转、历史记录和撤销操作等问题。在 Python 中&#xff0c;你可…...

Helm在线部署Longhorn(1.6.0版本)分布式存储

环境依赖&#xff1a; k8s (版本大于等于v1.21版本)、helm工具 安装前准备 k8s worker 节点都需要执行 yum -y --setopttsflagsnoscripts install iscsi-initiator-utils echo "InitiatorName$(/sbin/iscsi-iname)" > /etc/iscsi/initiatorname.iscsi systemctl …...

算法题目学习汇总

1、二叉树前中后序遍历:https://blog.csdn.net/cm15835106905/article/details/124699173 2、输入一棵二叉搜索树&#xff0c;将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点&#xff0c;只能调整树中结点指针的指向。 public class Solution {private Tr…...

DockerCompose中部署Jenkins(Docker Desktop在windows上数据卷映射)

场景 DockerJenkinsGiteeMaven项目配置jdk、maven、gitee等拉取代码并自动构建以及遇到的那些坑&#xff1a; DockerJenkinsGiteeMaven项目配置jdk、maven、gitee等拉取代码并自动构建以及遇到的那些坑_jenkins的安装以及集成jdkgitmaven 提示警告-CSDN博客 Windows10(家庭版…...

吊车报警的工作原理和使用场景_鼎跃安全

在现代建筑施工过程中&#xff0c;经常使用大型机械设备&#xff0c;如挖掘机、吊车、打桩机等&#xff0c;这些设备在施工过程中发挥着越来越重要的作用&#xff1b;同时&#xff0c;这些设备的作业频繁进行作业&#xff0c;对于接触到高压电线的风险也随之增加。大型机械设备…...

Spring5

文章目录 1. Spring 是什么&#xff1f;2. IoC3. Spring Demo4. IoC 创建对象的方式 / DI 方式注入的默认参数在哪里设定? 5. Spring 配置tx:annotation-driven 用于启用基于注解的事务管理 6. Bean的作用域7. 在Spring中有三种自动装配的方式1. 在xml中显式的配置2. 在java中…...

vue面试题二

一、请解释Vue中的双向数据绑定是什么&#xff1f; Vue中的双向数据绑定是一种机制&#xff0c;它使得数据的变化能够自动反映在用户界面上&#xff0c;同时用户界面中的输入也能够自动更新数据。这种机制实现了数据层&#xff08;Model&#xff09;和视图层&#xff08;View&…...

软件设计师笔记-程序语言基础知识

编程语言之间的翻译形式 编程语言之间的翻译形式主要有三种:汇编、解释和编译。这三种方式在将源代码转换为机器可执行的代码时,有着各自的特点和流程。 汇编: 定义:汇编是低级语言(如汇编语言)到机器语言的一种翻译方式。汇编语言是为特定计算机或计算机系列设计的一种…...

在Windows上安装VMWare Pro 16.2(虚拟机)并从零安装CentOS 7.6镜像过程记录

本文详细记录了在Windows的VMWare Workstation Pro 16.2中安装CentOS 7.6 的过程,非常适合新手从零开始一步步安装。 文章目录 一、安装VMWare Workstation Pro 16.2并激活二、安装CentOS 7.62.1 下载CentOS7.6镜像文件2.2 创建新的虚拟机2.3 安装CentOS镜像一、安装VMWare Wo…...

NGINX之location和rewrite

一.NGINX常用的正则表达式 二.Location location作用:对访问的路径做访问控制或者代理转发 1.location 常用的匹配规则&#xff1a; 进行普通字符精确匹配&#xff0c;也就是完全匹配^~ / 表示普通字符匹配。使用前缀匹配。如果匹配成功&#xff0c;则不再匹配其它 …...

Python数据框的合并(一) -- merge函数

目录 1 merge 函数详解 1.1 左连接&#xff08;Left Join&#xff09;: 1.2 右连接&#xff08;Right Join&#xff09;: 1.3 全连接&#xff08;Full Join 或 Outer Join&#xff09;: 2 代码示例 2.1 加载模块并创建示例数据框 2.2 左连接 2.3 右连接 2.4 全连接 1 m…...

【Qt秘籍】[010]-Qt常用控件

一、控件概述 在GUI&#xff08;图形用户界面&#xff09;开发领域&#xff0c;Qt无疑是众多开发者心中的首选框架之一。它不仅跨平台、功能强大&#xff0c;而且拥有丰富且灵活的控件库&#xff0c;使得开发者能够快速构建美观、高效的用户界面。对于初学者而言&#xff0…...

TypeScript基础教程学习

菜鸟教程 TypeScript基础类型 数字类型 number 双精度 64 位浮点值。它可以用来表示整数和分数。 let binaryLiteral: number 0b1010; // 二进制 let octalLiteral: number 0o744; // 八进制 let decLiteral: number 6; // 十进制 let hexLiteral: number 0xf00d…...

JavaSE面试

①.简述面向对象的三大特征 封装、继承、多态 1.封装&#xff1a; 概念&#xff1a; 是将类的某些信息隐藏在类的内部&#xff0c;不允许外部程序直接访问&#xff0c;而是通过该类提供的方法来实现对隐藏信息的操作和访问。 好处 &#xff1a; ①便于修改&#xff0c;增强了代…...

安全漏洞扫描工具

常用的安全漏洞扫描工具涵盖了网络扫描、Web应用扫描、系统漏洞检测等多个方面&#xff0c;以下是一些业界广泛认可和常用的工具&#xff1a; Nmap - 网络映射和安全审计工具&#xff0c;用于发现网络上的主机和服务&#xff0c;识别操作系统&#xff0c;枚举开放端口&#xff…...

前端开发部署:Visual Studio Code + vue

〇 说明 本教程全部采用默认安装路径&#xff0c;因为在进行自定义路径安装的时候&#xff0c;需要配置各种环境变量&#xff0c;在这个配置过程中&#xff0c;可能出现各种很混乱的问题。 一 安装Node.js 1 下载https://nodejs.org/en 2 按照默认NEXT执行 C:\Program Files…...

基于Sentry+OpenTelemetry实现微服务前后端全链路监控

文章目录 前⾔背景技术⽅案Sentry私有化部署部署环境准备 项目集成前端后端agent探针集成sentry sdk集成增强探针为⽇志注⼊TraceID异常处理SDK⾃定义开发sentry sdk⾃定义开发⾃定义SentryEvent注⼊otel追踪信息⾃定义全局异常上报issue事件新增动态过滤功能 Java Agent Exten…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...