[代码随想录]Day24-回溯算法part04

WtcSky / 2023-08-22 / 原文

题目：93. 复原 IP 地址

思路：

函数参数：参数就一个stirng，path先收集ip地址的四个部分，最后存入res中时拼接成一个string,因此path和res都是[]string类型
终止条件：当path有了ip的四个部分就终止；当然只有完全的把字符串遍历了才会存入res
单层逻辑：先取1-3位，判断是不是0-255内的数并且没有前导0，如果是合法字段就存入path继续递归

代码：

var res []string
var path []string
func restoreIpAddresses(s string) []string {
    res, path = make([]string, 0),  make([]string, 0, 4)
    RestoreIpAddresses(s)
    return res
}
func RestoreIpAddresses(s string) {
    if len(path) == 4{ // ip分四部分
        if len(s) == 0 { // 如果是分完了的就添加进去
            res = append(res, strings.Join(path,"."))
        }
        return
    }
    for i:=1 ; i <= 3; i++ {
        if len(s) < i { // 不够遍历了直接返回
            break
        }
        tmp := s[:i] // 取1-3位
        if isIP(tmp) { // 判断是不是合法的单个ip字段
            path = append(path, tmp)
            RestoreIpAddresses(s[i:])
            path = path[:len(path)-1]
        }else {
            break // 其实这个break只能break掉 前导0
        }
    }
    return
}

func isIP(s string) bool {
    num, _ := strconv.Atoi(s)
    if s[0] == '0' && len(s) != 1 { // 不能存在前导0
        return false
    }
    if num > 255 { // 不能大于255
        return false
    }
    return true
}

参考：

代码随想录

题目：78. 子集

思路：

函数参数：不能重复所以多加一个index作为起始位置
终止条件：遍历就完了，遍历到头就结束
单层逻辑：存

代码：

var (
    res [][]int
    path []int
)
func subsets(nums []int) [][]int {
    res = make([][]int, 0)
    path = make([]int, 0, len(nums))
    Subsets(nums, 0)
    return res
}
func Subsets(nums []int, index int) {
    res = append(res, append([]int{},path...)) // 全收集
    for i := index; i < len(nums); i++ {
        path = append(path, nums[i])
        Subsets(nums, i + 1)
        path = path[:len(path)-1]
    }
    return
}

参考：

代码随想录

题目：90. 子集 II

思路：

函数参数：不能重复所以多加一个index作为起始位置
终止条件：遍历就完了，遍历到头就结束
单层逻辑：可以是相同元素同一枝但不能是同一层，因为同一层的前面已经出现过了，会出现重复

代码：

var (
    res [][]int
    path []int
    used []bool
)
func subsetsWithDup(nums []int) [][]int {
    res = make([][]int, 0)
    path = make([]int, 0, len(nums))
    used = make([]bool, len(nums))
    sort.Ints(nums) // 提前排序
    SubsetsWithDup(nums, 0)
    return res
}

func SubsetsWithDup(nums []int,index int) {
    res = append(res, append([]int{},path...)) // 全收集
    for i := index; i < len(nums); i++ {
        if i != 0 && nums[i] == nums[i-1] && used[i-1] == false { // 不是同一枝直接去掉
            continue
        }
        used[i] = true
        path = append(path, nums[i])
        SubsetsWithDup(nums, i + 1)
        path = path[:len(path)-1]
        used[i] = false
    }
}