对于一个连续正整数组成的序列，可以将其拼接成一个字符串，再将字符串里的部分字符打乱顺序。如序列8 9 10 11 12，拼接成的字符串为89101112，打乱一部分字符后得到90811211，原来的正整数10就被拆成了0和1。
现给定一个按如上规则得到的打乱字符的字符串，请将其还原成连续正整数序列，并输出序列中最小的数字
19801211 5
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">8
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">利用 Python 的 collections.Counter 类统计字符串中各字符的频率。
对输入字符串 sequence 进行统计，作为目标频率 sequence_count。
滑动窗口初始化：
初始化一个滑动窗口，包含从 1 到 length 的所有整数。
对这些整数的字符频率进行统计，作为滑动窗口的当前频率 current_count。
滑动窗口比较：
如果当前滑动窗口的频率 current_count 与目标频率 sequence_count 相等，返回起始整数。
滑动窗口更新：
将滑动窗口向右滑动一位：
从当前频率中减去滑动窗口的第一个整数的字符频率。
添加滑动窗口新加入的整数的字符频率。
每次更新后，检查当前频率是否与目标频率相等。
返回结果：
如果在滑动窗口中找到了匹配的频率，返回起始整数。
如果遍历完可能的滑动窗口后仍未找到，返回 -1。
from collections import Counter
# 输入获取
sequence, length = input().split()
length = int(length)
# 统计数字的字符频率
def char_count(num):
return Counter(str(num))
# 找出最小符合条件的连续整数序列起点
def find_min_number():
# 统计输入字符串的字符频率
sequence_count = Counter(sequence)
# 初始化滑动窗口的字符频率
current_count = Counter()
for i in range(1, length + 1):
current_count.update(char_count(i)) # 统计从 1 到 length 的字符频率
# 滑动窗口比较
if current_count == sequence_count: # 如果初始窗口的频率与目标频率相等
return 1
# 移动滑动窗口
for i in range(2, 1000 - length + 2): # 从 2 开始滑动窗口，直到窗口结束不超过 1000
# 更新频率：移除旧数字字符，添加新数字字符
current_count.subtract(char_count(i - 1)) # 移除窗口左侧的数字
current_count.update(char_count(i + length - 1)) # 添加窗口右侧的新数字
if current_count == sequence_count: # 如果当前窗口频率与目标频率相等
return i
return -1 # 如果未找到符合条件的序列，返回 -1
# 调用算法
print(find_min_number())
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">主要步骤：
字符频率统计：
使用一个 Map
滑动窗口遍历：
遍历所有可能的连续整数序列，起点从 1 开始，到 1000 - sequenceLen + 1。
对当前窗口内的所有整数的字符统计频率。
频率匹配：
将当前窗口的字符频率与 scrambledInput 的字符频率进行比较。
如果匹配，返回当前窗口的起点。
返回结果：
如果遍历完所有可能的窗口后未找到匹配，返回 -1
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
// 读取输入
String scrambledInput = input.next(); // 输入的乱序字符
int sequenceLen = input.nextInt(); // 连续整数序列的长度
// 调用方法计算最小起点并输出
System.out.println(minNumber(scrambledInput, sequenceLen));
}
/**
* 找到最小的连续整数序列起点，使其字符频率与 scrambledInput 的频率相同
*
* @param scrambledInput 输入的字符序列
* @param sequenceLen 连续整数序列的长度
* @return 最小的起点，如果不存在返回 -1
*/
public static int minNumber(String scrambledInput, int sequenceLen) {
// 统计 scrambledInput 中每个字符的频率
Map<Character, Integer> originalCount = new HashMap<>();
countChars(scrambledInput, originalCount);
// 遍历所有可能的连续整数序列的起点
for (int start = 1; start <= 1000 - sequenceLen + 1; start++) {
// 统计当前窗口的字符频率
Map<Character, Integer> seqCount = new HashMap<>();
for (int i = start; i < start + sequenceLen; i++) {
countChars(String.valueOf(i), seqCount);
}
// 如果当前窗口频率与目标频率相同，返回起点
if (compareCounts(originalCount, seqCount)) {
return start;
}
}
// 如果未找到匹配的序列，返回 -1
return -1;
}
/**
* 统计字符串中每个字符的频率
*
* @param str 待统计的字符串
* @param countMap 用于存储频率统计结果的 Map
*/
private static void countChars(String str, Map<Character, Integer> countMap) {
for (char ch : str.toCharArray()) { // 遍历字符串中的每个字符
countMap.put(ch, countMap.getOrDefault(ch, 0) + 1); // 更新字符频率
}
}
/**
* 比较两个字符频率表是否相同
*
* @param original 目标频率表
* @param compared 待比较的频率表
* @return 如果两个频率表相同返回 true，否则返回 false
*/
private static boolean compareCounts(Map<Character, Integer> original, Map<Character, Integer> compared) {
// 如果两者大小不同，直接返回 false
if (original.size() != compared.size()) return false;
// 遍历目标频率表的键值对进行逐一比较
for (char ch : original.keySet()) {
if (!compared.containsKey(ch) || !compared.get(ch).equals(original.get(ch))) {
return false; // 如果某个字符的频率不相等，返回 false
}
}
return true; // 如果所有频率都相等，返回 true
}
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">更新中
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">更新中
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">这段代码的目标是找到一个长度为 k 的连续整数序列，其组成的字符与给定的字符串 str 的字符完全一致。代码逐步生成所有可能的连续整数序列，检查其字符组成是否与目标字符串相同。如果找到第一个符合条件的序列，返回其起始整数；如果找不到，则返回 -1
枚举所有可能的起始整数序列：
枚举范围为 [1, 1000 - k + 1]，确保序列长度不超出范围。
对每个起始整数 start，构造连续 k 个整数组成的字符串 seqStr。
比较字符频率：
检查 seqStr 和目标字符串 str 的字符是否完全一致。
使用字符频率统计（哈希表）进行比较，确保两者包含的字符种类和频率完全相同。
返回结果：
如果找到匹配的序列，返回其起始整数 start。
如果遍历结束仍未找到匹配，返回 -1。
// 主函数：查找最小的连续整数序列起点
function findMinSeq(str, k) {
let result = -1; // 结果初始化为 -1，表示未找到匹配的序列
// 枚举起始整数的范围
for (let start = 1; start <= 1000 - k + 1; start++) {
// 生成长度为 k 的连续整数序列的字符串
const seqStr = Array.from({ length: k }, (_, i) => start + i).join('');
// 判断字符组成是否与目标字符串相同
if (isSameChars(seqStr, str)) {
result = start; // 如果匹配，记录起始整数
break; // 终止循环
}
}
return result; // 返回找到的起始整数，或 -1
}
// 辅助函数：判断两个字符串的字符组成是否相同
function isSameChars(seqStr, shuffledStr) {
// 长度不一致直接返回 false
if (seqStr.length !== shuffledStr.length) return false;
// 统计字符频率的工具函数
const charCount = (s) =>
[...s].reduce((acc, c) => (acc[c] = (acc[c] || 0) + 1, acc), {});
// 分别统计 seqStr 和 shuffledStr 的字符频率
const seqCount = charCount(seqStr);
const shufCount = charCount(shuffledStr);
// 比较两个字符频率是否完全相同
return Object.keys(seqCount).every(
(key) => seqCount[key] === shufCount[key]
);
}
// 使用 readline 接收用户输入
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
// 处理用户输入
rl.on("line", (line) => {
const [shuffledStr, k] = line.split(" "); // 分割输入
console.log(findMinSeq(shuffledStr, Number(k))); // 调用主函数并输出结果
});
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：