文档章节

leetcode Restore IP Addresses

Lennie002
 Lennie002
发布于 2015/09/09 10:33
字数 321
阅读 39
收藏 0

将一个数字串转化成合法IP,  DFS,注意一些细节

class Solution {
public:

    vector<string> restoreIpAddresses(string s) {
    	vector<string> ans;
        dfs(ans, s, "", 0, 0);
        return ans;
    }
    void dfs(vector<string> &ans, string s, string str, int pos, int dep) {
        if (dep >= 4) {
            if (dep == 4 && pos == s.length()) ans.push_back(str);
        } else {
            for (int i = pos; i < s.length(); i++) {
                string sub = s.substr(pos, i-pos+1);
                if (sub.length() <= 3 && stoi(sub) >= 0 && stoi(sub) <= 255 &&
                    to_string(stoi(sub)) == sub) {
                    string common = (dep == 3 ? "": ".");
                    dfs(ans, s, str+sub+common, i+1, dep+1);
                }
            }
        }
    }
    
    /**
     * vector<string> ans; //return all ips
     * string s;    // input string
     * string ip;   // 暂时存储
     * string pos;  // 但前起始坐标
     * string step; // ip地址中第几位数(4部分)
     * 在一段 字符串 或 数组 上分段提取,使用 dfs, dfs 可以加入 剪枝
     * 在这段数据上 搜索最小值,可以改成bfs
     */
    void dfs2(vector<string> &ans, string s, string ip, int pos, int step)
    {
    	if(pos == s.length() && step == 4){
    		//删除最后的点
    		ans.push_back(ip.substr(0,ip.size()-1));
    		return;
    	}
    	if(step > 4) return; //剪枝
    	//  if(s.szie() - i > (4-step) * 3) return; //更快
    	
    	for(int i=pos+1; i<=s.size(); i++)
    	{
    		string tmp = s.substr(pos, i-pos);
    		int val = stoi(tmp);
    		//ip地址0-255之间, 并且 前面不能出现0(022);
    		// stoi(string) , to_string(int), char* = c_str(string) 
    		if(tmp.length() <=3 && val >=0 && val <= 255 && to_string(val) == tmp){
    			dfs2(ans, s, ip+tmp+".",i,step+1);
    		}
    	}
    }
};

© 著作权归作者所有

Lennie002
粉丝 8
博文 120
码字总数 64058
作品 0
大连
私信 提问
LeetCode 93 Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example: Given , return . (Order does not matter) 给一个字符串,转......

努力的C
2017/10/11
0
0
CRIU 2.0 发布 功能得以完善

CRIU 2.0发布,我们重组了criu-2的所有代码,新功能得以完善,漏洞得到修复。 更新日志: New code layout for sub-projects (e.g. Compel) Unprivileged dump Dump/check cpuinfo support ...

oschina
2016/03/10
1K
1
LeetCode 分类刷题—— Backtracking

Backtracking 的 Tips: 排列问题 Permutations。第 46 题,第 47 题。第 60 题,第 526 题,第 996 题。 组合问题 Combination。第 39 题,第 40 题,第 77 题,第 216 题。 排列和组合杂交问...

一缕殇流化隐半边冰霜
07/06
0
0
Leetcode日记8

(2015/2/3) LeetCode 4 Median of Two Sorted Arrays 题目大意:找到两个已排序数组的median。 median:中间位置的值。 算法: 参考:https://leetcode.com/discuss/15790/share-my-o-log...

fxdhdu
2016/02/18
111
0
分布式搜索引擎 ElasticSearch 6.1.2 和 5.6.6 发布

ElasticSearch 6.1.2 和 5.6.6 已发布,和平时一样,更新内容主要是功能增强、Bug 修复以及一些升级,具体如下: 6.1.2 更新内容 增强 Internal Make AbstractQueryBuilder.declareStandard...

淡漠悠然
2018/01/17
2.1K
5

没有更多内容

加载失败,请刷新页面

加载更多

手持式人证核验设备助力国家安全系统

手持式人证核验设备,是针对公共安全领域的移动化身份核验、追逃等需求推出的手持式一体化设备。其特点是具备人员信息采集、存储和比对功能,将采集到的人脸信息与居民身份证芯片中的人脸信息...

非思丸智能FaceTo
11分钟前
2
0
好程序员web前端教程分享JavaScript简写方法

今天好程序员web前端教程为大家分享JavaScript简写方法,小伙伴们快来看一看吧。 1.三元操作符 当想写if...else语句时,使用三元操作符来代替。 constx =20; let answer; if(x >10) { answer...

好程序员官网
15分钟前
3
0
PHP面试题2019年小米工程师面试题和答案解析

一、单选题(共29题,每题5分) 1.PHP面向对象方法重写描述错误的是? A、子类必须继承父类 B、子类可以重写父类已有方法 C、重写之后子类会调用父类方法 D、子类也可以具有与父类同名的属性...

一个PHP程序媛
18分钟前
2
0
K8s 从懵圈到熟练 – 镜像拉取这件小事

导读:相比 K8s 集群的其他功能,私有镜像的自动拉取,看起来可能是比较简单的。而镜像拉取失败,大多数情况下都和权限有关。所以,在处理相关问题的时候,我们往往会轻松的说:这问题很简单...

Mr_zebra
18分钟前
3
0
分布式锁简单入门以及实现方法

学过Java多线程的应该都知道什么是锁,没学过的也不用担心,Java中的锁可以简单的理解为多线程情况下访问临界资源的一种线程同步机制。 在学习或者使用Java的过程中进程会遇到各种各样的锁的...

yanlijun_java
21分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部