专栏首页架构说递归回溯--复原IP地址

递归回溯--复原IP地址

一句话经验

There is no coming to consciousness without pain.

没有任何一种觉醒是不带着痛苦的

一、题目描述

93. 复原IP地址

放轻松,虽然是c++实现,拒绝奇技淫巧,通俗易懂。
class Solution {
public:
 vector<string> restoreIpAddresses(string s) {
 
 vector<string> res;//输出结果
 vector<string> path;//栈保持路径
 
 //从位置0 遍历每个字符串
      dfs(s,0,0,path,res);
 return res;
    }

 void dfs(string s,int start,int depth ,vector<string> &path, vector<string> & res)
 {   

 if (start >s.size())
         {
 return ;//字符串遍历完毕
         }

 //递归结束条件01
 //选取4组后,还有剩余元素 肯定无法组成ip。剪枝
 if ( 4 ==depth &&  start  <s.size() )
         {
 return ;
         }
 ////递归结束条件02 寻找叶子节点。
 if ( 4 ==depth &&  start  == s.size() )
         {
 //拼成ip
 string str=path[0];
 for (int i = 1;i<4;++i) {
               str = str + '.' + path[i];
           }
           res.push_back(str);//ans中保存一种可行方案
 return; 
         }
 //
 
 // 递归变化条件 {2 5 5}
 //每一个string只能存长度1~3的字符串
 for(int i=1;i<4;i++)
         {
 //获取当前组 元素 
 string str = s.substr(start,i);//切割字符串
 //约束条件:
 if (i == 3 && atoi(str.c_str()) > 255) //不能大于255
 return;

 if (i != 1 && s[start] == '0') //01,001非法
 return;
              path.push_back(str);
 
 //下一组元素
              dfs(s,start+i,depth+1,path,res);
 
 //pop当前组 元素
              path.pop_back();
         }

    }
};
  • golang
func restoreIpAddresses(s string) []string {

    res:=make([]string,0) //符合高度为4的 3叉树的路径
    if len(s) > 12 {
        return res //过 12 位的肯定不能是 ip 地址,最大就是 255.255.255.255
    }

    path :=make([]string,0) //用栈进行回溯

    dfs(s,0,0,&path,&res) //空指针修改

    return res

}

func dfs(s string, start int,depth int,path* []string, res *[]string){
    //01 越界
     if start >len(s) {
         return 
     }
    if 4 == depth {
        //02 剪枝 [2.5.5.2.551113]
        if start <len(s) {
            return 
        }
        //03 符合条件的路径 "255.255.111.35"
        if start ==len(s){
         tmp := strings.Join(*path, ".")
         *res = append(*res, tmp)
         return 
        }
    }

    //循环处理

    for i:=1;i<4;i++{
        if start+i >len(s) {
            return 
        }
        temp :=s[start:start+i] //左闭右开
         //01 001 
        if i!=1 && s[start] =='0' {
            return 
        }
        if i==3 {
          ip, _ := strconv.Atoi(temp);
          if ip >255{
              continue;
          }
        }
     //////////////////////////////////////////////////

        *path = append(*path, temp) //插入最后一个元素
    
         dfs(s, start+i, depth+1,path,res)
        
        //删除最后一个记录,回溯使用
         *path = (*path)[:len((*path))-1]
        }
    }
  • 累计耗时 25×6

二、测试用例

给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成),整数之间用 '.' 分隔。

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

思考 60秒 。。。

思考 60秒 。。

三、思路分析

最迷惑地方

  • 看到ip问题,思路模糊,感觉无从下手,虽然是不断拆分字符,但是无法用语言描述。
  • 一个字符串拆分 3个部分,感觉无数可能,无法头脑计算出来,也是无法自己看成来的
  • 如何遍历这样情况,for循环好像解决不了这个问题
  • 如何组成ip地址
  • 如何截取字符。

熟悉的子问题

  • 这是一个字符串,长度从0到n。每个n有三个选择, ---tree
  1. 选 "2" 作为第一个片段
  2. 选 "25" 作为第一个片段
  3. 选 "255" 作为第一个片段
  • ip 4个部分组成,一个tree的路径最大长度为4 --如果还剩余字符剪枝

步骤描述

  • 参考 https://leetcode-cn.com/problems/restore-ip-addresses/solution/shou-hua-tu-jie-huan-yuan-dfs-hui-su-de-xi-jie-by-/

来源:https://leetcode-cn.com/problems/restore-ip-addresses/solution/shou-hua-tu-jie-huan-yuan-dfs-hui-su-de-xi-jie-by-/

来源:https://leetcode-cn.com/problems/restore-ip-addresses/solution/shou-hua-tu-jie-huan-yuan-dfs-hui-su-de-xi-jie-by-/

四、举一反三

Permutations II

322. 零钱兑换

分享最实用的经验 , 希望每一位来访的朋友都能有所收获! 如果有疑问请联系我,一起探讨,进步。

本文分享自微信公众号 - 架构说(JiaGouS),作者:王传义

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 单例模式

    /*************************************************************************

    程序员小王
  • 每日一题2-对链表进行插入排序

    输入: 4->2->1->3 输出: 1->2->3->4 示例 2: 输入: -1->5->3->4->0 输出: -1->0->3->4->5

    程序员小王
  • 151. 翻转字符串里的单词

    程序员小王
  • spring事务源码解析

      在spring jdbcTemplate 事务,各种诡异,包你醍醐灌顶!最后遗留了一个问题:spring是怎么样保证事务一致性的? 当然,spring事务内...

  • dubbo源码学习笔记----结合Spring

    dubbo结合spring public class ServiceBean<T> extends ServiceConfig<T> implements In...

    春哥大魔王
  • 走进Java接口测试之日志框架Logback

    对于一个成熟的接口测试框架,日志管理这个是必不可少的。在开发和调试阶段,日志可以帮助我们更快的定位问题;而在测试的运维过程中,日志系统又可以帮助我们记录大部分的...

    高楼Zee
  • 用欧拉计划学Rust编程(第67题)

    如果知道一个节点的左、右节点的最大路径,可以很容易地计算出当前节点的最大路径,从底层开始,逐层计算每个节点到底部节点的最大路径上一层的最大路径,所以从每一层中最...

    申龙斌
  • 走进Java接口测试之从0到1搭建数据驱动框架(完结篇)

    在前面的几篇文章中,我们介绍了从需求到设计,再到部分功能实现,本篇作为完结篇,我们一起来完成剩下的功能实现,主要为日志管理和性能监控以及有同学提出测试用例多参数...

    高楼Zee
  • 看了让人极度舒适的Markdown文章

    毕小朋,CSDN 博客专家,百度阅读 IT 类畅销书作者,著有《精通 Android Studio》;平时喜欢写作,热爱分享,个人博客访问量迄今已超过 280 ...

    用户1682855
  • LeetCode 1318. 或运算的最小翻转次数(位运算)

    你可以对 a 和 b 的二进制表示进行位翻转操作,返回能够使按位或运算 a OR b == c 成立的最小翻转次数。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券