题目
对于一个连续正整数组成的序列,可以将其拼接成一个字符串,再将字符串里的部分字符打乱顺序。如序列89101112, 拼接成的字符串19810112,打乱部分字符后得908112111。原来的正整数10就被拆成了0和1.现给定一个按如上规则得到的打乱字符的字符串,请将其还原成连续正整数序列,并输出序列中最小的数字,
输入描述
输入行,为打乱字符的字符串和正整数序列的长度,两者间用空格分隔,字符审长度不超过200,正整数不超过10000 保证输入可以还原成唯一序列。
输出描述
输出一个数字,为序列中最小的数字
示例1:
输入
19801211 5
输出
8
说明: 正常的数字序列为8 9 10 11 12这5个数字,最小数宇为8
思路
暴力法
- 最小值设为start=1,根据输入的序列长度n,得到start开始,长度为n的字符串tempstr
- 判断tempStr通过打乱顺序后是否能和输入的字符串相等。
- 如果相等,则返回start,否则继续遍历。
关键在于第2步:如果字符串a打乱后能够得到字符串b,那么字符串a和b通过排序后得到的字符串一定是相等的。
判断字符串a打乱后是否能够得到字符串b?字符的范围为[0-9],可以用一个int[10]的数组记录每个字符串出现的次数,如下:
在字符串a中各字符出现的次数得到int[] freqa;
在字符串b中各字符出现的次数得到int[] freqb;如果freqa和freqb中每个字符出现的次数相等,那么就a打乱顺序后可以得到b
滑动窗口法的代码步骤如下:
- 用一个int[10]的数组target_freqs,记录输入字符串每个字符串出现的次数
- 初始化窗口:[1,2,3,4,n-1]。使用cur_freqs记录当前窗口每个字符串出现的次数
- 如果cur_freqs和target_freqs每个字符出现的次数均相等,那么返回此窗口最左侧的值
- 否则,开始右移窗口,加入一个n,删除一个1,并且维护cur_freqs的值
题解
滑动窗口
java">package hwod;
import java.util.*;
public class RecoveryNumQueue {
private static int[] target_freqs = new int[10];
private static int[] cur_freqs = new int[10];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
final String[] inputs = sc.nextLine().split(" ");
String s = inputs[0];
int n = Integer.parseInt(inputs[1]);
System.out.println(recoveryNumQueue(s, n));
}
//滑动窗口
private static int recoveryNumQueue(String s, int n) {
//统计输入的字符串每个字符出现的次数
for (int i = 0; i < s.length(); i++) {
target_freqs[s.charAt(i) - '0'] += 1;
}
//初始化滑动窗口
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
queue.addLast(i + 1);
for (char c : String.valueOf(i + 1).toCharArray()) {
cur_freqs[c - '0'] += 1;
}
}
//移动窗口
while (!check(cur_freqs, target_freqs)) {
int addNum = queue.peekLast() + 1;
for (char c : String.valueOf(addNum).toCharArray()) {
cur_freqs[c - '0'] += 1;
}
queue.addLast(addNum);
int removeNum = queue.peekFirst();
for (char c : String.valueOf(removeNum).toCharArray()) {
cur_freqs[c - '0'] -= 1;
}
queue.removeFirst();
}
return queue.peekFirst();
}
private static boolean check(int[] cur_freqs, int[] target_freqs) {
for (int i = 0; i < 10; i++) {
if (cur_freqs[i] != target_freqs[i]) return false;
}
return true;
}
}
暴力破解
java">package hwod;
import java.util.*;
public class RecoveryNumQueue {
private static int[] target_freqs = new int[10];
private static int[] cur_freqs = new int[10];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
final String[] inputs = sc.nextLine().split(" ");
String s = inputs[0];
int n = Integer.parseInt(inputs[1]);
System.out.println(recoveryNumQueue(s, n));
}
//暴力查找
private static int recoveryNumQueue(String s, int n) {
int ans = 0;
while (true) {
if (check(ans, n, s)) return ans;
ans++;
}
}
private static String sort(String string) {
char[] chars = string.toCharArray();
Arrays.sort(chars);
return String.valueOf(chars);
}
private static boolean check(int start, int n, String s) {
StringBuilder sb = new StringBuilder();
for (int i = start; i < start + n; i++) {
sb.append(i);
}
return sort(sb.toString()).equals(s);
}
}
推荐
如果你对本系列的其他题目感兴趣,可以参考华为OD机试真题及题解(JAVA),查看当前专栏更新的所有题目。