力扣 93. 复原 IP 地址

这篇具有很好参考价值的文章主要介绍了力扣 93. 复原 IP 地址。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目来源:https://leetcode.cn/problems/restore-ip-addresses/description/

力扣 93. 复原 IP 地址,开始C++吧,leetcode,算法,c++,回溯算法

C++题解:递归回溯法。

  • 递归参数:因为不能重复分割,需要ind记录下一层递归分割的起始位置;还需要一个变量num,记录ip段的数量。
  • 递归终止条件:ip段的数量达到4 且 ind等于s的长度,可进行有效ip地址保存;当s剩余字符较长时,可进行提前截断。
  • 单层递归逻辑:截断的长度为1-3个字符,判断截出的字符串有效性,无效则停止回溯,有效则继续下一步的回溯,同时记得ip的回溯。
class Solution {
public:
    vector<string> res;
    string ip = "";
    bool isval(string ipseg) {  // 判断字符串有效性
        int lenipseg = ipseg.size();
        if(lenipseg == 1) return true;
        else if(lenipseg == 2){
            if(ipseg[0] == '0') return false;
            return true;
        }
        else if(lenipseg == 3){
            if(ipseg[0] == '0') return false;
            int ipsegint = (ipseg[0] - '0')*100 + (ipseg[1] - '0')*10 + ipseg[2] - '0';
            if(ipsegint <= 255) return true;
            else return false;
        }
        return false;
    }
    void backtracking(string s, int ind, int num) {
        if(ind == s.size() && num == 4) {
            res.push_back(ip);
            return;
        }
        if(num == 0 && s.size() - ind > 12) return;
        else if(num == 1 && s.size() - ind > 9) return;
        else if(num == 2 && s.size() - ind > 6) return;
        else if(num == 3 && s.size() - ind > 3) return;
        else if(num == 4 && s.size() - ind > 0) return; 
        else if(ind >= s.size() || num > 4) return;

        for(int i = ind, j = 1; j <= 3; j++){
            string ipseg = s.substr(i, j);            
            if(isval(ipseg)) {
                int lenip = ip.size(); //记录ip长度,方便回溯
                ip = ip + ipseg;
                num++;
                if(num < 4) ip = ip + ".";
                backtracking(s, i + j, num);
                ip = ip.substr(0, lenip);
                num--;
            }
            else return;
        }
        return;
    }
    vector<string> restoreIpAddresses(string s) {
        int len = s.size();
        if(len > 12) return res;
        backtracking(s, 0, 0);
        return res;
    }
};

 C++题解:思路同上,来源代码随想录

 文章来源地址https://www.toymoban.com/news/detail-526962.html

class Solution {
private:
    vector<string> result;// 记录结果
    // startIndex: 搜索的起始位置,pointNum:添加逗点的数量
    void backtracking(string& s, int startIndex, int pointNum) {
        if (pointNum == 3) { // 逗点数量为3时,分隔结束
            // 判断第四段子字符串是否合法,如果合法就放进result中
            if (isValid(s, startIndex, s.size() - 1)) {
                result.push_back(s);
            }
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
                s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一个逗点
                pointNum++;
                backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2
                pointNum--;                         // 回溯
                s.erase(s.begin() + i + 1);         // 回溯删掉逗点
            } else break; // 不合法,直接结束本层循环
        }
    }
    // 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
    bool isValid(const string& s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s[start] == '0' && start != end) { // 0开头的数字不合法
                return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
                return false;
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255) { // 如果大于255了不合法
                return false;
            }
        }
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了
        backtracking(s, 0, 0);
        return result;
    }
};

到了这里,关于力扣 93. 复原 IP 地址的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣每日一题93:复原IP地址

    有效 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 地址。 给定一个只包含数字的字

    2024年02月06日
    浏览(35)
  • leetcode做题笔记93. 复原 IP 地址

    有效 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 地址。 给定一个只包含数字的字

    2024年02月12日
    浏览(41)
  • 代码随想录23| 93.复原IP地址, 78.子集, 90.子集II

    题目链接/文章讲解:链接地址 视频讲解:链接地址 题目链接/文章讲解:链接地址 视频讲解:链接地址 题目链接/文章讲解:链接地址 视频讲解:链接地址

    2024年02月11日
    浏览(87)
  • 代码随想录刷题笔记 DAY 28 | 复原 IP 地址 No.93 | 子集 No.78 | 子集 II No.90

    01. 复原 IP 地址(No. 93) 题目链接 代码随想录题解 1.1 题目 有效 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\\\" 是 无效 I

    2024年02月22日
    浏览(46)
  • 算法学习——LeetCode力扣回溯篇2

    40. 组合总和 II - 力扣(LeetCode) 描述 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意:解集不能包含重复的组合。 示例 示例 1: 输入: candidates = [10,1,2,7

    2024年02月20日
    浏览(35)
  • 算法刷题Day 28 复原IP地址+子集+子集II

    我的做法有点奇怪,还是参考一下代码随想录的做法吧 涉及到去重,可别忘了排序 不然去重的效果没法实现

    2024年02月16日
    浏览(41)
  • 面试热题(复原ip地址)

    有效 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 地址。 给定一个只包含数字的字

    2024年02月11日
    浏览(46)
  • Rust每日一练(Leetday0031) 解码方法、复原 IP 地址

    目录 91. 解码方法  Decode Ways  🌟🌟 93. 复原 IP 地址 Restore IP Addresses  🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 一条包含字母  A-Z  的消息通过以下映射进行了  编码  : 要  解码  已编码的消息,所有

    2024年02月09日
    浏览(35)
  • leetcode(力扣) 剑指 Offer 12. 矩阵中的路径(回溯 DFS)

    给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

    2024年02月14日
    浏览(46)
  • 力扣--深度优先算法/回溯算法47.全排列 Ⅱ

    思路分析: 使用DFS算法进行全排列,递归地尝试每个可能的排列方式。 使用 path 向量保存当前正在生成的排列,当其大小达到输入数组的大小时,将其加入结果集。 使用 numvisited 向量标记每个数字是否已经被访问过,以确保每个数字在一个排列中只使用一次。 在递归过程中

    2024年03月13日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包