2716.最小化字符串长度

image-20230626074806661

解题思路

这道题就是一个求不同的字符串，选中一个字符，然后看左侧或者右侧有误相同的的字符，有就移除，换言之就是统计出现过的字符串个数

示例代码

1
2
3
4
5
6
7
func minimizedStringLength(s string) int {
    m := map[int32]struct{}{}
    for _, i := range s {
        m[i] = struct{}{}
    }
    return len(m)
}

2717.半有序排序

image-20230604150447846

解题思路

l表示1的位置，r表示n的位置

  • 如果l < r，那么各自移动即可，结果为1+n-r-1
  • 如果l > r，在l移动的过程中，就帮r移动一次，此时次数会再减少一次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func semiOrderedPermutation(nums []int) int {
    n := len(nums)
    l, r := 0, 0
    for i := 0; i < n; i++ {
        if nums[i] == 1 {
            l = i
        }
        if nums[i] == n {
            r = i
        }
    }
    if r > l {
        return l + n - r - 1
    }
    return l + n - r - 1 - 1
}

2718. 查询后矩阵的和

image-20230604150911684

image-20230604150926143

解题思路

因为是最后计算，所以最后填入的数字才是有效数字，这里倒序倒序填入

如果当前行/列没有被填入(表示queries中最后一次填入)，则进行操作，此时我们需要填入的值为当前行/列，将去已经被列/行填入的空位置。用哈希表记录该行或者列是否填入过。

以第i行为例，如果当前行未填入，则进行操作，此前一共操作了m列，此时我们只需要填入n-m个格子即可，答案增加(n-m)*val即可，列同理

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func matrixSumQueries(n int, queries [][]int) int64 {
    vis := [2]map[int]bool{{}, {}} // 0: 行, 1: 列
    var ans int64
    for i := len(queries) - 1; i >= 0; i-- {
        t, index, val := queries[i][0], queries[i][1], queries[i][2]
        if !vis[t][index] { // 没有被赋值过
            var remain int
            if t == 0 {
                remain = n - len(vis[1])
            } else {
                remain = n - len(vis[0])
            }
            // 这一行/列还剩下 remain 个可以填入的格子
            ans += int64(remain * val)
            vis[t][index] = true
        }
    }
    return ans
}

2719. 统计整数数目

image-20230604163653379

解题思路

根据灵神的数位 DP 通用模板，我们不需要判断是否填了数字，可以省略最后一个参数，本题详见数位 DP 通用模板

示例代码

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
func count(num1 string, num2 string, minSum int, maxSum int) int {
    const mod int = 1e9 + 7
    f := func(s string) int {
        // 剪枝
        memo := make([][]int, len(s))
        for i := range memo {
            memo[i] = make([]int, min(9*len(s), maxSum)+1)
            for j := range memo[i] {
                memo[i][j] = -1
            }
        }

        var dfs func(i int, sum int, limitUp bool) int
        dfs = func(i int, sum int, limitUp bool) int {
            if sum > maxSum {
                return 0
            }
            if i == len(s) {
                if sum >= minSum {
                    return 1
                }
                return 0
            }
            var res int
            if !limitUp && memo[i][sum] != -1 {
                return memo[i][sum]
            }

            up := 9
            if limitUp {
                up = int(s[i] - '0')
            }
            for d := 0; d <= up; d++ {
                res = (res + dfs(i+1, sum+d, limitUp && d == up)) % mod
            }
            if !limitUp {
                memo[i][sum] = res
            }
            return res
        }
        return dfs(0, 0, true)
    }
    ans := f(num2) - f(num1) + mod // 避免负数
    sum := 0
    for _, c := range num1 {
        sum += int(c - '0')
    }
    if minSum <= sum && sum <= maxSum { // x=num1 是合法的，补回来
        ans++
    }
    return ans % mod
}