代码随想录打卡第二十五天
代码随想录–回溯部分
day 24 休息
day 25 回溯第三天
文章目录
- 代码随想录--回溯部分
- 一、力扣93--复原IP地址
- 二、力扣78--子集
- 三、力扣90--子集Ⅱ
一、力扣93–复原IP地址
代码随想录题目链接:代码随想录
有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 ‘.’ 分隔。
例如:“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址,但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s ,用以表示一个 IP 地址,返回所有可能的有效 IP 地址,这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案
简单来说就是穷举,把一个数组按照规则分成四串,所有的可能性
类似分割回文串,但是需要修改“回文串”的判断逻辑
把切下来的子串用于判断,当其开头不是0且整体在0-255之间,则可以下一步递归,否则不递归
代码如下:
class Solution {
public:vector<string> result;bool isValid(const string s){int num = 0;if (s.size() > 1 && s[0] == '0'|| !s.size()) return false;else {for (int i = 0; i < s.size(); i++) {if (s[i] > '9' || s[i] < '0') return false;num = num * 10 + (s[i] - '0');if (num > 255) { return false;}}if(num > 255 || num < 0) return false;return true;}}void backTracking(string & s, int startIndex, int pointNum){if(pointNum == 3){string temp = string(s.begin() + startIndex, s.end());if(isValid(temp)){result.push_back(s); }return;}for(int i = startIndex; i < s.size(); i ++){string test = string(s.begin() + startIndex, s.begin() + i + 1);if(isValid(test)) {s.insert(s.begin() + i + 1, '.');pointNum ++;backTracking(s, i + 2, pointNum);s.erase(s.begin() + i + 1);pointNum --;}else break;}}vector<string> restoreIpAddresses(string s) {if (s.size() < 4 || s.size() > 12) return result;backTracking(s, 0, 0);return result;}
};
切割字符串这里需要注意,是左闭右开的
所以是startIndex + i + 1
二、力扣78–子集
代码随想录题目链接:代码随想录
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的
子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
非常像力扣77–组合的问题,只不过是k在动态的变化
只要在判断return的条件上修改一下就行了
不再需要判断是否能够加入result中,也不用中断后续的递归,只管让代码运行即可
这样就能做到遍历完整的树,每次回溯都需要把自身加入结果中,不需要判断了
代码如下:
class Solution {
public:vector<int> path;vector<vector<int>> result;void backTracking(vector<int> & nums, int startIndex){result.push_back(path);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;}
};
输入
nums =[1,2,3]
输出
[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
从输入输出也能看出回溯的顺序,先是搜索完1向下的一整串,返回后从2继续向下搜索
所以每层都需要记录自己,不然会漏掉
三、力扣90–子集Ⅱ
代码随想录题目链接:代码随想录
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的
子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
不同于子集,这次给的num会存在重复数字,输出要去重
思想和组合总和Ⅲ是一样的,对nums排序,并且通过used数组记录回溯层数
这样判断前一位和后一位是否相同且是否在一层,就可以做到去重复了
代码如下:
class Solution {
public:vector<int> path;vector<vector<int>> result;vector<bool> used;void backTracking(vector<int> & nums, int startIndex){result.push_back(path);for(int i = startIndex; i < nums.size(); i ++){if(i > 0 && nums[i] == nums[i - 1] && !used[i-1]) continue;path.push_back(nums[i]);used[i] = true;backTracking(nums, i + 1);path.pop_back();used[i] = false;}}vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end());used = vector<bool>(nums.size(), false);backTracking(nums, 0);return result;}
};
相关文章:
代码随想录打卡第二十五天
代码随想录–回溯部分 day 24 休息 day 25 回溯第三天 文章目录 代码随想录--回溯部分一、力扣93--复原IP地址二、力扣78--子集三、力扣90--子集Ⅱ 一、力扣93–复原IP地址 代码随想录题目链接:代码随想录 有效 IP 地址 正好由四个整数(每个整数位于 0…...
openharmony上传图片,并获取返回路径
适用条件: openharmony开发 4.0 release版本,对应能力API10 一直不断尝试,一会用官方提供的上传文件,一会用第三方库的axios都不行, 一会报错‘没权限,一会报错’路径错误,还有报错‘401参数错…...
git常用命令及git分支
git常用命令及git分支 git常用命令设置用户签名初始化本地库查看本地库状态将文件添加到暂存区提交到本地库查看历史记录版本穿梭 git分支什么是分支分支的好处分支的操作查看分支创建分支切换分支删除分支合并分支合并冲突 git常用命令 设置用户签名 //设置用户签名 git con…...
c# 依赖注入-服务的生命周期
在 C# 中,依赖注入服务的生命周期指的是在应用程序中管理和控制依赖项注入服务对象的生命周期的方式。常见的生命周期包括瞬态(transient)、作用域(scoped)和单例(singleton)三种。 瞬态&#…...
一站式短视频矩阵开发,高效托管!
短视频矩阵系统源码SaaS解决方案提供全面的开发服务,包括可视化视频编辑、矩阵式内容分发托管以及集成的多功能开发支持。 短视频矩阵:引爆您的数字营销革命 短视频矩阵系统是一套多功能集成解决方案,专为提升在短视频平台上的内容创作、管理…...
实践致知第16享:设置Word中某一页横着的效果及操作
一、背景需求 小姑电话说:现在有个word文档,里面有个表格太长(如下图所示),希望这一个设置成横的,其余页还是保持竖的! 二、解决方案 1、将鼠标放置在该页的最前面闪烁,然后选择“页面”》“↘…...
Leetcode—3011. 判断一个数组是否可以变为有序【中等】(__builtin_popcount()、ranges::is_sorted())
2024每日刷题(144) Leetcode—3011. 判断一个数组是否可以变为有序 O(n)复杂度实现代码 class Solution { public:bool canSortArray(vector<int>& nums) {// 二进制数位下1数目相同的元素就不进行组内排序// 只进行分组// 当前组的值若小于…...
盲盒一番赏小程序:开启惊喜之旅,探索无限创意!
在这个充满无限想象与惊喜的时代,盲盒已成为连接心灵与梦想的奇妙桥梁。为了将这份独特的乐趣与探索精神传递给每一位热爱生活、追求新鲜的你,我们自豪地推出了“盲盒一番赏”小程序——一个集创意、趣味、互动与社交于一体的盲盒新纪元,邀您…...
Linux基础知识之Linux文件系统权限
概述 文件权限控制对文件的访问可以针对文件所属用户、所属组和其他用户可以设置不同的权限权限具有优先级。user 权限覆盖 group 权限,后者覆盖 other 权限 权限:读取、写入和执行 权限 对文件的影响 对目录的影响 r (读取) 可以读取文件的内容 …...
Qt qml详细介绍
一.基本类型 QML的基本类型包括了很多不同的类型,这些类型可以用于定义用户界面元素、属性和信号。以下是一些常用的QML基本类型及其详细介绍: 数值类型:包括整数类型(int、uint、short、ushort等)和浮点数类型&#…...
深度解析:如何优雅地删除GitHub仓库中的特定commit历史
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…...
JS之短路操作符
短路操作符(Short-circuit Operator)是 JavaScript 中的一个概念,这些操作符同样适用于 TypeScript,因为 TypeScript 是 JavaScript 的类型超集。短路操作符主要包括逻辑“与”(&&)和逻辑“或”&am…...
【Linux】安装PHP扩展-redis
说明 本文档是在centos7.6的环境下,安装PHP7.4之后,安装对应的PHP扩展包redis。 一、下载redis扩展 pecl官方地址:PECL :: The PHP Extension Community Library 下载的版本是:redis-5.3.7.tgz 二、安装redis扩展 1.上传 redis 压缩包到…...
内衣洗衣机怎么选?分享五款人气巅峰机型,选对不选贵
随着科技的不断发展,内衣裤洗衣机成为了家庭必备的家电之一。选择一个好的品牌对于日后的使用体验至关重要。市场上内衣洗衣机型号繁多,究竟哪个牌子好用呢?下面给大家分享五款无论是口碑还是价格,都称得上是公认好用又实惠的内衣…...
OpenMesh入门,安装,运行示例Hello World
安装 环境 win10,qt5 源码下载编译 进入OpenMesh官网OpenMesh官网 https://www.graphics.rwth-aachen.de/software/openmesh/download/ 使用cmake gui 注意:先安装qt5 使用 CMake-Gui 构建 vs 2019 项目 注意 where is the source code 是<project…...
std::env是什么库?|Python一对一教学答疑
你好,我是悦创。 std::env 是 Rust 标准库中的一个模块,提供了访问操作系统环境的功能,比如处理环境变量、程序参数等。这个模块包含了一系列的函数和类型,用于管理与程序执行环境相关的信息。以下是 std::env 模块提供的一些主要…...
Go语言--广播式并发聊天服务器
实现功能 每个客户端上线,服务端可以向其他客户端广播上线信息;发送的消息可以广播给其他在线的客户支持改名支持客户端主动退出支持通过who查找当前在线的用户超时退出 流程 变量 用户结构体 保存用户的管道,用户名以及网络地址信息 typ…...
Spring MVC 全注解开发
1. Spring MVC 全注解开发 文章目录 1. Spring MVC 全注解开发2. web.xml 文件 的替代2.1 Servlet3.0新特性2.2 编写 WebAppInitializer 3. Spring MVC的配置3.1 Spring MVC的配置:开启注解驱动3.2 Spring MVC的配置:视图解析器3.3 Spring MVC的配置&…...
MQTT——Mosquitto使用(Linux订阅者+Win发布者)
前提:WSL(Ubuntu22)作为订阅者,本机Win10作为发布者。 1、Linux安装Mosquitto 命令行安装。 sudo apt-get install mosquitto 以上默认只安装了mosquitto的服务,不带测试客户端工具mosquitto_sub和mosquitto_pub。如…...
ArcGIS识别不GDB文件地理数据库显示为空?
点击下方全系列课程学习 点击学习—>ArcGIS全系列实战视频教程——9个单一课程组合系列直播回放 点击学习——>遥感影像综合处理4大遥感软件ArcGISENVIErdaseCognition 我们经常会碰到拷贝的GDB文件ArcGIS无法识别,软件只是把他当做普通的文件夹去看待&am…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...
Linux基础开发工具——vim工具
文章目录 vim工具什么是vimvim的多模式和使用vim的基础模式vim的三种基础模式三种模式的初步了解 常用模式的详细讲解插入模式命令模式模式转化光标的移动文本的编辑 底行模式替换模式视图模式总结 使用vim的小技巧vim的配置(了解) vim工具 本文章仍然是继续讲解Linux系统下的…...
深入浅出JavaScript中的ArrayBuffer:二进制数据的“瑞士军刀”
深入浅出JavaScript中的ArrayBuffer:二进制数据的“瑞士军刀” 在JavaScript中,我们经常需要处理文本、数组、对象等数据类型。但当我们需要处理文件上传、图像处理、网络通信等场景时,单纯依赖字符串或数组就显得力不从心了。这时ÿ…...
使用 uv 工具快速部署并管理 vLLM 推理环境
uv:现代 Python 项目管理的高效助手 uv:Rust 驱动的 Python 包管理新时代 在部署大语言模型(LLM)推理服务时,vLLM 是一个备受关注的方案,具备高吞吐、低延迟和对 OpenAI API 的良好兼容性。为了提高部署效…...
关于 ffmpeg设置摄像头报错“Could not set video options” 的解决方法
若该文为原创文章,转载请注明原文出处 本文章博客地址:https://hpzwl.blog.csdn.net/article/details/148515355 长沙红胖子Qt(长沙创微智科)博文大全:开发技术集合(包含Qt实用技术、树莓派、三维、OpenCV…...
