IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> leetcode 93. 复原 IP 地址 刷了一天,小白忘了整理回溯法了 -> 正文阅读

[数据结构与算法]leetcode 93. 复原 IP 地址 刷了一天,小白忘了整理回溯法了

强烈安利一名大佬:代码随想录链接如下

代码随想录

给定一个只包含数字的字符串,用以表示一个 IP 地址,返回所有可能从 s 获得的 有效 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 地址。


```cpp
class Solution {
public:
    vector<string> result;
    vector<string> restoreIpAddresses(string s) {
        backstracking(s, 0, 0);
        return result;
    }
    void backstracking(string s, int index, int pointNum) {  //index代表切割的位置,pointNum代表已经使用的 . 的个数
        if(pointNum == 3) {
            if (isTrue(s, index, s.size() - 1)) {
                result.push_back(s);
            }
            return ;
        }
        for(int i = index; i < s.size(); i++) {
            if (!isTrue(s, index, i)) { 
                break;  //break用于完全结束一个循环这一块都不行,更别说别的了
            }
            //string str = s.substr(index, i);
            s.insert(s.begin() + i + 1, '.');   // 插入begin() + i + 1的点.
            pointNum++;                     
            backstracking(s, i + 2, pointNum); //由于已经插入 . ,所以下次循环在 i + 2 处开始了
            pointNum--;
            s.erase(s.begin() + i + 1);  //回溯法,删除begin() + i + 1的点

        }

    }
    bool isTrue(string s, int left, int right) {  // 判断截取的ip这一段是否有效
        if (left > right || ((right - left) > 2) ) {
            return false;
        }
        if (s[left] == '0' && left != right) {
            return false;
        }
        int sum = 0;
        for (int i = left; i <= right; i++) {
            if (s[i] > '9' || s[i] < '0') {
                return false;
            }
            int temp = s[i] - '0';
            sum = 10 * sum + temp;   //累加法
            if (sum > 255) {
                return false;
            }
        }
        return true;
    }
};

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-08-16 11:59:24  更:2021-08-16 12:01:30 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 21:38:30-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码