【CT】LeetCode手撕—93. 复原 IP 地址

目录

  • 题目
  • 1- 思路
  • 2- 实现
    • ⭐93. 复原 IP 地址——题解思路
  • 3- ACM 实现


题目

  • 原题连接:93. 复原 IP 地址

1- 思路

模式识别:给一个 String 字符串 ——> 复原 IP 地址 ——> 回溯三部曲 ,回溯的切割问题 ——> 实现一个左闭右闭区间的 isValid 实现
回溯三部曲

  • 1. 定义回溯参数及返回值
    • public void backTracing(String s ,int startIndex,int pointSum)
    • startIndex :代表切割线
    • pointSum :代表 逗点数量
  • 2. 回溯终止条件
    • 用一个全局变量 count 来计算逗号的数量,当逗号的数量达到 3 则此时终止
  • 3. 回溯逻辑
    • for 中 i 从 startIndex 开始,遍历到 s.length()

IP地址合法性判断

    1. 不能以 0 开头
    1. 遍历判断不能是非法字符
    1. 求和不能大于 255

2- 实现

⭐93. 复原 IP 地址——题解思路

在这里插入图片描述

class Solution {
    public List<String> restoreIpAddresses(String s) {
        backTracing(s,0,0);
        return res;
    }


    // 回溯
    List<String> res = new ArrayList<>();
    public void backTracing(String s, int startIndex,int pointSum){

        //2. 终止条件
        if(pointSum==3){
            if(isValid(s,startIndex,s.length()-1)){
                res.add(s);
            }
            return;
        }

        //3. 遍历回溯逻辑
        for(int i = startIndex;i<s.length();i++){
            if(isValid(s,startIndex,i)){
                s = s.substring(0,i+1)+"."+s.substring(i+1);
                pointSum++;
                backTracing(s,i+2,pointSum);
                pointSum--;
                s = s.substring(0,i+1)+s.substring(i+2);
            }else{
                break;
            }
        }
    }

    public Boolean isValid(String s,int start,int end){
        if(start>end){
            return false;
        }
        if(start!=end && s.charAt(start)=='0'){
            return false;
        }
        // 遍历判断,字符合法 ,是否超过 255
        int sum = 0;
        for(int i = start;i <= end;i++){
            if(s.charAt(i) >'9' || s.charAt(i) <'0'){
                return false;
            }
            sum = sum*10 + (s.charAt(i)-'0');
            if(sum>255){
                return false;
            }
        }
        return true;
    }
}

3- ACM 实现

public class remakeIP {


    static List<String> res = new ArrayList<>();
    public static List<String> splitIP(String s){
        backTracing(s,0,0);
        return res;
    }

    // 回溯参数及返回值
    public static void backTracing(String s,int startIndex,int pointSum){
        // 2. 终止条件
        if(pointSum==3){
            if(isValid(s,startIndex,s.length()-1)){
                res.add(s);
            }
            return ;
        }

        //3. 回溯
        for(int i = startIndex; i < s.length();i++){
            if(isValid(s,startIndex,i)){
                s = s.substring(0,i+1) + "."+s.substring(i+1);
                pointSum++;
                backTracing(s,i+2,pointSum);
                s = s.substring(0,i+1)+s.substring(i+2);
                pointSum--;
            }else{
                break;
            }
        }
    }


    public static boolean isValid(String s ,int start,int end){
        if(start>end){
            return false;
        }
        // 判断前置 0
        if(start!=end && s.charAt(start)=='0'){
            return false;
        }
        // 遍历判断 非法字符 和 255
        int sum = 0;
        for(int i = start; i <= end;i++){
            if(s.charAt(i)>'9' || s.charAt(i)<'0'){
                return false;
            }
            sum = sum*10+(s.charAt(i)-'0');
            if(sum>255) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println("输入字符串s");
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        splitIP(input);
        for(String s : res){
            System.out.println(s+" ");
        }
    }
}


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/761701.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

小白入门云计算的最佳方式,是去考一张AWS证书

云计算的快速发展让它成为现代IT行业的核心技术之一。 作为一名初学者&#xff0c;如何高效地入门云计算&#xff1f; 我的建议是&#xff1a;考一张AWS证书。 AWS&#xff08;Amazon Web Services&#xff09;在云计算市场占据领先地位&#xff0c;它的认证体系既权威又全面&a…

实现Ubuntu计划任务的反弹shell

一、实验环境 Ubuntu&#xff1a;IP地址&#xff1a;192.168.223.156 Kali : IP地址&#xff1a;192.168.223.152 二、编写crontab计划任务 在Ubuntu的系统中使用crontab -e命令编写计划任务&#xff0c;如下所示&#xff1a; 作用&#xff1a;是将一个交互式的bash …

Kubernetes的发展历程:从Google内部项目到云原生计算的基石

目录 一、起源与背景 1.1 Google的内部项目 1.2 Omega的出现 二、Kubernetes的诞生 2.1 开源的决策 2.2 初期发布 三、Kubernetes的发展历程 3.1 社区的成长 3.2 生态系统的壮大 3.3 重大版本和功能 3.4 多云和混合云的支持 四、Kubernetes的核心概念 4.1 Pod 4.…

vscode 安装Vue插件

打开扩展面板 --> 点击左侧的扩展图标&#xff0c;或者按下快捷键 Ctrl Shift X 搜索插件,在搜索框中输入 Vue vue-helper 用来快捷提示&#xff0c;如果使用elementui的话&#xff0c;插件不会自动提示&#xff0c;安装了它&#xff0c;组件、属性都会有提示了 Vetur V…

硬核丨2024文本生成类AI产品横向评测报告

文本生成/写作”作为使用最高频的AI场景&#xff0c;各类产品如雨后春笋般出现。我们针对办公/学习的写作场景进行了全面系统的评测。希望此次评测结论能够帮您在工作学习中使用AI应用提效。 本次评测对象包含文心、通义、kimi等模型厂商及笔灵、迅捷、秘塔等应用厂商共13款产…

制造业如何拥抱数字化?百数服务商的转型策略与实践

制造业作为实体经济的主体部分&#xff0c;也是核心部分&#xff0c;发挥着基础性、主导性和引领性作用。推动制造业数字化转型是实现经济高质量发展的必由之路。 在这场数字化浪潮中&#xff0c;低代码平台作为一种新兴的技术手段&#xff0c;逐渐受到了企业的青睐。其能够在…

国产压缩包工具——JlmPackCore SDK说明(一)

一、什么是JlmPackCore SDK &#xff08;1&#xff09;自主可控 JlmPackCore是一套基于我国自主知识产权的核心算法发明专利——杰林码&#xff08;详系请参考《杰林码原理及应用》一书&#xff0c;也可以参考后续发表的相关论文&#xff09;&#xff0c;其中一篇会议论文&…

Eagle Trader的交易魅力!

这就是 Eagle Trader 的独特魅力所在 - 让交易者能够敏锐地捕捉到市场的脉搏&#xff0c;将图表上的每一个波动转化为盈利的机遇。在这里&#xff0c;您可以凭借自己的智慧和勇气&#xff0c;将复杂的市场数据转化为实际的收益。 Eagle Trader 提供了丰富的交易工具和资源&…

开源网安荣获第一新声“2024中国最佳信创安全厂商”,信创实力获认可

近日&#xff0c;由权威机构【第一新声】与【天眼查】联合发起的“2024中国最佳信创厂商系列榜单”评选中&#xff0c;开源网安以其技术创新能力和在信创领域持续投入&#xff0c;成功入选“中国最佳信创安全厂商”。 开源网安&#xff0c;作为软件安全领域创领者&#xff0c;自…

Fooocus模型配置中文教程

很多同学这里不知道该怎么选择。不知道每个模型效果&#xff0c;针对这个整理了一个表格。参考表格就可生成预期效果图。 下载地址&#xff1a; https://download.csdn.net/download/yuanshiren133/89503764

qt结合vs2022安装

进入清华大学开源软件&#xff1a; 清华大学开源软件镜像站 | Tsinghua Open Source Mirror 下载完成后&#xff0c;双击进行安装&#xff1a; 进入邮箱进行验证&#xff1a; 可能是因为网络问题&#xff0c;无法安装。 重新安装5.12.12版本。 安装后启动失败&#xff0c;重新…

高效的向量搜索算法——分层可导航小世界图(HNSW)

最近在接触大模型相关内容&#xff0c;发现一种高效的向量搜索算法HNSW&#xff0c;这里做一下记录。 在之前自己也接触过一段时间的复杂网络&#xff08;网络科学&#xff09;&#xff0c;没想到&#xff0c;将网络科学的思想引入到向量搜索算法中&#xff0c;可以产生令人眼前…

信必优持续践行ESG之绿色生活

在当今世界&#xff0c;可持续发展已成为全球共识&#xff0c;企业作为社会的重要参与者&#xff0c;肩负着推动环境、社会和治理&#xff08;ESG&#xff09;实践的重任。信必优始终致力于将ESG理念融入企业文化和运营的每一个层面。今天&#xff0c;我们将走进信必优的绿色生…

生成式AI:未来商业的变革者

在2023年&#xff0c;生成式人工智能&#xff08;GenAI&#xff09;的浪潮席卷了全球&#xff0c;成为科技领域最炙手可热的话题之一。它不仅改变了我们与机器的互动方式&#xff0c;更在商业创新和生产力提升方面发挥了巨大的作用。本文将深入探讨2024年生成式AI的应用模式、趋…

24年11月软考科目怎么选?这份备考指南很刚需

前几天软考出成绩了&#xff0c;不知道各位朋友们考的如何&#xff1f; 今年出分比往年早不少&#xff0c;也是玩了一波心跳与刺激。上半年的软考算是告一段落&#xff0c;下半年考试的朋友们可得上心了。 今天给大家整理了一份11月软考的备考攻略&#xff0c;从改革到选课备考…

git 提交代码忽略eslint代码检测

在暂存代码的时候会出现以上情况因为在提交代码的时候会默认运行代码进行检测&#xff0c;如果不符合代码规范就会进行报错 解决&#xff1a; 使用 git commit --no-verify -m xxx 忽略eslint的检测

如何使用ChatGPT提高数学建模竞赛的获奖概率

如何使用ChatGPT提高数学建模竞赛的获奖概率 数学建模助手GPT https://chatgpt-plus.top/g/g-OX0D7uMn9-shu-ju-jian-mo-zhu-shou-by-maynor 1. 问题分析与理解 在数学建模的初期&#xff0c;准确理解问题的背景和要求至关重要。通过使用ChatGPT&#xff0c;你可以&#xff…

Python自动化,实现自动登录并爬取商品数据,实现数据可视化

关于如何使用Python自动化登录天 猫并爬取商品数据的指南&#xff0c;我们需要明确这是一个涉及多个步骤的复杂过程&#xff0c;且需要考虑到天猫的反爬虫策略。以下是一个简化的步骤指南&#xff1a; 步骤一&#xff1a;准备工作 环境准备&#xff1a;确保你的Python环境已经…

002-基于Sklearn的机器学习入门:基本概念

本节将继续介绍与机器学习有关的一些基本概念&#xff0c;包括机器学习的分类&#xff0c;性能指标等。同样&#xff0c;如果你对本节内容很熟悉&#xff0c;可直接跳过。 2.1 常见的监督学习方法

docker部署wg-easy和firefly

Background WireGuard是一种新型的VPN协议,它通过在内核层运行,提供高效、安全、简单和现代的VPN解决方案。wg-easy是一个专为简化 WireGuard VPN配置和管理而设计的工具&#xff0c;提供了界面化的管理&#xff0c;进一步降低WireGuard 的使用门槛&#xff0c;让用户无需深入了…