扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C++实现LeetCode(93.复原IP地址)
  • 286

0
分享到

C++实现LeetCode(93.复原IP地址)

2024-04-02 19:04:59 286人浏览 薄情痞子
摘要

[LeetCode] 93.Restore IP Addresses 复原IP地址 Given a string containing only digits, restore it

[LeetCode] 93.Restore IP Addresses 复原IP地址

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

这道题要求是复原IP地址，IP地址对我们并不陌生，就算我们不是学CS的，只要我们是广大网友之一，就应该对其并不陌生。IP地址由32位二进制数组成，为便于使用，常以XXX.XXX.XXX.XXX形式表现，每组XXX代表小于或等于255的10进制数。所以说IP地址总共有四段，每一段可能有一位，两位或者三位，范围是[0, 255]，题目明确指出输入字符串只含有数字，所以当某段是三位时，我们要判断其是否越界（>255)，还有一点很重要的是，当只有一位时，0可以成某一段，如果有两位或三位时，像 00， 01， 001， 011， 000等都是不合法的，所以我们还是需要有一个判定函数来判断某个字符串是否合法。这道题其实也可以看做是字符串的分段问题，在输入字符串中加入三个点，将字符串分为四段，每一段必须合法，求所有可能的情况。根据目前刷了这么多题，得出了两个经验，一是只要遇到字符串的子序列或配准问题首先考虑动态规划DP，二是只要遇到需要求出所有可能情况首先考虑用递归。这道题并非是求字符串的子序列或配准问题，更符合第二种情况，所以我们要用递归来解。我们用k来表示当前还需要分的段数，如果k = 0，则表示三个点已经加入完成，四段已经形成，若这时字符串刚好为空，则将当前分好的结果保存。若k != 0, 则对于每一段，我们分别用一位，两位，三位来尝试，分别判断其合不合法，如果合法，则调用递归继续分剩下的字符串，最终和求出所有合法组合，代码如下：

c++ 解法一：


class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        restore(s, 4, "", res);
        return res;
    }
    void restore(string s, int k, string out, vector<string> &res) {
        if (k == 0) {
            if (s.empty()) res.push_back(out);
        }
        else {
            for (int i = 1; i <= 3; ++i) {
                if (s.size() >= i && isValid(s.substr(0, i))) {
                    if (k == 1) restore(s.substr(i), k - 1, out + s.substr(0, i), res);
                    else restore(s.substr(i), k - 1, out + s.substr(0, i) + ".", res);
                }
            }
        }
    }
    bool isValid(string s) {
        if (s.empty() || s.size() > 3 || (s.size() > 1 && s[0] == '0')) return false;
        int res = atoi(s.c_str());
        return res <= 255 && res >= 0;
    }
};

我们也可以省掉isValid函数，直接在调用递归之前用if语句来滤掉不符合题意的情况，这里面用了k != std::to_string(val).size()，其实并不难理解，比如当k=3时，说明应该是个三位数，但如果字符是"010"，那么转为整型val=10，再转回字符串就是"10"，此时的长度和k值不同了，这样就可以找出不合要求的情况了，参见代码如下；

C++ 解法二：


class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        helper(s, 0, "", res);
        return res;
    }
    void helper(string s, int n, string out, vector<string>& res) {
        if (n == 4) {
            if (s.empty()) res.push_back(out);
        } else {
            for (int k = 1; k < 4; ++k) {
                if (s.size() < k) break;
                int val = atoi(s.substr(0, k).c_str());
                if (val > 255 || k != std::to_string(val).size()) continue;
                helper(s.substr(k), n + 1, out + s.substr(0, k) + (n == 3 ? "" : "."), res);
            }
        }
    }
};

Java 解法二：


public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<String>();
        helper(s, 0, "", res);
        return res;
    }
    public void helper(String s, int n, String out, List<String> res) {
        if (n == 4) {
            if (s.isEmpty()) res.add(out);
            return;
        }
        for (int k = 1; k < 4; ++k) {
            if (s.length() < k) break;
            int val = Integer.parseInt(s.substring(0, k));
            if (val > 255 || k != String.valueOf(val).length()) continue;
            helper(s.substring(k), n + 1, out + s.substring(0, k) + (n == 3 ? "" : "."), res);
        }
    }
}

由于每段数字最多只能有三位，而且只能分为四段，所以情况并不是很多，我们可以使用暴力搜索的方法，每一段都循环1到3，然后当4段位数之和等于原字符串长度时，我们进一步判断每段数字是否不大于255，然后滤去不合要求的数字，加入结果中即可，参见代码如下；

C++ 解法三：


class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        for (int a = 1; a < 4; ++a) 
        for (int b = 1; b < 4; ++b) 
        for (int c = 1; c < 4; ++c) 
        for (int d = 1; d < 4; ++d) 
            if (a + b + c + d == s.size()) {
                int A = stoi(s.substr(0, a));
                int B = stoi(s.substr(a, b));
                int C = stoi(s.substr(a + b, c));
                int D = stoi(s.substr(a + b + c, d));
                if (A <= 255 && B <= 255 && C <= 255 && D <= 255) {
                    string t = to_string(A) + "." + to_string(B) + "." + to_string(C) + "." + to_string(D);
                    if (t.size() == s.size() + 3) res.push_back(t);
                }
            }
        return res;
    }
};

Java 解法三：


public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<String>();
        for (int a = 1; a < 4; ++a) 
        for (int b = 1; b < 4; ++b) 
        for (int c = 1; c < 4; ++c)
        for (int d = 1; d < 4; ++d) 
            if (a + b + c + d == s.length()) {
                int A = Integer.parseInt(s.substring(0, a));
                int B = Integer.parseInt(s.substring(a, a + b));
                int C = Integer.parseInt(s.substring(a + b, a + b + c));
                int D = Integer.parseInt(s.substring(a + b + c));
                if (A <= 255 && B <= 255 && C <= 255 && D <= 255) {
                    String t = String.valueOf(A) + "." + String.valueOf(B) + "." + String.valueOf(C) + "." + String.valueOf(D);
                    if (t.length() == s.length() + 3) res.add(t);
                }
            }
        return res;
    }
}

到此这篇关于C++实现LeetCode(93.复原IP地址)的文章就介绍到这了,更多相关C++实现复原IP地址内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

--结束END--

本文标题: C++实现LeetCode(93.复原IP地址)

本文链接: https://lsjlt.com/news/130760.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • C++实现LeetCode(93.复原IP地址)
    [LeetCode] 93.Restore IP Addresses 复原IP地址 Given a string containing only digits, restore it...
    99+
    2024-04-02
  • C++怎么复原IP地址
    这篇文章主要介绍“C++怎么复原IP地址”，在日常操作中，相信很多人在C++怎么复原IP地址问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++怎么复原IP地址”的疑惑有所帮助！接下来，请跟着小编一起来学习吧...
    99+
    2023-06-20
  • java实现IP地址转换
    一个IP地址是用四个字节（每个字节8位）的二进制码组成。请将32位二进制码表示的IP地址转换为十进制格式表示的IP地址输出。 输入数据要求： 必须为二进制数，即只能输入0或者1 长...
    99+
    2024-04-02
  • C++实现LeetCode(99.复原二叉搜索树)
    [LeetCode] 99. Recover Binary Search Tree 复原二叉搜索树 Two elements of a binary search tree (BST...
    99+
    2024-04-02
  • Centos7.5配置IP地址的实现
    1.配置ip地址前首先ifconfig查看网卡信息并获取到网卡的名称 2.进入到网卡配置目录 cd /etc/sysconfig/network-scripts/，找到配置文件为ifcfg-em2 3.修改i...
    99+
    2022-06-04
    Centos7.5配置IP地址 Centos配置IP
  • ThinkPHP中实现IP地址定位
    在网站开发中，我们经常需要获取用户的地理位置信息以提供个性化的服务。一种常见的方法是通过IP地址定位。在本文中，我们将介绍如何在ThinkPHP框架中实现IP地址定位。 一、IP地址定位的基本原理 IP地址是Internet上的设备在网络中...
    99+
    2023-09-12
    tcp/ip php 数据库 ThinkPHP
  • java实现通过IP地址获取mac（物理地址）
    java实现通过IP地址获取mac（物理地址），只能获取到局域网的mac地址，具体代码如下: package com.qcmsa.util;import org.apache.commons.log...
    99+
    2023-09-01
    java tcp/ip macos
  • C++实现LeetCode(174.地牢游戏)
    [LeetCode] 174. Dungeon Game 地牢游戏 The demons had captured the princess (P) and imprisoned h...
    99+
    2024-04-02
  • Redis IP地址的绑定的实现
    很多时候我们的redis的IP地址一般都是默认的127.0.0.1代表只能接受本机的访问，因此我们其他机器上想要访问这个redis的时候，就需要去修改ip地址的访问。 第一步：进入到...
    99+
    2024-04-02
  • python如何实现ip地址伪装
    这篇文章主要介绍python如何实现ip地址伪装，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！ip地址伪装对于网络中的反爬虫策略来说，大多数都是根据单个IP的行为来判断是不是网络爬虫...
    99+
    2024-04-02
  • C++如何实现LeetCode之复原二叉搜索树
    这篇文章给大家分享的是有关C++如何实现LeetCode之复原二叉搜索树的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。[LeetCode] 99. Recover Binary Search Tree 复原二叉搜...
    99+
    2023-06-20
  • Android 获取IP地址的实现方法
    Android 获取IP地址 最近做项目，有一个需求是Android设备获取当前IP的功能，经过一番查询资料解决了，记录下实现方法。 1.使用WIFI 首先设置用户权限 &l...
    99+
    2022-06-06
    获取ip地址 ip 方法 Android
  • Java实现局域网IP地址扫描
    Java扫描局域网地址主要通过CMD命令，主要通过Runtime和Process类，由于同一局域网下的IP地址比较多需要通过Java的多线程来扫描端口。 import java.io...
    99+
    2024-04-02
  • 怎么用PHP实现IP地址跳转
    在网络开发过程中，经常需要根据用户的IP地址来实现目标地址的跳转，这种跳转方式可以用于访客的地理位置选择、网站语言转换、广告投放等方面。本文将介绍如何使用PHP实现IP地址跳转。第一步：获取访客的IP地址使用PHP处理IP地址，需要首先获取...
    99+
    2023-05-14
    php
  • python实现获取服务器IP地址
    第一种：#!/usr/bin/env pythonimport  osip=os.popen("ifconfig eth0 | awk -F [:' ']+ 'NR==2{print $4}'")print ip.readline()第二种...
    99+
    2023-01-31
    地址 服务器 python
  • python实现局域网ip地址扫描
    python 遍历局域网ip 从知道python开始，我的视线里就没缺少过他。尤其是现如今开发语言大有傻瓜化的趋势。而作为这一趋势的领导，脚本语言就显得格外亮眼。不管是python还是ruby，perl，都火的不得了。就连java都出了个...
    99+
    2023-01-31
    局域网 地址 python
  • 如何用PHP实现IP地址跳转
    这篇文章主要介绍了如何用PHP实现IP地址跳转的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇如何用PHP实现IP地址跳转文章都会有所收获，下面我们一起来看看吧。第一步：获取访客的IP地址使用PHP处理IP地址，...
    99+
    2023-07-05
  • Shell脚本实现自动修改IP地址
    作为一名Linux SA，日常运维中很多地方都会用到脚本，而服务器的ip一般采用静态ip或者MAC绑定，当然后者比较操作起来相对繁琐，而前者我们可以设置主机名、ip信息、网关等配置。修改成特定的主机名在维护...
    99+
    2022-06-04
    脚本 地址 Shell
  • BAT脚本实现自动IP地址切换
    BAT自动IP地址切换脚本如下： @echo off color 3f mode con cols=80 lines=30 title 自动IP地址切换脚本 By 小强 if "%1...
    99+
    2024-04-02
  • Python如何实现获取内网IP地址
    本文小编为大家详细介绍“Python如何实现获取内网IP地址”，内容详细，步骤清晰，细节处理妥当，希望这篇“Python如何实现获取内网IP地址”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。方法一import&n...
    99+
    2023-07-05
软考高级职称资格查询
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作