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

代码随想录算法训练营第27天|93.复原IP地址、78.子集、90.子集二

目录

  • 一、力扣93.复原IP地址
    • 1.1 题目
    • 1.2 思路
    • 1.3 代码
    • 1.4 总结
  • 二、力扣78.子集
    • 2.1 题目
    • 2.2 思路
    • 2.3 代码
    • 2.4 总结
  • 三、力扣90.子集二
    • 3.1 题目
    • 3.2 思路
    • 3.3 代码
    • 3.4 总结

一、力扣93.复原IP地址

(比较困难,做起来很吃力)

1.1 题目

在这里插入图片描述

1.2 思路

同样是分割问题,不过本题需要在字符串上直接进行操作,由于String是不可修改的,所以需要借助StringBuilder来处理字符串的增减及拼接操作;
递归终止条件:设置pointCount来记录点的数量,当ip地址中已加入三个点时终止,然后记得再判断最后一段的有效性;
回溯:pointCount的减减以及删掉刚刚加入到字符串里的点;

1.3 代码

class Solution {public List<String> res = new ArrayList<>();public int pointCount = 0;//ip地址中点的数量public List<String> restoreIpAddresses(String s) {//java处理字符串用StringBuilderStringBuilder str = new StringBuilder(s);backTracking(str,0);return res;}public void backTracking(StringBuilder str,int startIndex){//递归终止条件if(pointCount == 3){//还剩最后一段的合法性未判断if(isVaild(str,startIndex,str.length()-1)){res.add(str.toString());}return;}//递归+回溯for(int i = startIndex;i < str.length();i++){if(isVaild(str,startIndex,i)){//合法,那么加点切割str.insert(i+1,".");pointCount++;backTracking(str,i+2);str.deleteCharAt(i+1);pointCount--;}else{break;}}}//判断字符串str[left,right]左闭右闭是否满足ip段要求public boolean isVaild(StringBuilder str,int left,int right){if(left > right){return false;}//不能含有前导0if(str.charAt(left) == '0' && left != right){return false;}//介于0-255之间int num = 0;for(int i = left;i <= right ;i++){if(str.charAt(i) < '0' || str.charAt(i) > '9'){return false;}num = (num * 10) + (str.charAt(i)-'0');if(num > 255){return false;}}return true;}}

1.4 总结

StringBuilder使用方法:https://blog.csdn.net/qq_50617271/article/details/112686826
判断ip段是否合法时的方法isVaild()中的循环: s[i],表示字符串中的一位,S【i】-0. 把字符串转化成数字。 num*10,是下一个循环的时候上一位数字要左移。假设s=【255】, 循环三次的结果就是 2->25->255.

二、力扣78.子集

2.1 题目

在这里插入图片描述

2.2 思路

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话,那么组合问题和分割问题都是收集树的叶子节点,而子集问题是找树的所有节点!
自己的想法:和组合问题类似,不同的地方是树结构的每个结点的数据都要加入到结果集中,即path当中每加入一个元素就需要将path加入到res结果集里。

2.3 代码

class Solution {public List<List<Integer>> res = new ArrayList<>();public List<Integer> path = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {res.add(new ArrayList<>(path));//添加空集backTracking(nums,0);return res;}public void backTracking(int[] nums,int startIndex){//递归终止条件if(startIndex == nums.length){return;}for(int i = startIndex; i< nums.length;i++){path.add(nums[i]);res.add(new ArrayList<>(path));backTracking(nums,i+1);path.remove(path.size()-1);}}
}

2.4 总结

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话,那么组合问题和分割问题都是收集树的叶子节点,而子集问题是找树的所有节点!

三、力扣90.子集二

3.1 题目

在这里插入图片描述

3.2 思路

在上一题子集问题的基础上多了个条件:可能包含重复元素,那么就需要先排序,然后按照树的结构横向去重,即兄弟之间去重。

3.3 代码

class Solution {public List<List<Integer>> res = new ArrayList<>();public List<Integer> path = new ArrayList<>();boolean[] used;//记录数据元素是否使用过,用来去重public List<List<Integer>> subsetsWithDup(int[] nums) {used = new boolean[nums.length];for(int i = 0;i<nums.length;i++){used[i] = false;}//先向结果集中加入空集res.add(new ArrayList<>(path));//对原数组排序Arrays.sort(nums);backTracking(nums,0);return res;}//递归回溯public void backTracking(int[] nums,int startIndex){//递归终止条件if(startIndex == nums.length){return;}for(int i = startIndex;i<nums.length;i++){//兄弟去重if(i!=0 && nums[i] == nums[i-1] && used[i-1] == false){continue;}path.add(nums[i]);res.add(new ArrayList<>(path));used[i] = true;backTracking(nums,i+1);path.remove(path.size()-1);used[i] = false;}}
}

3.4 总结

横向(兄弟)去重:注意是used[i-1] == false;即前一个相同的元素没有被用,也就是如果用当前位置元素的话汇合上一次for循环i-1的组合重复,所有要continue,避免重复,即横向(兄弟)去重。

            //兄弟去重if(i!=0 && nums[i] == nums[i-1] && used[i-1] == false){continue;}

相关文章:

代码随想录算法训练营第27天|93.复原IP地址、78.子集、90.子集二

目录 一、力扣93.复原IP地址1.1 题目1.2 思路1.3 代码1.4 总结 二、力扣78.子集2.1 题目2.2 思路2.3 代码2.4 总结 三、力扣90.子集二3.1 题目3.2 思路3.3 代码3.4 总结 一、力扣93.复原IP地址 &#xff08;比较困难&#xff0c;做起来很吃力&#xff09; 1.1 题目 1.2 思路 …...

Java微服务轻松部署服务器

我们在日常开发微服务之后需要再服务器上面部署&#xff0c;那么如何进行部署呢&#xff0c;先把微服务的各个服务和中间件以及对应的端口列举出来&#xff0c;都打包成镜像&#xff0c;以及前端代码部署的nginx&#xff0c;使用docker-compose启动&#xff0c;访问服务器nginx…...

Wordpress站点通过修改.htaccess 设置重定向实现强制 https 访问

要在WordPress站点上通过修改.htaccess文件实现强制HTTPS访问&#xff0c;您可以按照以下步骤进行操作&#xff1a; 登录到WordPress站点管理后台。 在文件管理器或通过FTP访问网站根目录&#xff0c;找到并打开名为 .htaccess 的文件。 在打开的文件中添加以下代码&#xf…...

人大金仓助力国家电网调度中心培养国产数据库专家人才

近日,为进一步提升调度自动化安全可靠水平,提高电网数据应用效能,人大金仓助力国家电网调度中心培养国产数据库专家人才。 调度自动化系统拥有海量电网数据资源,是支撑电网安全经济优质运行的重要保障。数据库是调度自动化系统稳定运行的基石之一,其结构严谨、运行稳定、扩展灵…...

什么是增强型SSL证书?购买一张需要多少钱?

增强型SSL证书是一种提供更高级别安全验证与用户信任度的网络安全工具&#xff0c;也被称为EV证书。相较于DV&#xff08;域名验证&#xff09;和OV&#xff08;组织验证&#xff09;证书&#xff0c;它通过严格的身份核实流程确保网站所有者的合法性和真实性。 首先&#xff0…...

C++:函数传参到函数执行结束发生了什么

首先要明确两个概念 函数实参的入栈从右向左栈区从高地址向低地址偏移 接下来看下面一段代码 void fun(int a,int b,int c){std::cout<<&a<<" "<<&b<<" "<<&c<<std::endl; } int main(){fun(1,2,3); }…...

QT中dumpcpp以及dumpdoc使用

qt中调用COM的方式方法有四种&#xff0c;参考解释在 Qt 中使用 ActiveX 控件和 COM (runebook.dev) 介绍dumpcpp的使用方法Qt - dumpcpp 工具 (ActiveQt) (runebook.dev)&#xff1a; 在安装好了的qt电脑上&#xff0c;通过powershell窗口来实现&#xff0c;powershell比cmd要…...

RPM与DNF的操作实践

这几课有三个目标&#xff1a; 第一步&#xff1a;先配置软件源 跳转到yum.repos.d目录&#xff0c;用vim创建一个openeuler_x84_64.repo文件。这个文件就是我们将会用到的软件源。 我们在里面添加这些东西&#xff0c;保存并退出即可。 然后&#xff0c;我们用yum list all就…...

车道线检测之LaneNet

论文&#xff1a;Towards End-to-End Lane Detection: an Instance Segmentation Approach Github&#xff1a;https://github.com/MaybeShewill-CV/lanenet-lane-detection?tabreadme-ov-file 论文提出一种车道线检测网络LaneNet&#xff0c;该网络以enet为主干网络结构&…...

MySQL连接数不足导致服务异常GetConnectionTimeoutException

文章目录 场景复现解决方案一、调整连接数二、优化程序 场景复现 已经上线正常运行的项目突然很多功能无法使用&#xff0c;查看程序日志发现MySQL报错&#xff0c;异常信息: Could not open JDBC Connection for transaction; nested exception is com.alibaba.druid.pool.Ge…...

软考76-上午题-【面向对象技术3-设计模式】-创建型设计模式01

一、创建型设计模式一览 二、创建型设计模式 2-1、创建型设计模式的概念 一个类创建型模式使用继承改变被实例化的类&#xff1b; 一个对象创建型模式将实例化委托给另一个对象。 对应java的new一个对象。 2-2、简单工厂模式&#xff08;静态工厂方法&#xff09; 简单工厂…...

Matlab 双目相机标定(内置函数)

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 相机标定的目的就是要找到从世界坐标转换为图像坐标所用到的投影P矩阵各个系数(即相机的内参与外参)。具体过程如下所述: 1、首先我们需要获取一个已知图形的图像(这里我们使用MATLAB所提供的数据)。 2、找到同…...

【博客7.4】缤果Qt5_TWS串口调试助手V2.0 (高级篇)

超级好用的Qt5_TWS耳机串口调试助手 开发工具: qt-opensource-windows-x86-5.14.2 (编程语言C) 目录 前言 一、软件概要&#xff1a; 二、软件界面&#xff1a; 1.App演示 三、获取 >> 源码以及Git记录&#xff1a; 总结 前言 串口调试助手支持常用的50bps - 10M…...

CSS案例-4.padding导航栏练习

效果 相关数据: 上边框:3px,颜色#ff8500 下边框:1px,颜色#edeef0 背景颜色:#fcfcfc 高度:41px 内边距20px 字体颜色#4c4c4c 知识点 盒子边框border 属性 作用 border-width 定义边框粗细,单位px border-style 边框的样式 border-color 边框颜色 边框样式...

5.1.4.2、【AI技术新纪元:Spring AI解码】Llama2 Chat

Llama2 Chat Meta 的 Llama 2 Chat 是 Llama 2 系列大型语言模型的一部分。它在基于对话的应用程序中表现出色,参数规模范围从 70 亿到 700 亿不等。利用公共数据集和超过 100 万次人类注释,Llama Chat 提供了上下文感知的对话。 通过从公共数据源获取的 2 万亿标记进行训练…...

后台发送GET/POST方法

前言: 1,get请求 2,post请求 3,post,get通用方法 4,其他的get,post写法 正文: 1,get请求 import org.apache.commons.httpclient.HttpClient; import org.apache.commons.httpclient.HttpException; import org.apache.commons.httpclient.HttpStatus; import or…...

计算机考研|双非一战135上岸,408经验分享+复盘

计算机专业的同学真的别想的太天真&#xff01; 相比于其他专业&#xff0c;计算机专业的同学其实还是很有优势的 但是现在随着计算机专业的同学越来越多&#xff0c;找工作的困难程度以及学历自然而然被卷起来了 以前的算法岗基本要求在本科以上&#xff0c;现在基本都是非92研…...

低代码与数字化工具:重塑软件开发的新范式

随着信息技术的飞速发展&#xff0c;软件开发已成为推动数字化转型的核心力量。在这个变革的时代&#xff0c;低代码与数字化工具逐渐崭露头角&#xff0c;它们不仅简化了开发过程&#xff0c;还大大提高了开发效率&#xff0c;成为推动软件开发领域变革的重要力量。 低代码&am…...

如何使用 ArcGIS Pro 生成TIN

三角网是一种常用于表示地表地形的数字地球模型&#xff08;DEM&#xff09;方式&#xff0c;我们可以通过 ArcGIS Pro 将等高线和高程点转换为TIN&#xff0c;这里为大家介绍一下转换方法&#xff0c;希望能对你有所帮助。 数据来源 教程所使用的数据是从水经微图中下载的高…...

你真的会做抖音小店吗?你做抖店的方法是正确的吗?教学分享

大家好&#xff0c;我是电商花花。 新的一年&#xff0c;不少做抖店的商家都会产生一个疑问&#xff0c;2024年抖音小店无货源还能继续做吗&#xff1f; 做无货源模式还会被处罚吗&#xff1f; 先说答案&#xff0c;2024年抖音小店无货源能做&#xff0c;不仅能做且仍然是抖音…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...