代码随想录算法训练营第二十一天 | 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)图片生成 关于资源清理 结束语 引言 在云计算和人工智能…...
C#实战:基于WebAPI与Modbus构建EMS核心采集服务
1. 为什么需要EMS核心采集服务? 在工业现场,我们经常会遇到几十台甚至上百台智能电表、传感器等设备需要监控。这些设备可能来自不同厂家,使用不同的通信协议,数据格式也各不相同。想象一下,如果每个设备都需要单独开发…...
OpenClaw隐私方案:nanobot镜像本地化部署与敏感数据处理实践
OpenClaw隐私方案:nanobot镜像本地化部署与敏感数据处理实践 1. 为什么需要本地化部署的AI助手? 去年在处理一份涉及客户隐私的法律文件时,我遇到了一个两难选择:要么手动逐条整理数百页文档,要么使用云端AI工具但面…...
OpenClaw负载测试:GLM-4.7-Flash并发处理能力评估
OpenClaw负载测试:GLM-4.7-Flash并发处理能力评估 1. 测试背景与目标 上周在尝试用OpenClaw自动化处理一批市场调研报告时,遇到了一个典型问题:当我同时提交20份PDF文件让AI助手提取关键数据时,系统开始出现响应延迟和部分任务超…...
PTA L1-064 AI核心代码:从‘估值一亿’到‘精准实现’的避坑指南
1. 这道题为什么值"一亿"? PTA L1-064被戏称为"估值一亿"的题目,主要因为它在字符串处理中埋了多个隐蔽的坑点。我第一次做这道题时,看着题目要求觉得规则很明确,不就是几个字符串替换吗?结果提交…...
OpenClaw任务编排:GLM-4.7-Flash复杂流程设计
OpenClaw任务编排:GLM-4.7-Flash复杂流程设计 1. 为什么需要任务编排 去年我接手了一个市场分析项目,需要每周手动收集竞品动态并生成报告。重复性的复制粘贴和格式调整消耗了大量时间,直到发现OpenClaw可以通过编排GLM-4.7-Flash模型实现全…...
互联网大厂 Java 面试实战:一次“高并发系统追问”下的真实对话
在大多数 Java 面试中,真正拉开差距的从来不是“你会多少知识点”,而是当系统出现问题时,你是否知道该怎么扛。很多候选人熟悉各种八股文,但一旦进入场景题就会卡住。下面通过一场更贴近真实大厂风格的面试,对话式还原…...
1756-L55处理器单元
1756-L55 处理器单元(ControlLogix 系列PLC CPU)一、主要特点高性能处理器,适合中大型控制系统支持多任务运行与快速扫描支持在线编程与程序修改模块化结构,扩展灵活支持本地及远程I/O控制可实现冗余系统,提高可靠性支…...
MySQL技巧(八) :死锁解决与实战案例
在数据库高并发场景下,死锁是一个绕不开的经典难题。两个或多个事务相互持有对方需要的锁,导致都无法继续执行,就像两辆车在狭窄路口互不相让。本文将带你从原理到实战,掌握死锁的排查、解决和预防全流程。一、死锁快速定位当应用…...
光阀的“第二曲线”:投影行业LCOS技术现状与发展趋势分析
1. 报告导读与核心摘要 在投影显示技术的版图中,LCoS(硅基液晶,Liquid Crystal on Silicon)长期处于一种微妙的位置:它拥有DLP无法比拟的画质潜力,却因成本和体积问题始终未能真正撼动DLP的市场地位。然而,2025-2026年行业展会上的一系列技术突破,正在改写这一格局。 …...
Arduino高性能WebSocket客户端库深度解析
1. Arduino-Websocket-Fast 库深度解析:面向嵌入式物联网的高性能 WebSocket 客户端实现1.1 设计动因与工程定位在嵌入式物联网(IoT)系统开发中,WebSocket 协议因其全双工、低开销、长连接特性,已成为设备与云平台间实…...
