2810. 故障键盘

image-20231128171905060

模拟

模拟键盘的输入，创建一个字符串，当遇到 ii 时就往字符串头部插入，再次遇到反转后往后插入，最后根据反转状态判断是否需要反转整个字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func finalString(s string) string {
    q := make([]rune, 0)
    tail := true
    for _, v := range s {
        if v == 'i' {
            tail = !tail
        } else if tail {
            q = append(q, v)
        } else {
            q = append([]rune{v}, q...)
        }
    }
    if !tail {
        for i, j := 0, len(q); i < j/2; i++ {
            q[i], q[j-1-i] = q[j-1-i], q[i]
        }
    }
    return string(q)
}

分别插入

每次反转就相当于是往头部插入字符串，将奇数次和偶数次反转的字符串放在一起，因为会反转多次，奇/偶里面的字符串是相连的。

因为反转是往头部插入，所以前面的部分需要反转后与另外一部分相连

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func finalString(s string) string {
    qs := [2][]rune{}
    tail := 1
    for _, v := range s {
        if v == 'i' {
            tail ^= 1
        } else {
            qs[tail] = append(qs[tail], v)
        }
    }
    q := qs[tail^1]
    for i, n := 0, len(q); i < n/2; i++ {
        q[i], q[n-1-i] = q[n-1-i], q[i]
    }
    return string(append(q, qs[tail]...))
}

2811. 判断是否能拆分数组

image-20231128181232477

解题思路：

  • 当 n≤2n \leq 2 时，这种情况下是肯定符合要求的
  • 当 n≥3n \geq 3 时，无论如何分割，最终总会在某个时刻分割出一个长度为 22 的子数组。如果 numsnums 的所有长度为 22 的子数组的和都小于 mm，那么原数组不满足要求，否则可以以这个子数组为最终答案，一个个去掉 numsnums 的首尾元素，最终得到这个子数组

最终问题变成了是否有两个相邻的数和 ≥m\geq m

1
2
3
4
5
6
7
8
9
10
11
12
13
func canSplitArray(nums []int, m int) bool {
    if len(nums) <= 2 {
        return true
    }
    
    n := len(nums)
    for i := 1; i < n; i++ {
        if nums[i-1] + nums[i] >= m {
            return true
        }
    }
    return false
}

2812. 找出最安全路径

image-20231128182626863

解题思路：

从所有的 11 出发，使用 BFS计算出每个格子(i,j)(i,j) 到最近的 11 的曼哈顿距离 dis[i][j]dis[i][j]（题目保证了至少有一个 11 ）。答案是不会超过 dis[i][j]dis[i][j] 的最大值，直接倒序枚举答案。假设答案为 dd，把所有的 dis[i][j]=ddis[i][j] = d 的格子与四周 ≥d\geq d 的格子用并集查连起来，在答案为 dd 的情况下，这些格子之间是可以互相到达的，判断 (0,0)(0,0) 和 (n−1,n−1)(n-1,n-1) 是否连通，如果联通就返回 dd

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
func maximumSafenessFactor(grid [][]int) int {
    n := len(grid)
    type pair struct{ x, y int }
    q := []pair{}
    dis := make([][]int, n) // 每个格子到最近的 1 的曼哈顿距离
    for i, row := range grid {
        dis[i] = make([]int, n)
        for j, x := range row {
            if x > 0 {
                q = append(q, pair{i, j})
            } else {
                dis[i][j] = -1
            }
        }
    }
    
    dir4 := []pair{{0, -1}, {0, 1}, {-1, 0}, {1, 0}} // 上下左右
    groups := [][]pair{q}
    for len(q) > 0 {
        tmp := q
        q = nil
        for _, p := range tmp {
            for _, d := range dir4 {
                x, y := p.x+d.x, p.y+d.y
                if x < 0 || x == n || y < 0 || y == n || dis[x][y] != -1 {
                    continue
                }
                q = append(q, pair{x, y})
                dis[x][y] = len(groups)
            }
        }
        groups = append(groups, q)
    }
    
    // 并集查
    fa := make([]int, n*n)
    for i := range fa {
        fa[i] = i
    }
    var find func(int) int
    find = func(x int) int {
        if fa[x] != x {
            fa[x] = find(fa[x])
        }
        return fa[x]
    }
    
    for ans := len(groups) - 2; ans > 0; ans-- { // 最后一个为空
        for _, p := range groups[ans] {
            i, j := p.x, p.y
            for _, d := range dir4 {
                x, y := i+d.x, j+d.y
                if 0 <= x && x < n && 0 <= y && y < n && dis[x][y] >= dis[i][j] { // 只能连大于等于他的
                    fa[find(x*n+y)] = find(i*n + j)
                }
            }
        }
        if find(0) == find(n*n-1) {
            return ans
        }
    }
    return 0
}

2813. 子序列最大优雅度

image-20231128184029547

解题思路：

利润从大到小排序，先选择前 kk 个项目,计算最大利润

遍历 [k+1,n][k+1,n] 中的项目, 只有当第 k+ik+i 个项目为选择过,且前面选择的项目没有重复时才能从原来选择的项目中替换以增加利润，因为:

  • 如果 k+ik+i 个项目与前面的类别相同,那么他的利润更小，不需要选他
  • 如果前面项目为出现重复, 那么类别一增一减 distinct_categoriesdistinct\_categories 不会有变化,而后面的利润比前面小，反而会降低

我们需要保证 total_profittotal\_profit 劲量大的同时去增加 categoriescategories 的数量，以达到目的

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
func findMaximumElegance(items [][]int, k int) int64 {
    sort.Slice(items, func(i, j int) bool {
        return items[i][0] > items[j][0]
    })
    ans, totalProfit := 0, 0
    vis := map[int]bool{}
    repeat := []int{}
    
    for _, item := range items[:k] {
        profit, category := item[0], item[1]
        totalProfit += profit
        if !vis[category] {
            vis[category] = true
        } else {
            repeat = append(repeat, profit)
        }
    }
    
    ans = totalProfit + len(vis)*len(vis)
    for _, item := range items[k:] {
        profit, category := item[0], item[1]
        if len(repeat) > 0 && !vis[category] { // 类别为出现过,且前面出现过重复
            vis[category] = true
            totalProfit += profit - repeat[len(repeat)-1] // 替换利润最小的
            repeat = repeat[:len(repeat)-1]
        }
        ans = max(ans, totalProfit+len(vis)*len(vis))
    }
    return int64(ans)
}