题解：P12289 [蓝桥杯 2024 国 Java A] 修改数位
\(\mathbf{upd\ 2025/6/13}\)：减少了一些废话，精简了文章内容。
思路与算法
题目大意
题目要求我们找到一个长度为 \(10\) 的子串，使得该子串包含从 \(0\) 到 \(9\) 的所有数字，且每个数字恰好出现一次。
思路
为了满足要求，我们可以修改原数的某些数字，但需要最小化修改的代价（即修改的数字差值之和）。同时，修改后的数仍需满足没有前导零的限制。
不是我说，我的算法倒还挺暴力的。
我的做法是现选出一个字串，然后再使用类似于桶排序的方法统计数字个数。由于这里字串长度是固定的，且是由左侧向右侧扫描，就是滑动窗口的写法。
每次桶排序统计结束后，我们能够得到哪些数字被多算了，哪些数字被少算了，这时，我们不断保证被替换的的数字与替换后的数字之差最小即可。
这个时候要注意两个特殊情况：
1. 原串长度小于 \(10\)，也就是说根本不可能出现 \(10\) 个不同的数字。
2. 当扫描第一个长度为 \(10\) 的字串时，要注意第一个数不能被修改为 \(0\)（即不能有前导零）。
算法
由算法标签可知
从上面的推导，我们能知道要写以下几个算法：
1.滑动窗口：
遍历长度为 \(10\) 的所有子串。其中，对每个子串，计算其是否已经是一个排列。如果是，则代价为 \(0\)，直接返回结果。如果不是，则计算将其变为一个排列的最小代价。
tip：这里不是真正意义上的的双指针，实际上是单指针。
2.桶排序：
统计每个数字的出现次数。
这里我们还做了一些其他的优化（类似于 KMP？）：
1.减少重复计算：
滑动窗口可以通过增量更新频率数组（就是当它往后移动的时候，直接加减新进入窗口中的数字与离开窗口中的数字），避免重复计算。
2.排序：
对于多余和缺失的数字，可以排序后匹配，确保代价最小。
代码
这里献上自己的代码（Python 超时了，就不放出来了）：
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89 | #include <bits/stdc++.h>
using namespace std;
int main() {
string m_str;
cin >> m_str;
int n = m_str.size();
if (n < 10) {
cout << -1 << endl;
return 0;
}
int min_cost = INT_MAX;
// 滑动窗口遍历所有长度为 10 的子串
for (int i = 0; i <= n - 10; i++) {
string window = m_str.substr(i, 10);
int freq[10] = {0};
// 统计子串中每个数字的频率
for (char d : window) {
freq[d - '0']++;
}
// 检查是否已经是一个排列
bool is_permutation = true;
for (int d = 0; d <= 9; d++) {
if (freq[d] != 1) {
is_permutation = false;
break;
}
}
// 如果是排列，直接输出结果
if (is_permutation) {
cout << 0 << endl;
return 0;
}
// 记录多余和缺失的数字
char dup[10], miss[10];
int dup_cnt = 0, miss_cnt = 0;
for (int d = 0; d <= 9; d++) {
int cnt = freq[d];
if (cnt > 1) {
for (int j = 1; j < cnt; j++) {
dup[dup_cnt++] = d + '0';
}
} else if (cnt == 0) {
miss[miss_cnt++] = d + '0';
}
}
// 计算代价
bool mnz = (window[0] == '0');
// 是否有前导零
int cost = 0;
if (mnz) {
// 特殊处理前导零
bool found = false;
for (int j = 0; j < dup_cnt; j++) {
if (dup[j] == window[0]) {
char best_d = '0';
int min_diff = INT_MAX;
for (int k = 0; k < miss_cnt; k++) {
if (miss[k] != '0') {
int diff = abs(miss[k] - window[0]);
if (diff < min_diff) {
min_diff = diff;
best_d = miss[k];
}
}
}
if (best_d == '0') {
cost = INT_MAX;
break;
}
cost += min_diff;
found = true;
break;
}
}
if (!found) continue;
}
// 匹配多余和缺失的数字
sort(dup, dup + dup_cnt);
sort(miss, miss + miss_cnt);
for (int j = 0; j < dup_cnt; j++) {
cost += abs(miss[j] - dup[j]);
}
// 更新最小代价
min_cost = min(min_cost, cost);
}
cout << min_cost << endl;
return 0;
}
|
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109 | using System;
using System.Linq;
class Program
{
static void Main()
{
string m_str = Console.ReadLine();
int n = m_str.Length; -1
if (n < 10)
{
Console.WriteLine(-1);
return;
}
int min_cost = int.MaxValue;
for (int i = 0; i <= n - 10; i++)
{
string window = m_str.Substring(i, 10);
int[] freq = new int[10];
// 统计子串中每个数字的频率
foreach (char d in window)
{
freq[d - '0']++;
}
// 检查是否已经是一个排列
bool is_permutation = true;
for (int d = 0; d <= 9; d++)
{
if (freq[d] != 1)
{
is_permutation = false;
break;
}
}
// 如果是排列，直接输出结果
if (is_permutation)
{
Console.WriteLine(0);
return;
}
// 记录多余和缺失的数字
char[] dup = new char[10];
char[] miss = new char[10];
int dup_cnt = 0, miss_cnt = 0;
for (int d = 0; d <= 9; d++)
{
int cnt = freq[d];
if (cnt > 1)
{
for (int j = 1; j < cnt; j++)
{
dup[dup_cnt++] = (char)(d + '0');
}
}
else if (cnt == 0)
{
miss[miss_cnt++] = (char)(d + '0');
}
}
// 计算代价
bool mnz = (window[0] == '0'); // 是否有前导零
int cost = 0;
if (mnz)
{
// 特殊处理前导零
bool found = false;
for (int j = 0; j < dup_cnt; j++)
{
if (dup[j] == window[0])
{
char best_d = '0';
int min_diff = int.MaxValue;
for (int k = 0; k < miss_cnt; k++)
{
if (miss[k] != '0')
{
int diff = Math.Abs(miss[k] - window[0]);
if (diff < min_diff)
{
min_diff = diff;
best_d = miss[k];
}
}
}
if (best_d == '0')
{
cost = int.MaxValue;
break;
}
cost += min_diff;
found = true;
break;
}
}
if (!found) continue;
}
// 匹配多余和缺失的数字
Array.Sort(dup, 0, dup_cnt);
Array.Sort(miss, 0, miss_cnt);
for (int j = 0; j < dup_cnt; j++)
{
cost += Math.Abs(miss[j] - dup[j]);
}
// 更新最小代价
min_cost = Math.Min(min_cost, cost);
}
Console.WriteLine(min_cost);
}
}
|
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88 | import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String m_str = scanner.nextLine();
int n = m_str.length();
if (n < 10) {
System.out.println(-1);
return;
}
int min_cost = Integer.MAX_VALUE;
for (int i = 0; i <= n - 10; i++) {
String window = m_str.substring(i, i + 10);
int[] freq = new int[10];
// 统计子串中每个数字的频率
for (char d : window.toCharArray()) {
freq[d - '0']++;
}
// 检查是否已经是一个排列
boolean is_permutation = true;
for (int d = 0; d <= 9; d++) {
if (freq[d] != 1) {
is_permutation = false;
break;
}
}
// 如果是排列，直接输出结果
if (is_permutation) {
System.out.println(0);
return;
}
// 记录多余和缺失的数字
char[] dup = new char[10];
char[] miss = new char[10];
int dup_cnt = 0, miss_cnt = 0;
for (int d = 0; d <= 9; d++) {
int cnt = freq[d];
if (cnt > 1) {
for (int j = 1; j < cnt; j++) {
dup[dup_cnt++] = (char) (d + '0');
}
} else if (cnt == 0) {
miss[miss_cnt++] = (char) (d + '0');
}
}
// 计算代价
boolean mnz = (window.charAt(0) == '0'); // 是否有前导零
int cost = 0;
if (mnz) {
// 特殊处理前导零
boolean found = false;
for (int j = 0; j < dup_cnt; j++) {
if (dup[j] == window.charAt(0)) {
char best_d = '0';
int min_diff = Integer.MAX_VALUE;
for (int k = 0; k < miss_cnt; k++) {
if (miss[k] != '0') {
int diff = Math.abs(miss[k] - window.charAt(0));
if (diff < min_diff) {
min_diff = diff;
best_d = miss[k];
}
}
}
if (best_d == '0') {
cost = Integer.MAX_VALUE;
break;
}
cost += min_diff;
found = true;
break;
}
}
if (!found) continue;
}
// 匹配多余和缺失的数字
Arrays.sort(dup, 0, dup_cnt);
Arrays.sort(miss, 0, miss_cnt);
for (int j = 0; j < dup_cnt; j++) {
cost += Math.abs(miss[j] - dup[j]);
}
// 更新最小代价
min_cost = Math.min(min_cost, cost);
}
System.out.println(min_cost);
}
}
|