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

代码随想录算法训练营第二十一天 | 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 总结 自己实现中遇到哪些困难 一句话讲明白问题分类 组合问题和分割问题都是收集树的叶子节点&#xff0c;子集问题是找树的所有节点&#xff01;切割字符串问题回顾 昨天的切割回文子串&#xff0c;和今天的切割ip地址&#xff0c;都是需要将字符串拆分成 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 初始化完成时触发&#xff08;全局只触发一次&#xff09;&#xff0c…...

边缘提取函数 [OPENCV--2]

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

插值原理(数值计算方法)

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

【Pikachu】SSRF(Server-Side Request Forgery)服务器端请求伪造实战

尽人事以听天命 1.Server-Side Request Forgery服务器端请求伪造学习 SSRF&#xff08;服务器端请求伪造&#xff09;攻击的详细解析与防范 SSRF&#xff08;Server-Side Request Forgery&#xff0c;服务器端请求伪造&#xff09; 是一种安全漏洞&#xff0c;它允许攻击者通…...

IDEA怎么定位java类所用maven依赖版本及引用位置

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

Discuz论坛网站管理员的默认用户名admin怎么修改啊?

当我们在某个论坛注册账号后&#xff0c;处于某种原因想要修改用户名&#xff0c;该如何修改&#xff1f; Discuz论坛网站管理员处于安全性或某种原因想要修改默认用户名admin该如何修改&#xff1f;驰网飞飞和你分享 其实非常简单&#xff0c;但是普通用户没有修改权限&…...

BIO、NIO、AIO的区别?

文章目录 BIO、NIO、AIO的区别&#xff1f;为什么不使用java 原生nio哪些项目使用了netty BIO阻塞I/O存在问题 NIO&#xff08;nonblocking IO&#xff09;Java NIO channel(通道)、buffer、selector&#xff08;选择器&#xff09; AIO(Asynchronous I/O&#xff09; BIO、NIO…...

音视频入门基础:MPEG2-TS专题(7)——FFmpeg源码中,读取出一个transport packet数据的实现

一、引言 从《音视频入门基础&#xff1a;MPEG2-TS专题&#xff08;3&#xff09;——TS Header简介》可以知道&#xff0c;TS格式有三种&#xff1a;分别为transport packet长度固定为188、192和204字节。而FFmpeg源码中是通过read_packet函数从一段MPEG2-TS传输流/TS文件中读…...

Flutter中sqflite的使用案例

目录 引言 安装sqflite 创建表 查询数据 添加数据 删除数据 更新数据 完整使用案例 引言 随着移动应用的发展&#xff0c;本地数据存储成为了一个不可或缺的功能。在Flutter中&#xff0c;sqflite 是一个非常流行且强大的SQLite插件&#xff0c;它允许开发者在移动设备…...

【2024 Optimal Control 16-745】【Lecture 2】integrators.ipynb功能分析

代码功能分析 导入库和项目设置 import Pkg; Pkg.activate(__DIR__); Pkg.instantiate()功能&#xff1a;激活当前文件夹为 Julia 项目环境&#xff0c;并安装当前项目中缺失的依赖包。 import Pkg&#xff1a; 导入 Julia 的包管理模块 Pkg&#xff0c;用于管理项目依赖。 …...

【linux】ubuntu下常用快捷键【笔记】

环境 硬件&#xff1a;通用PC 系统&#xff1a;Ubuntu 20.04 软件 &#xff1a; 打开终端窗口&#xff1a;Ctrl Alt T 关闭当前窗口&#xff1a;Alt F4 改变窗口大小&#xff1a;Alt F8 移动窗口&#xff1a; Alt F7 配合 “←”、“→”、“↑”、“↓”来移动窗口 …...

【Linux】常用命令练习

一、常用命令 1、在/hadoop目录下创建src和WebRoot两个文件夹 分别创建&#xff1a;mkdir -p /hadoop/src mkdir -p /hadoop/WebRoot 同时创建&#xff1a;mkdir -p /hadoop/{src,WebRoot}2、进入到/hadoop目录&#xff0c;在该目录下创建.classpath和README文件 分别创建&am…...

力扣-Hot100-数组【算法学习day.37】

前言 ###我做这类文档一个重要的目的还是给正在学习的大家提供方向&#xff08;例如想要掌握基础用法&#xff0c;该刷哪些题&#xff1f;&#xff09;我的解析也不会做的非常详细&#xff0c;只会提供思路和一些关键点&#xff0c;力扣上的大佬们的题解质量是非常非常高滴&am…...

表格不同类型的数据如何向量化?

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

成都栩熙酷,电商服务新选择

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

【java基础】微服务篇

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

【LLM训练系列02】如何找到一个大模型Lora的target_modules

方法1&#xff1a;观察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提供了一套基础组件&#xff0c;类似HTML里的标签元素&#xff0c;不推荐在uni-app中使用使用div等HTML标签。在uni-app中&#xff0c;对应<div>的标签是view&#xff0c;对应<span>的是text&#xff0c;对应<a>的是navigator&#xff0c;常用uni-app…...

基于Amazon Bedrock:一站式多模态数据处理新体验

目录 引言 关于Amazon Bedrock 基础模型体验 1、进入环境 2、发现模型及快速体验 3、打开 Amazon Bedrock 控制台 4、通过 Playgrounds 体验模型 &#xff08;1&#xff09;文本生成 &#xff08;2&#xff09;图片生成 关于资源清理 结束语 引言 在云计算和人工智能…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...