网易2021秋招-最小字典序字符串

网易2021秋招-最小字典序字符串

第一行输入2个数字

第一个数字n代表字符串应该扩充为多少位,第二个数字m代表字符串当前有多少个字符

第二行输入m个数字,代表当前字符串

第三行为输出,输出需要满足在不改变当前字符串前后位置的情况下,扩充为长度为n的最小字典序的字符串

每个数字仅可以选择1次

示例1:

1
2
3
5 3
2 3 5
1 2 3 4 5

示例2:

1
2
3
5 2
4 2
1 3 4 2 5

解题思路

观察用例可以输入的n就是扩展后字符的最大数,且每个数字只可以选择1次

现有的数字的前后顺序不变,想要字典序最小,插入的数字需要和现有的数字进行比较,小的数字优先插入到现有数字之前。

可以利用一个队列Queue存储当前的字符,保证先后顺序,同时需要一个n+1的数组,用来保存数字是否被选择的状态。

将原始的字符串在对应位置置为true,表示已经选择,之后的插入数字中不能从中选择这类数字。同时将这些数字加入Queue保证先后顺序

利用StringBuilder来进行最终答案的拼接

  • 循环从1开始到n,进行插入数字和队列数字的大小判断:
  • 当队列不为空且队列的头部小于新选择数字i时,从队列中取出头部原始的数字加入到结果res
  • 如果不小于,则说明未选择的数字应该插入到前面,res.append(i + " ");
  • 如果循环完了,队列中还有值,直接把队列中所有数字按顺序加入res即可
  • 最后去除首尾空格,返回结果

Java代码

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
import java.util.*;

public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
boolean[] visited = new boolean[n + 1];
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < m; i++) {
int num = sc.nextInt();
visited[num] = true;
queue.offer(num);
}
StringBuilder res = new StringBuilder();
for (int i = 1; i <= n; i++) {
if (visited[i]) continue;
while (!queue.isEmpty() && queue.peek() < i) {
res.append(queue.poll() + " ");
}
res.append(i + " ");
}
while (!queue.isEmpty()) {
res.append(queue.poll() + " ");
}
System.out.println(res.toString().trim());
}
}
打赏了解一下?
0%