代码随想录算法训练营第二十一天 | 93.复原IP地址 | 78.子集
Day 20 总结
- 自己实现中遇到哪些困难
- 一句话讲明白问题分类
- 组合问题和分割问题都是收集树的叶子节点,子集问题是找树的所有节点!
- 切割字符串问题回顾
- 昨天的切割回文子串,和今天的切割ip地址,都是需要将字符串拆分成 n 份。
- 只不过每一小份的长度不定,切完当前这一小份,再交给下层去切割剩余部分。
- 一句话讲明白问题分类
- 今日收获,记录一下自己的学习时间
- 17:30 - 19:00
93.复原IP地址
题目链接/文章讲解:代码随想录
题目链接:https://leetcode.cn/problems/restore-ip-addresses/
题目描述:
有效 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-255。
1.字符串分隔:一定是从前向后进行切割,先切割一个数字出来,然后再对剩下的字符串再次进行切割。然后要检查当前切割出来的字符串是不是合格的,如果前面都切不出来合格的字符串,后面的切割也没有意义,直接结束该分支的搜索。找到了一个合适的字符串,就传递到下层一次,再剩余字符串中继续切割。当前层切割的字符串长度慢慢递增。
2.检查切割的结果:到达搜索树的结尾时,要确保整个字符串已经切割完了,并且切割成了四个部分。排除不符合条件的分支,并把切割完的字符串收集到结果集合中。
回溯模板:
代码实现:
class Solution {public List<String> results = new ArrayList<>();public List<String> path = new ArrayList<>();public List<String> restoreIpAddresses(String s) {backtrack(s, 0);return results;}// 参数:// 返回值:public void backtrack(String s, int startIndex) {// 终止条件if (path.size() > 4) {return;} if (startIndex == s.length() && path.size() == 4) {StringBuffer ipAddr = new StringBuffer();for (int i=0; i<4; i++) {ipAddr.append(path.get(i));if (i < 3) {ipAddr.append(".");}}results.add(ipAddr.toString());}// 回溯单层搜索过程for (int i=startIndex; i<s.length(); i++){if (!isValid(s, startIndex, i+1)) {continue;}path.add(s.substring(startIndex, i+1));backtrack(s, i+1);path.remove(path.size()-1);}}public boolean isValid(String s, int start, int end) {if (end - start > 3) {return false;}if (s.charAt(start) == '0') {if (end - start > 1) {return false;}}if (end - start > 2) {if (s.charAt(start) == '0') {return false;}if (Integer.parseInt(s.substring(start,end)) > 255) {return false;}}return true;}
}// 实现方案2
class Solution {List<Integer> path = new ArrayList<>();List<String> results = new ArrayList<>();char[] arr;public List<String> restoreIpAddresses(String s) {arr = s.toCharArray();backtrack(0);return results;}public void backtrack(int startIdx) {if (path.size() > 4 || startIdx > arr.length) return;if (startIdx == arr.length && path.size() == 4) {String s = "";for (Integer i : path) s = s+i+".";results.add(s.substring(0,s.length()-1));}for (int i=startIdx; i<arr.length; i++) {int num = getNum(startIdx, i);if (num == -1) return;path.add(num);backtrack(i+1);path.remove(path.size()-1);}}public int getNum(int start, int end) {// 小于四位数if (end - start >= 3) return -1;// 没有前导0if (arr[start] == '0') {if (end > start) return -1;return 0;}// 1-255int num = 0;while (start <= end) {num = num * 10 + (int)(arr[start++]-'0');}if (num > 255) return -1;return num;}
}
78.子集
题目链接/文章讲解:代码随想录
题目链接:https://leetcode.cn/problems/subsets/
题目描述:
给你一个整数数组 nums
,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
实现思路:
收集搜索树上的所有节点。
回溯模板:
代码实现:
class Solution {// 全局变量免去参数传递List<List<Integer>> results = new ArrayList<>();List<Integer> path = new ArrayList<>();int[] nums;public List<List<Integer>> subsets(int[] nums) {this.nums = nums;results.add(new ArrayList<>(path)); // 空集backtrace(0);return results;}public void backtrace(int startIdx) {// 到达底搜索树底层,向上返回if (startIdx >= nums.length) return;for (int i=startIdx; i<nums.length; i++) {path.add(nums[i]);results.add(new ArrayList<>(path)); // 收集所有情况backtrace(i+1);path.remove(path.size()-1);}}
}
相关文章:
代码随想录算法训练营第二十一天 | 93.复原IP地址 | 78.子集
Day 20 总结 自己实现中遇到哪些困难 一句话讲明白问题分类 组合问题和分割问题都是收集树的叶子节点,子集问题是找树的所有节点!切割字符串问题回顾 昨天的切割回文子串,和今天的切割ip地址,都是需要将字符串拆分成 n 份。只不过…...
#Uniapp篇:支持纯血鸿蒙发布适配UIUI
uni-ui梳理 组件生命周期 https://uniapp.dcloud.net.cn/tutorial/page.html#componentlifecycle 页面生命周期 https://uniapp.dcloud.net.cn/collocation/App.html#applifecycle onLaunch 当uni-app 初始化完成时触发(全局只触发一次),…...

边缘提取函数 [OPENCV--2]
OPENCV中最常用的边界检测是CANNY函数 下面展示它的用法 通常输入一个灰度图像(边界一般和颜色无关)这样也可以简化运算cv::Canny(inmat , outmat , therhold1, therhold2 ) 第一个参数是输入的灰度图像,第二个是输出的图像这两个参数都是引用…...

插值原理(数值计算方法)
插值原理(数值计算方法) 一. 原理介绍二. 图例三. 唯一性表述 一. 原理介绍 在数学中,插值(Interpolation)是指通过已知的离散数据点,构造一个连续的函数,该函数能够精确地通过这些数据点&#…...

【Pikachu】SSRF(Server-Side Request Forgery)服务器端请求伪造实战
尽人事以听天命 1.Server-Side Request Forgery服务器端请求伪造学习 SSRF(服务器端请求伪造)攻击的详细解析与防范 SSRF(Server-Side Request Forgery,服务器端请求伪造) 是一种安全漏洞,它允许攻击者通…...

IDEA怎么定位java类所用maven依赖版本及引用位置
在实际开发中,我们可能会遇到需要搞清楚代码所用依赖版本号及引用位置的场景,便于排查问题,怎么通过IDEA实现呢? 可以在IDEA中打开项目,右键点击maven的pom.xml文件,或者在maven窗口下选中项目,…...

Discuz论坛网站管理员的默认用户名admin怎么修改啊?
当我们在某个论坛注册账号后,处于某种原因想要修改用户名,该如何修改? Discuz论坛网站管理员处于安全性或某种原因想要修改默认用户名admin该如何修改?驰网飞飞和你分享 其实非常简单,但是普通用户没有修改权限&…...
BIO、NIO、AIO的区别?
文章目录 BIO、NIO、AIO的区别?为什么不使用java 原生nio哪些项目使用了netty BIO阻塞I/O存在问题 NIO(nonblocking IO)Java NIO channel(通道)、buffer、selector(选择器) AIO(Asynchronous I/O) BIO、NIO…...
音视频入门基础:MPEG2-TS专题(7)——FFmpeg源码中,读取出一个transport packet数据的实现
一、引言 从《音视频入门基础:MPEG2-TS专题(3)——TS Header简介》可以知道,TS格式有三种:分别为transport packet长度固定为188、192和204字节。而FFmpeg源码中是通过read_packet函数从一段MPEG2-TS传输流/TS文件中读…...
Flutter中sqflite的使用案例
目录 引言 安装sqflite 创建表 查询数据 添加数据 删除数据 更新数据 完整使用案例 引言 随着移动应用的发展,本地数据存储成为了一个不可或缺的功能。在Flutter中,sqflite 是一个非常流行且强大的SQLite插件,它允许开发者在移动设备…...

【2024 Optimal Control 16-745】【Lecture 2】integrators.ipynb功能分析
代码功能分析 导入库和项目设置 import Pkg; Pkg.activate(__DIR__); Pkg.instantiate()功能:激活当前文件夹为 Julia 项目环境,并安装当前项目中缺失的依赖包。 import Pkg: 导入 Julia 的包管理模块 Pkg,用于管理项目依赖。 …...
【linux】ubuntu下常用快捷键【笔记】
环境 硬件:通用PC 系统:Ubuntu 20.04 软件 : 打开终端窗口:Ctrl Alt T 关闭当前窗口:Alt F4 改变窗口大小:Alt F8 移动窗口: Alt F7 配合 “←”、“→”、“↑”、“↓”来移动窗口 …...
【Linux】常用命令练习
一、常用命令 1、在/hadoop目录下创建src和WebRoot两个文件夹 分别创建:mkdir -p /hadoop/src mkdir -p /hadoop/WebRoot 同时创建:mkdir -p /hadoop/{src,WebRoot}2、进入到/hadoop目录,在该目录下创建.classpath和README文件 分别创建&am…...

力扣-Hot100-数组【算法学习day.37】
前言 ###我做这类文档一个重要的目的还是给正在学习的大家提供方向(例如想要掌握基础用法,该刷哪些题?)我的解析也不会做的非常详细,只会提供思路和一些关键点,力扣上的大佬们的题解质量是非常非常高滴&am…...

表格不同类型的数据如何向量化?
在进行机器学习项目时,首先需要获取数据,这些数据可以来自数据库、API、网络抓取,或从CSV、Excel等文件中读取。数据可能包含数值、文本和类别等多种特征,但原始数据通常无法直接用于训练模型。 数据预处理包括清洗、填补缺失值和…...

成都栩熙酷,电商服务新选择
在当今数字经济蓬勃发展的时代,电商平台已成为推动商业创新、促进消费升级的重要力量。抖音小店,作为短视频与电商深度融合的产物,凭借其独特的社交属性和内容营销优势,迅速吸引了大量用户和商家的关注。在这场变革中,…...

【java基础】微服务篇
参考黑马八股视频。 目录 Spring Cloud 5大组件 注册中心 负载均衡 限流 CAP和BASE 分布式事务解决方案 分布式服务的接口幂等性 分布式任务调度 Spring Cloud 5大组件 注册中心 Eureka的作用 健康监控 负载均衡 限流 漏桶固定速率,令牌桶不限速 CAP和BA…...

【LLM训练系列02】如何找到一个大模型Lora的target_modules
方法1:观察attention中的线性层 import numpy as np import pandas as pd from peft import PeftModel import torch import torch.nn.functional as F from torch import Tensor from transformers import AutoTokenizer, AutoModel, BitsAndBytesConfig from typ…...

uni-app快速入门(八)--常用内置组件(上)
uni-app提供了一套基础组件,类似HTML里的标签元素,不推荐在uni-app中使用使用div等HTML标签。在uni-app中,对应<div>的标签是view,对应<span>的是text,对应<a>的是navigator,常用uni-app…...

基于Amazon Bedrock:一站式多模态数据处理新体验
目录 引言 关于Amazon Bedrock 基础模型体验 1、进入环境 2、发现模型及快速体验 3、打开 Amazon Bedrock 控制台 4、通过 Playgrounds 体验模型 (1)文本生成 (2)图片生成 关于资源清理 结束语 引言 在云计算和人工智能…...

第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...

【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...