E卷-刷题笔记合集🔗

恢复数字序列

问题描述

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

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

输入格式

输入一行，包含两个部分，用空格分隔：

1. 一个打乱字符的字符串 。
2. 一个正整数 ，表示正整数序列的长度。

输出格式

输出一个整数，表示还原后的连续正整数序列中最小的数字。

样例输入

19801211 5

样例输出

8

样例解释

数据范围

• 字符串 的长度不超过 200。
• 。
• 保证输入可以还原成唯一的连续正整数序列。

题解

滑动窗口

这道题的核心在于如何从打乱的字符串中还原出原始的连续正整数序列。解题思路如下：

1. 观察题目给出的条件：正整数不超过1000。这为解题提供了一个重要的限制条件。
2. 使用滑动窗口的思想，在1到1000的范围内滑动一个长度为N的窗口。
3. 关键点在于如何高效地比较两个字符串是否包含相同的字符及数量。这里使用计数的方法：对输入的打乱字符串，统计每个数字字符出现的次数。对滑动窗口内的数字，同样统计每个数字字符出现的次数。比较这两个统计结果是否完全相同。
4. 算法步骤： a. 统计输入字符串中每个数字字符的出现次数。 b. 初始化滑动窗口，统计1到N的连续数字中每个数字字符的出现次数。 c. 比较初始窗口的统计结果与输入字符串的统计结果，如果相同，返回1。 d. 如果不同，向右滑动窗口：减去离开窗口的数字的字符计数增加进入窗口的新数字的字符计数比较新的窗口统计结果与输入字符串的统计结果 e. 重复步骤d，直到找到匹配的序列或遍历完所有可能的起始数字。

参考代码

• Python

def count_chars(s):
    """
    统计字符串中每个字符的出现次数
    :param s: 输入字符串
    :return: 字符计数字典
    """
    return {c: s.count(c) for c in set(s)}

def update_count(num, count, is_add):
    """
    更新字符计数字典
    :param num: 要更新的数字
    :param count: 字符计数字典
    :param is_add: True表示增加计数，False表示减少计数
    """
    for c in str(num):
        count[c] = count.get(c, 0) + (1 if is_add else -1)

def is_match(target, current):
    """
    检查两个计数字典是否匹配
    :param target: 目标计数字典
    :param current: 当前计数字典
    :return: 是否匹配
    """
    return all(current.get(c, 0) == target[c] for c in target)

def find_sequence_start(s, k):
    """
    找到连续序列的起始数字
    :param s: 打乱的字符串
    :param k: 连续序列的长度
    :return: 连续序列的起始数字
    """
    # 统计目标字符串中每个字符的出现次数
    target_count = count_chars(s)
    
    # 初始化滑动窗口，统计1到k的连续数字中每个字符的出现次数
    window_count = count_chars(''.join(str(i) for i in range(1, k+1)))
    
    # 检查初始窗口是否匹配
    if is_match(target_count, window_count):
        return 1
    
    # 滑动窗口，检查每个可能的起始数字
    for start in range(2, 1001 - k + 1):
        # 移除离开窗口的数字的字符计数
        update_count(start - 1, window_count, False)
        # 添加进入窗口的新数字的字符计数
        update_count(start + k - 1, window_count, True)
        # 检查当前窗口是否匹配
        if is_match(target_count, window_count):
            return start
    
    # 理论上不会达到这里，因为题目保证有唯一解
    return -1

# 输入处理
s, k = input().split()
k = int(k)

# 输出结果
print(find_sequence_start(s, k))

• C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_LEN 201
#define MAX_NUM 1000

void count_chars(const char* s, int* count) {
    // 统计字符串中每个字符的出现次数
    while (*s) {
        count[*s - '0']++;
        s++;
    }
}

void update_count(int num, int* count, int is_add) {
    // 更新字符计数数组
    char num_str[5];
    sprintf(num_str, "%d", num);
    for (int i = 0; num_str[i]; i++) {
        count[num_str[i] - '0'] += is_add ? 1 : -1;
    }
}

int is_match(const int* target, const int* current) {
    // 检查两个计数数组是否匹配
    for (int i = 0; i < 10; i++) {
        if (target[i] != current[i]) return 0;
    }
    return 1;
}

int find_sequence_start(const char* s, int k) {
    int target_count[10] = {0};
    int window_count[10] = {0};
    
    // 统计目标字符串中每个字符的出现次数
    count_chars(s, target_count);
    
    // 初始化滑动窗口，统计1到k的连续数字中每个字符的出现次数
    for (int i = 1; i <= k; i++) {
        update_count(i, window_count, 1);
    }
    
    // 检查初始窗口是否匹配
    if (is_match(target_count, window_count)) return 1;
    
    // 滑动窗口，检查每个可能的起始数字
    for (int start = 2; start <= MAX_NUM - k + 1; start++) {
        // 移除离开窗口的数字的字符计数
        update_count(start - 1, window_count, 0);
        // 添加进入窗口的新数字的字符计数
        update_count(start + k - 1, window_count, 1);
        // 检查当前窗口是否匹配
        if (is_match(target_count, window_count)) return start;
    }
    
    // 理论上