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

算法打卡 Day29(回溯算法)-复原 IP 地址 + 子集 + 子集 Ⅱ

文章目录

  • Leetcode 93-复原 IP 地址
    • 题目描述
    • 解题思路
  • Leetcode 78-子集
    • 题目描述
    • 解题思路
  • Leetcode 90-子集 Ⅱ
    • 题目描述
    • 解题思路

Leetcode 93-复原 IP 地址

题目描述

https://leetcode.cn/problems/restore-ip-addresses/description/

在这里插入图片描述

解题思路

这是一道切割问题,可以参考分割回文串的思路

采用 isValid 函数判断当前切割得到的子串是否有效

class Solution {
public:vector<string> res;bool isValid(string s, int start, int end){if(start > end) return false;if (s[start] == '0' && end - start > 0) return false;if (end - start + 1 > 3) return false; // 添加长度检查string sub = s.substr(start, end-start+1);int num = stoi(sub);if (num > 255) return false;return true;}void backTracking(string s, int startIndex, int dotNum){if(dotNum == 3){if (isValid(s, startIndex,s.size()-1)){res.push_back(s);}return;}for (int i = startIndex; i< startIndex+3 && i <s.size();i++){if (isValid(s, startIndex,i)){s.insert(s.begin()+i+1,'.');dotNum += 1;backTracking(s, i + 2, dotNum);dotNum -= 1;s.erase(s.begin()+i+1);}}}vector<string> restoreIpAddresses(string s) {backTracking(s,0,0);return res;}
};

Leetcode 78-子集

题目描述

https://leetcode.cn/problems/subsets/description/

在这里插入图片描述

解题思路

在子集问题中需要在每一层递归中进行结果的收集

class Solution {
public:vector<vector<int>> res;vector<int> path;void backTracking(vector<int>& nums, int count, int startIndex){if (path.size()==count) {res.push_back(path);return;}for (int i = startIndex; i <nums.size();i++){path.push_back(nums[i]);backTracking(nums,count, i+1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {for (int i =0; i <=nums.size(); i++){backTracking(nums,i,0);}return res;}
};

Leetcode 90-子集 Ⅱ

题目描述

https://leetcode.cn/problems/subsets-ii/description/

在这里插入图片描述

解题思路

class Solution {
public:vector<vector<int>> res;vector<int> path;void backTracking(vector<int>& nums, int startIndex){res.push_back(path);if (startIndex == nums.size()) return;for (int i =startIndex; i < nums.size();i++){if (i >startIndex && nums[i]==nums[i-1]) continue;path.push_back(nums[i]);backTracking(nums,i+1);path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(),nums.end());backTracking(nums,0);return res;}
};

相关文章:

算法打卡 Day29(回溯算法)-复原 IP 地址 + 子集 + 子集 Ⅱ

文章目录 Leetcode 93-复原 IP 地址题目描述解题思路 Leetcode 78-子集题目描述解题思路 Leetcode 90-子集 Ⅱ题目描述解题思路 Leetcode 93-复原 IP 地址 题目描述 https://leetcode.cn/problems/restore-ip-addresses/description/ 解题思路 这是一道切割问题&#xff0c;…...

LeetCode 热题100-17 缺失的第一个正数

缺失的第一个正数 给你一个未排序的整数数组 nums &#xff0c;请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,0] 输出&#xff1a;3 解释&#xff1a;范围 [1,…...

基于CloudflareSpeedTest项目实现git clone加速

1.网络测速 「自选优选 IP」测试 Cloudflare CDN 延迟和速度&#xff0c;获取最快 IP 更多内容参考项目&#xff1a;https://github.com/XIU2/CloudflareSpeedTest 国外很多网站都在使用 Cloudflare CDN&#xff0c;但分配给中国内地访客的 IP 并不友好&#xff08;延迟高、丢…...

对与单纯post方法写项目的修改成baseservlet方法

解决的问题&#xff1a; 1.用baseservlet方法来写&#xff1a; 我之前没听明白gsa讲的那些&#xff0c;然后自己写了注册&#xff0c;用的post方法&#xff0c;就是那个叫我们最好不要用有点low的方法&#xff0c;后面与别人交流后发现是要用baseservlet来写&#xff0c;叫他…...

北京地铁换乘站人流量监控与图像识别技术优化

关于“北京地铁换乘站人流量监控与图像识别技术优化”&#xff0c;可以从以下几个方面进行详细阐述&#xff1a; 一、北京地铁换乘站人流量监控现状 北京地铁作为全国最繁忙的城市轨道交通系统之一&#xff0c;其换乘站的人流量监控是保障运营安全、提高运营效率的关键环节。…...

Day16_0.1基础学习MATLAB学习小技巧总结(16)——元胞数组

利用空闲时间把碎片化的MATLAB知识重新系统的学习一遍&#xff0c;为了在这个过程中加深印象&#xff0c;也为了能够有所足迹&#xff0c;我会把自己的学习总结发在专栏中&#xff0c;以便学习交流。 素材来源“数学建模清风” 特此说明&#xff1a;本博客的内容只在于总结在…...

C#自定义控件的放置与拖动

1、自定义控件 using System; using System.Collections.Generic; using System.ComponentModel; using System.Drawing; using System.Drawing.Drawing2D; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Windows.Forms;namespace PartA…...

python circular import python循环导入问题

遇到的问题是因为模块之间存在循环导入&#xff08;circular import&#xff09;&#xff0c;导致了ImportError。循环导入是指两个或多个模块相互导入对方&#xff0c;如模块A导入了模块B的方法&#xff0c;模块B又导入了模块A的方法&#xff0c;从而导致其中一个模块在完全初…...

kafka集群安装

kafka集群安装 文档 kafka单机安装 下载地址 官网&#xff1a;https://kafka.apache.org/最新版本下载页面&#xff1a;https://kafka.apache.org/downloads 说明 版本选择&#xff1a;3.0.0&#xff0c;kafka_2.12-3.0.0.tgz下载地址&#xff1a;https://archive.apache…...

SQL通用语法、SQL分类以及DDL

1.SQL 1.1SQL通用语法 1.SQL语句可以单行或多行书写&#xff0c;以分号结尾2.SQL语句可以使用空格/缩进来增强语句的可读性。3.MySQL数据库的SQL语句不区分大小写&#xff0c;关键字建议使用大写。4.注释&#xff1a; 单行注释&#xff1a;–空格 注释内容或#注释内容&#…...

静态链接和动态链接

静态链接和动态链接是两种将可执行文件与库进行链接的方式。它们的主要区别体现在链接时机、可执行文件的大小以及运行时的灵活性上。 1.静态链接 在静态链接中&#xff0c;所有需要的库&#xff08;例如 C 标准库 libc&#xff09;都会在编译时被复制并嵌入到最终的可执行文…...

构建智能门禁安防系统:树莓派 4B、OpenCV、SQLite 和 MQTT 的应用(代码示例)

一、项目概述 1.1 项目目标和用途 本项目旨在开发一个智能门禁安防系统&#xff0c;该系统利用摄像头和人脸识别技术&#xff0c;结合本地人脸库&#xff0c;实现对进出人员的自动识别和管理。系统能够实时记录进出人员的信息&#xff0c;并对未注册人员进行警报提示。通过与…...

基于 Konva 实现Web PPT 编辑器(二)

动画系统 为了实现演示中复杂的动画效果&#xff0c;使用 Animation 类统一管理&#xff1b;切换动画通过 css animation 实现&#xff0c;并且是应用在 konvajs-content 上&#xff0c;动画则通过 gsap 实现&#xff0c;应用在 Konva.Node 上&#xff0c;实现思路如下&#xf…...

【开源免费】基于SpringBoot+Vue.JS在线竞拍系统(JAVA毕业设计)

本文项目编号 T 013 &#xff0c;文末自助获取源码 \color{red}{T013&#xff0c;文末自助获取源码} T013&#xff0c;文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析 六、核心代码6.1 查…...

Qt TabWidget添加多个窗口,实现分页窗体布局

Qt TabWidget添加多个窗口窗体&#xff0c;可关闭与打开 点击按钮可判断是否打开&#xff0c;避免重复打开 使用Qt中的TabWidget组件创建一个简单的分页窗体布局。点击按钮时&#xff0c;会新增一个窗体并添加到TabWidget中。每个子窗体能动态获取父窗体指针以进行操作 分别…...

HarmonyOS开发实战( Beta5版)合理使用动画丢帧规范实践

本文列举了部分用于优化动画时延的正反案例&#xff0c;帮助开发者在遇到相似场景时进行优化&#xff0c;解决构建页面动画时遇到动画时延较长的问题。 减少动画丢帧 在播放动画或者生成动画时&#xff0c;画面产生停滞而导致帧率过低的现象&#xff0c;称为动画丢帧。 播放…...

基于BiLSTM-CRF的医学命名实体识别研究(下)模型构建

一.生成映射字典 接下来需要将每个汉字、边界、拼音、偏旁部首等映射成向量。所以&#xff0c;我们首先需要来构造字典&#xff0c;统计多少个不同的字、边界、拼音、偏旁部首等&#xff0c;然后再构建模型将不同的汉字、拼音等映射成不同的向量。 在prepare_data.py中自定义…...

5.sklearn-朴素贝叶斯算法、决策树、随机森林

文章目录 环境配置&#xff08;必看&#xff09;头文件引用1.朴素贝叶斯算法代码运行结果优缺点 2.决策树代码运行结果决策树可视化图片优缺点 3.随机森林代码RandomForestClassifier()运行结果总结 本章学习资源 环境配置&#xff08;必看&#xff09; Anaconda-创建虚拟环境…...

VMWARE VCENTER6.7 VCSA通过Web5480进行版本升级

VCENTER当前版本如下图 操作前先给VCENTER打一个快照&#xff0c;出问题可以立即回退 1、先下载VCSA镜像&#xff0c;并将VCSA镜像上传至DataStore中&#xff1b; 2、选中VCSA虚拟机&#xff0c;编辑配置 3、挂载新上传的VCSA镜像&#xff0c;一定要勾选“已连接”和“打开电源…...

GIT使用常见问题

如何安装Git&#xff1f; 在Windows操作系统中&#xff0c;可以从Git官方网站&#xff08;https://git-scm.com&#xff09;下载最新的Git安装程序&#xff0c;然后按照提示进行安装。在Mac操作系统中&#xff0c;可以使用Homebrew或者直接从Git官方网站下载安装程序进行安装。…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...