2696. 删除子串后的字符串最小长度

image-20230521164525293

解题思路

使用栈，遍历字符串，字母直接入栈，碰到CorD判断栈顶为A或者B则出栈，最后返回栈的长度即可

示例代码

1
2
3
4
5
6
7
8
9
10
11
func minLength(s string) int {
    stack := make([]rune, 0)
    for _, char := range s {
        if len(stack) > 0 && ((stack[len(stack)-1] == 'A' && char == 'B') || (stack[len(stack)-1] == 'C' && char == 'D')) {
            stack = stack[:len(stack)-1] // 出栈
        } else {
            stack = append(stack, char) // 入栈
        }
    }
    return len(stack)
}

2697. 字典序最小回文串

image-20230521164940441

解题思路

双指针从两侧像中间匹配，遇到不同的字段时，替换较大那个字母，保证题目要求的只需选取 **字典序最小** 的方案

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func makeSmallestPalindrome(s string) string {
    i, j := 0, len(s)-1
    str := []byte(s)
    for i < j {
        if str[i] != str[j] {
            if str[i] < str[j] {
                str[j] = str[i]
            } else {
                str[i] = str[j]
            }
        }
        i++
        j--
    }
    return string(str)
}

2698. 求一个整数的惩罚数

image-20230521173706766

解题思路

通过回溯去分割子串，判断是否是惩罚数。回溯时需要分割条件为切割的字符串个数。

回溯时先每个字符串切割第一位，不满足条件时再加一位进行切割，直到字符串使用完毕，判断是否满足答案。

示例代码

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
func punishmentNumber(n int) int {
    var sum int

    for i := 1; i <= n; i++ {
        s := strconv.Itoa(i * i)
        n := len(s)
        var dfs func(int, int) bool
        dfs = func(p int, sum int) bool {
            if p == n { // 切割到最后一位,判断是否符合要求
                return sum == i
            }
            x := 0
            for j := p; j < n; j++ {
                x = x*10 + int(s[j]-'0')
                if dfs(j+1, sum+x) {
                    return true
                }
            }
            return false
        }
        if dfs(0, 0) {
            sum += i * i
        }
    }
    return sum
}

2699. 修改图中的边权

image-20230521191131169

image-20230521191149635

解题思路

见详细分析两次 Dijkstra（稠密图下是线性做法)

示例代码：

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

func modifiedGraphEdges(n int, edges [][]int, source int, destination int, target int) [][]int {
    type edge struct {
        to, eid int // eid方便后续修改edges
    }
    graph := make([][]edge, n)
    for i, e := range edges {
        form, to := e[0], e[1]
        graph[form] = append(graph[form], edge{to, i})
        graph[to] = append(graph[to], edge{form, i})
    }

    var delta int
    dis := make([][2]int, n)
    for i := range dis {
        dis[i] = [2]int{math.MaxInt, math.MaxInt}
    }
    dis[source] = [2]int{}
    dijkstra := func(k int) {
        vis := make([]bool, n)
        for {
            // 找到最短路,并且没有vis的点,(第一轮循环找的是起点 source)
            x := -1
            for y, b := range vis {
                if !b && (x < 0 || dis[y][k] < dis[x][k]) {
                    x = y
                }
            }

            if x == destination { // 起点source到终点 destination的最短距离已确认
                return
            }
            vis[x] = true
            for _, e := range graph[x] {
                y, wt := e.to, edges[e.eid][2]
                if wt == -1 {
                    wt = 1 // -1改为1
                }
                if k == 1 && edges[e.eid][2] == -1 { // 第二次 Dijkstra，改成 w
                    w := delta + dis[y][0] - dis[x][1]
                    if w > wt {
                        wt = w
                        edges[e.eid][2] = w
                    }
                }
                // 更新最短路
                dis[y][k] = min(dis[y][k], dis[x][k]+wt)
            }
        }
    }

    // 第一次dijkstra
    dijkstra(0)
    delta = target - dis[destination][0]
    if delta < 0 { // 起点到终点长度好过target,无解,  -1 全改为 1 时，最短路比 target 还大
        return nil
    }

    // 第二次dijkstra
    dijkstra(1)
    if dis[destination][1] < target { // 如果第二次dijkstra,最短路无法再变大，无法达到 target
        return nil
    }

    for _, e := range edges {
        if e[2] == -1 { // 剩余没修改的边全部改成 1
            e[2] = 1
        }
    }
    return edges
}