代码随想录算法训练营第二十四天 | 93、78、90

算法
, , ,

93. 复原 IP 地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package main

import (
    "strconv"
    "strings"
)

func restoreIpAddresses(s string) []string {
    var result []string
    n := len(s)
    if n < 4 || n > 12 {
        return result
    }

    var backtrack func(int, []string)
    backtrack = func(start int, path []string) {
        if len(path) == 4 {
            if start == n {
                result = append(result, strings.Join(path, "."))
            }
            return
        }

        for i := 1; i <= 3; i++ {
            end := start + i
            if end > n {
                break
            }
            segment := s[start:end]
            if isValid(segment) {
                backtrack(end, append(path, segment))
            }
        }
    }

    backtrack(0, []string{})
    return result
}

func isValid(segment string) bool {
    if len(segment) > 1 && segment[0] == '0' {
        return false
    }
    num, err := strconv.Atoi(segment)
    if err != nil {
        return false
    }
    return num <= 255
}

78. 子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package main

func subsets(nums []int) [][]int {
    var result [][]int
    var backtrack func(int, []int)

    backtrack = func(start int, path []int) {
        // 将当前路径的副本添加到结果集
        temp := make([]int, len(path))
        copy(temp, path)
        result = append(result, temp)

        // 遍历所有可能的起始位置
        for i := start; i < len(nums); i++ {
            // 将当前元素加入路径
            path = append(path, nums[i])
            // 递归处理后续元素
            backtrack(i+1, path)
            // 回溯，移除最后添加的元素
            path = path[:len(path)-1]
        }
    }

    backtrack(0, []int{})
    return result
}

90. 子集 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package main

import "sort"

func subsetsWithDup(nums []int) [][]int {
    sort.Ints(nums) // 排序以方便处理重复元素
    var result [][]int
    var backtrack func(int, []int)

    backtrack = func(start int, path []int) {
        // 添加当前路径的副本到结果集
        tmp := make([]int, len(path))
        copy(tmp, path)
        result = append(result, tmp)

        for i := start; i < len(nums); i++ {
            // 跳过同一层中重复使用的相同元素
            if i > start && nums[i] == nums[i-1] {
                continue
            }
            path = append(path, nums[i]) // 选择当前元素
            backtrack(i+1, path)         // 递归处理后续元素
            path = path[:len(path)-1]    // 回溯，撤销选择
        }
    }

    backtrack(0, []int{}) // 从空路径开始生成所有子集
    return result
}