题目

leetcode:93

代码与解析

这道题和 二叉树所有路径以及https://blog.devilwst.top/2021/12/30/很像。
差不多是https://blog.devilwst.top/2021/12/30/这道题的兄弟。

大致核心是收集所有路径,把符合条件的节点添加到path.和分割回文串一样,这个也是分割问题!!!!

回溯三部曲:

  • 确定递归参数及返回值
    只需要传入start用于记录索引。

  • 确定终止条件
    这个终止条件和https://blog.devilwst.top/2021/12/30/这个不一样,
    很容易忽略start的位置。start==len(s)这个容易忽略
    len(path)==4&&start==len(s)

if len(path)==4&&start==len(s){
    temp := strings.Join(path, ".")
    res = append(res, temp)
    return
}
  • 确定单层逻辑
    和上一道差不多。大差不差。符合条件的就添加进path
for i:=start;i<len(s);i++{
    subString := s[start: i+1]
    if isValid(subString){
        path = append(path, subString)
    }else{
        continue
    }
    backtracking(i+1)
    path = path[:len(path)-1]
}
  • IP有效验证
    我写的比较乱
    注意s[startIndex]=='0'的判断,不应该写s[startIndex]==0,因为s截取出来不是数字
func isValid(str string)bool{
    if len(str)==1{
        return true
    }
    // 到下面说明当前段 长度大于1
    start := str[0] - '0'
    // 长度大于1,第一位还等于0,false
    if start==0{
        return false
    }
    // 转换为int判断是否小于255
    s, _ := strconv.ParseInt(str, 10, 32)
    if s>255{
        return false
    }
    return true
}
---------------------下面是一位大佬的代码-------------------------
func isIp3(s string,startIndex,end int)bool{
    checkInt,_:=strconv.Atoi(s[startIndex:end+1])
    if end-startIndex+1>1&&s[startIndex]=='0'{//对于前导 0的IP(特别注意s[startIndex]=='0'的判断,不应该写成s[startIndex]==0,因为s截取出来不是数字)
        return false
    }
    if checkInt>255{
        return false
    }
    return true
}
————选自carl大佬博客https://programmercarl.com/0093.复原IP地址.html#go  片段

整体代码:

func restoreIpAddresses(s string) []string {
    res := []string{}
    path := []string{}
    var backtracking func(start int)
    backtracking = func(start int){
        if len(path)==4&&start==len(s){
            // temp := strings.Join(path, ".")
            temp:=""
            for i:=0;i<=2;i++{
                temp = temp + path[i] + "."
            }
            temp +=  path[3]
            res = append(res, temp)
            return
        }
        for i:=start;i<len(s);i++{
            subString := s[start: i+1]
            if isValid(subString){
                path = append(path, subString)
            }else{
                continue
            }
            backtracking(i+1)
            path = path[:len(path)-1]
        }
    }
    backtracking(0)
    return res
}
func isValid(str string)bool{
    if len(str)==1{
        return true
    }
    // 到下面说明当前段 长度大于1
    start := str[0] - '0'
    // 长度大于1,第一位还等于0,false
    if start==0{
        return false
    }
    // 转换为int判断是否小于255
    s, _ := strconv.ParseInt(str, 10, 32)
    if s>255{
        return false
    }
    return true
}

站点统计

  • 文章总数:309 篇
  • 分类总数:19 个
  • 标签总数:191 个
  • 运行天数:1006 天
  • 访问总数:124252 人次

浙公网安备33011302000604

辽ICP备20003309号