(新卷,100分)- 恢复数字序列（Java & JS & Python）

(新卷,100分)- 恢复数字序列（Java & JS & Python）

题目描述

对于一个连续正整数组成的序列，可以将其拼接成一个字符串，再将字符串里的部分字符打乱顺序。如序列8 9 10 11 12，拼接成的字符串为89101112，打乱一部分字符后得到90811211，原来的正整数10就被拆成了0和1。

现给定一个按如上规则得到的打乱字符的字符串，请将其还原成连续正整数序列，并输出序列中最小的数字。

输入描述

输入一行，为打乱字符的字符串和正整数序列的长度，两者间用空格分隔，字符串长度不超过200，正整数不超过1000，保证输入可以还原成唯一序列。

输出描述

输出一个数字，为序列中最小的数字。

用例

题目解析

本题“打乱字符的字符串”的是由“连续正整数序列”组成的，而题目又说：正整数不超过1000

因此，本题可以考虑使用滑动窗口，在1~1000整数范围内滑动，滑窗窗口的长度为输入的“连续正整数序列”的长度。

我们只需要统计“打乱字符的字符串”中各字符的数量，以及滑窗中各字符的数量，如果所有字符对于的数量都相同，那么说明对应滑窗就是一个符合要求的连续正整数数列，我们只需要取滑窗第一个数值即可。

滑窗在运动过程中，可以利用差异比较，即当前滑窗相交于上一个滑窗，失去了一个数字，新增了一个数字，当前滑窗只需要针对失去数字和新增数字的字符做数量修改即可。

Java算法源码

import java.util.HashMap;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

String s = sc.next(); // 打乱字符的字符串
int k = sc.nextInt(); // 连续正整数序列的长度

System.out.println(getResult(s, k));
}

public static int getResult(String s, int k) {
// base：统计打乱字符的字符串中 各字符的数量
HashMap<Character, Integer> base = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
base.put(c, base.getOrDefault(c, 0) + 1);
}

// 初始滑窗（长度k）中各字符的数量
HashMap<Character, Integer> count = new HashMap<>();
for (int i = 1; i <= k; i++) {
countNumChar(i + "", count, true);
}

// 比较滑窗各字符数量，和base统计的各字符数量是否一致，若一致，则说明初始滑窗就是一个符合要求的连续整数数列，该数列的最小值为1
if (cmp(base, count)) return 1;

// 否则继续尝试后续滑窗，注意题目说正整数不超过1000，因此我们可以尝试连续正整数序列取值范围就是1~1000
for (int i = 2; i <= 1000 – k + 1; i++) {
// 相较于上一个滑窗失去的数字
String remove = i – 1 + "";
countNumChar(remove, count, false);

// 相较于上一个滑窗新增的数字
String add = i + k – 1 + "";
countNumChar(add, count, true);

// 比较
if (cmp(base, count)) return i;
}

return -1; // 题目说存在唯一的序列满足条件，因此这里返回语句是走不到的
}

public static void countNumChar(String num, HashMap<Character, Integer> count, boolean isAdd) {
for (int j = 0; j < num.length(); j++) {
char c = num.charAt(j);
count.put(c, count.getOrDefault(c, 0) + (isAdd ? 1 : -1));
}
}

public static boolean cmp(HashMap<Character, Integer> base, HashMap<Character, Integer> count) {
for (Character c : base.keySet()) {
if (!count.containsKey(c) || count.get(c) – base.get(c) != 0) {
return false;
}
}
return true;
}
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});

rl.on("line", (line) => {
const [s, k] = line.split(" ");
console.log(getResult(s, Number(k)));
});

/**
*
* @param {*} s 打乱字符的字符串
* @param {*} k 连续正整数序列的长度
*/
function getResult(s, k) {
// base：统计打乱字符的字符串中 各字符的数量
const base = {};
for (let c of s) {
base[c] = (base[c] ?? 0) + 1;
}

// 初始滑窗（长度k）中各字符的数量
const count = {};
for (let i = 1; i <= k; i++) {
countNumChar(i + "", count, true);
}

// 比较滑窗各字符数量，和base统计的各字符数量是否一致，若一致，则说明初始滑窗就是一个符合要求的连续整数数列，该数列的最小值为1
if (cmp(base, count)) return 1;

// 否则继续尝试后续滑窗，注意题目说正整数不超过1000，因此我们可以尝试连续正整数序列取值范围就是1~1000
for (let i = 2; i <= 1000 – k + 1; i++) {
// 相较于上一个滑窗失去的数字
const remove = i – 1 + "";
countNumChar(remove, count, false);

// 相较于上一个滑窗新增的数字
const add = i + k – 1 + "";
countNumChar(add, count, true);

// 比较
if (cmp(base, count)) return i;
}

return -1; // 题目说存在唯一的序列满足条件，因此这里返回语句是走不到的
}

function countNumChar(num, count, isAdd) {
for (let c of num) {
count[c] = (count[c] ?? 0) + (isAdd ? 1 : -1);
}
}

function cmp(base, count) {
for (let c in base) {
if (count[c] === undefined || count[c] != base[c]) {
return false;
}
}
return true;
}

Python算法源码

# 输入获取
s, k = input().split()
k = int(k)

def cmp(base, count):
for c in base:
if count.get(c) is None or count[c] != base[c]:
return False
return True

def countNumChar(num, count, isAdd):
for c in num:
count[c] = count.get(c, 0) + (1 if isAdd else -1)

# 算法入口
def getResult():
# base：统计打乱字符的字符串中 各字符的数量
base = {}
for c in s:
base[c] = base.get(c, 0) + 1

# 初始滑窗（长度k）中各字符的数量
count = {}
for i in range(1, k + 1):
countNumChar(str(i), count, True)

# 比较滑窗各字符数量，和base统计的各字符数量是否一致，若一致，则说明初始滑窗就是一个符合要求的连续整数数列，该数列的最小值为1
if cmp(base, count):
return 1

# 否则继续尝试后续滑窗，注意题目说正整数不超过1000，因此我们可以尝试连续正整数序列取值范围就是1~1000
for i in range(2, 1000 – k + 2):
# 相较于上一个滑窗失去的数字
remove = str(i – 1)
countNumChar(remove, count, False)

# 相较于上一个滑窗新增的数字
add = str(i + k – 1)
countNumChar(add, count, True)

# 比较
if cmp(base, count):
return i

# 题目说存在唯一的序列满足条件，因此这里返回语句是走不到的
return -1

# 调用算法
print(getResult())