当前位置： 首页 > article >正文

【2024年华为OD机试】(B卷,100分)- 恢复数字序列 （Java JS PythonC/C++）

article 2025/1/18 6:25:19

在这里插入图片描述

一、问题描述

题目解析

题目描述

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

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

输入描述

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

输出描述

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

用例

输入

19801211 5

输出

8

说明
无

题目解析

问题分析

  1. 目标
    给定一个打乱字符的字符串和一个正整数序列的长度，还原出原始的连续正整数序列，并输出序列中最小的数字。

  2. 关键点

    • 字符串是由连续正整数序列拼接而成，字符顺序被打乱。
    • 正整数不超过 1000，序列长度已知。
    • 需要找到唯一的连续正整数序列，使得其字符组成与输入字符串一致。

  3. 问题转化
    通过滑动窗口在 1~1000 范围内寻找一个长度为 n 的连续序列，使得该序列拼接后的字符组成与输入字符串一致。

解题思路

  1. 统计输入字符串的字符频率
    使用哈希表统计输入字符串中每个字符的出现次数。

  2. 滑动窗口遍历

    • 在 1~1000 范围内滑动一个长度为 n 的窗口。
    • 对于每个窗口，统计窗口内数字拼接后的字符频率。
    • 比较窗口字符频率与输入字符串字符频率是否一致。

  3. 优化滑动窗口

    • 利用滑动窗口的特性，每次移动窗口时，只需更新窗口两端的变化（移除一个数字，添加一个数字）。
    • 避免每次重新统计整个窗口的字符频率。

  4. 返回结果
    找到匹配的窗口后，返回窗口中的最小数字。

示例分析

输入

19801211 5

步骤

  1. 统计输入字符串 19801211 的字符频率：

    • '1': 3, '9': 1, '8': 1, '0': 1, '2': 1。

  2. 滑动窗口遍历：

    • 窗口长度为 5，从 1 开始滑动。
    • 窗口 8, 9, 10, 11, 12 拼接后的字符串为 89101112，字符频率为：
      • '8': 1, '9': 1, '1': 3, '0': 1, '2': 1。
    • 与输入字符串字符频率一致，匹配成功。

  3. 返回窗口中的最小数字 8。

复杂度分析

  1. 时间复杂度

    • 统计输入字符串字符频率：O(m)，其中 m 是字符串长度。
    • 滑动窗口遍历：O(1000 * n)，其中 n 是序列长度。
    • 总时间复杂度：O(m + 1000 * n)。

  2. 空间复杂度

    • 哈希表存储字符频率：O(1)（字符种类有限）。
    • 总空间复杂度：O(1)。

总结

本题的核心是通过滑动窗口和字符频率统计，高效地还原出原始的连续正整数序列。关键在于：

  1. 利用滑动窗口减少重复计算。
  2. 通过字符频率匹配快速判断窗口是否满足条件。
  3. 时间复杂度优化，避免暴力枚举。

二、JavaScript算法源码

这段JavaScript代码实现了一个程序，通过Node.js环境下的控制台输入接口获取数据，然后处理字符串以查找符合条件的连续整数序列。以下是对这段代码的详细解析和讲解：

核心代码讲解

输入处理
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)));
});
  • 功能：使用readline模块监听控制台输入。
  • 逻辑解释：
    • 创建readline接口，用于读取标准输入输出。
    • 使用rl.on("line", callback)监听每行输入。
    • 将输入行按空格分割为字符串和整数。
    • 调用getResult(s, Number(k))并输出结果。
getResult函数
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统计的各字符数量是否一致
  if (cmp(base, count)) return 1;

  // 尝试后续滑窗
  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; // 题目假设存在唯一序列满足条件
}
  • 功能：查找符合条件的连续整数序列。
  • 逻辑解释：
    • 使用base对象记录字符串s中各字符的数量。
    • 使用count对象记录初始滑动窗口中各字符数量。
    • 比较初始滑窗是否符合条件，符合则返回1。
    • 否则，使用滑动窗口技术，调整窗口位置，检查新增和移除字符后是否符合条件。
    • 滑动窗口从整数2开始尝试至1000。
    • 如果找到符合条件的序列，返回序列起始值。
辅助函数
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;
}
  • countNumChar：更新count对象中字符数量。isAdd为true则增加，否则减少。
  • cmp：比较base和count是否相同，若不同返回false，否则返回true。

代码总结

  • 核心思想：将字符串视作字符的多重集，滑动窗口法用于查找连续整数序列。
  • 使用场景：适合用于字符序列匹配问题，尤其是需要通过滑动窗口技术优化的场景。

该代码在处理输入时假设只有一个符合条件的序列，因此不考虑无法找到的情况。希望这些解释能帮助您理解这段代码的实现逻辑！如果您有其他问题或需要更多解释，请随时问我。

三、Java算法源码

这段Java代码实现了一个程序，用于判断一个打乱的字符序列中是否存在一个连续的正整数序列的字符表示，且该整数序列的长度为给定值k。以下是对这段代码的详细解析和讲解，涵盖了关键部分和实现细节。

Java代码解析与讲解

主函数 (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));
}
  • 功能：读取输入字符串和整数k。
  • 逻辑解释：
    • 使用Scanner对象从标准输入流中读取数据。
    • 调用getResult方法，传入读取的字符串s和整数k。
    • 输出结果。
getResult 方法
public static int getResult(String s, int k) {
    // 统计打乱字符的字符串中各字符的数量
    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是否一致
    if (cmp(base, count)) return 1;

    // 尝试后续滑窗（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; // 理论上不会触发
}
  • 功能：寻找符合条件的连续正整数序列。
  • 逻辑解释：
    • 使用base记录输入字符串s中每种字符出现的次数。
    • 使用count记录当前滑动窗口中字符的频率。
    • 首先检查初始窗口，如果匹配则返回1。
    • 如果不匹配，移动滑动窗口，逐步检查每个窗口。
    • for循环从2到1000 - k + 1，确保遍历所有可能的连续整数序列。
    • countNumChar用于更新滑动窗口中字符的频率。
countNumChar 方法
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));
    }
}
  • 功能：更新字符计数。
  • 逻辑解释：
    • 遍历字符串num的每个字符c。
    • 根据isAdd标志增加或减少count中该字符的计数。
cmp 方法
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;
}
  • 功能：比较两个字符计数器是否相等。
  • 逻辑解释：
    • 检查count中是否包含base中的所有字符且对应的计数相同。
    • 如果有任何字符的计数不匹配，返回false。

总结

  • 核心思想：使用滑动窗口法和哈希表计数，查找满足条件的整数序列。
  • 使用场景：有效地解决字符匹配问题，尤其当字符构成的是数字形式的字符串时。
  • 代码优化：利用哈希表（HashMap）快速查找和更新字符频率，提升性能。

希望这些解释能帮助您理解这段代码。如果您有其他问题或需要进一步的解释，请随时提问！

四、Python算法源码

这段Python代码实现了一个程序，用于查找一个打乱字符的字符串中是否存在一个连续的正整数序列（以字符形式表示），且该序列的长度为给定的整数k。以下是对这段代码的详细解析和讲解：

核心代码解析

输入处理
s, k = input().split()
k = int(k)
  • 功能：从标准输入中读取数据。
  • 逻辑解释：
    • 使用input().split()读取一行输入，并按空格分割成两个部分。
    • s是输入的字符序列，k是整数，表示序列长度。
    • 将k转换为整数类型。
辅助函数
def cmp(base, count):
    for c in base:
        if count.get(c) is None or count[c] != base[c]:
            return False
    return True
  • 功能：比较两个字符计数字典是否相等。
  • 逻辑解释：
    • 遍历base字典中的每个字符c。
    • 检查count中是否包含base中的所有字符且对应的计数相同。
    • 如果有任何字符的计数不匹配，返回False。
def countNumChar(num, count, isAdd):
    for c in num:
        count[c] = count.get(c, 0) + (1 if isAdd else -1)
  • 功能：更新字符计数。
  • 逻辑解释：
    • 遍历字符串num的每个字符c。
    • 根据isAdd标志增加或减少count中该字符的计数。
主算法函数 (getResult)
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统计的各字符数量是否一致
    if cmp(base, count):
        return 1

    # 尝试后续滑窗
    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
  • 功能：寻找符合条件的连续正整数序列。
  • 逻辑解释：
    • 使用base记录输入字符串s中每种字符出现的次数。
    • 使用count记录当前滑动窗口中字符的频率。
    • 首先检查初始窗口（从1到k），如果匹配则返回1。
    • 如果不匹配，通过滑动窗口技术逐步检查每个后续窗口。
    • 从整数2开始尝试至1000 - k + 1，确保遍历所有可能的连续整数序列。
    • 返回匹配的起始整数值。

总结

  • 核心思想：利用滑动窗口法和字典计数，寻找满足条件的整数序列。
  • 使用场景：该算法适用于需要判断字符序列是否能够重新排列为某种特定模式的场景。
  • 代码优化：通过对字符串字符进行频率计数，降低了时间复杂度。

希望这些解释能帮助您理解这段代码的实现逻辑！如果有其他问题或需要进一步的解释，请随时问我。

五、C/C++算法源码：

C++ 版本

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

// 比较两个哈希表是否相等
bool cmp(unordered_map<char, int>& base, unordered_map<char, int>& count) {
    for (auto& pair : base) {
        if (count[pair.first] != pair.second) {
            return false;
        }
    }
    return true;
}

// 更新字符计数
void countNumChar(const string& num, unordered_map<char, int>& count, bool isAdd) {
    for (char c : num) {
        count[c] += (isAdd ? 1 : -1);
    }
}

// 主算法
int getResult(string s, int k) {
    // 统计输入字符串中各字符的数量
    unordered_map<char, int> base;
    for (char c : s) {
        base[c]++;
    }

    // 初始化滑动窗口中各字符的数量
    unordered_map<char, int> count;
    for (int i = 1; i <= k; ++i) {
        countNumChar(to_string(i), count, true);
    }

    // 比较初始滑窗
    if (cmp(base, count)) {
        return 1;
    }

    // 尝试后续滑窗
    for (int i = 2; i <= 1000 - k + 1; ++i) {
        // 移除上一个滑窗的第一个数字
        countNumChar(to_string(i - 1), count, false);

        // 添加新的滑窗的最后一个数字
        countNumChar(to_string(i + k - 1), count, true);

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

    // 理论上不会触发
    return -1;
}

int main() {
    string s;
    int k;
    cin >> s >> k;
    cout << getResult(s, k) << endl;
    return 0;
}
代码讲解
  • unordered_map：用于存储字符和它们的出现次数，相当于Python中的字典。
  • cmp函数：比较两个字符频率表，判断是否相等。
  • countNumChar函数：更新字符计数，根据isAdd标志增加或减少。
  • getResult函数：实现主逻辑，通过滑动窗口技术寻找符合条件的整数序列。

C 语言版本

C语言不直接支持哈希表，但可以使用数组或结构体模拟。这里使用简单的数组来模拟字符计数。

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

#define MAX_SIZE 256 // 假设字符集大小

// 比较两个字符计数数组是否相等
int cmp(int base[], int count[]) {
    for (int i = 0; i < MAX_SIZE; i++) {
        if (base[i] != count[i]) {
            return 0; // 不相等
        }
    }
    return 1; // 相等
}

// 更新字符计数
void countNumChar(const char* num, int count[], int isAdd) {
    for (int i = 0; num[i] != '\0'; i++) {
        count[(unsigned char)num[i]] += (isAdd ? 1 : -1);
    }
}

// 主算法
int getResult(char* s, int k) {
    // 统计输入字符串中各字符的数量
    int base[MAX_SIZE] = {0};
    for (int i = 0; s[i] != '\0'; i++) {
        base[(unsigned char)s[i]]++;
    }

    // 初始化滑动窗口中各字符的数量
    int count[MAX_SIZE] = {0};
    char num[10]; // 用于存储整数的字符串形式
    for (int i = 1; i <= k; i++) {
        sprintf(num, "%d", i);
        countNumChar(num, count, 1);
    }

    // 比较初始滑窗
    if (cmp(base, count)) {
        return 1;
    }

    // 尝试后续滑窗
    for (int i = 2; i <= 1000 - k + 1; i++) {
        // 移除上一个滑窗的第一个数字
        sprintf(num, "%d", i - 1);
        countNumChar(num, count, 0);

        // 添加新的滑窗的最后一个数字
        sprintf(num, "%d", i + k - 1);
        countNumChar(num, count, 1);

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

    // 理论上不会触发
    return -1;
}

int main() {
    char s[1001]; // 假设输入长度不会超过1000
    int k;
    scanf("%s %d", s, &k);
    printf("%d\n", getResult(s, k));
    return 0;
}
代码讲解
  • 字符计数数组：base和count是整型数组，用于记录字符频率。
  • cmp函数：对比两个计数数组是否完全相等。
  • countNumChar函数：更新字符计数。
  • getResult函数：实现主逻辑，通过调整滑动窗口查找符合条件的整数序列。
  • sprintf：用于将整数转换为字符形式。

这两个实现版本分别利用了C++和C语言的特性，解决了同样的问题。希望这些解释能帮助您理解代码的实现！如果有其他疑问，请随时询问。

六、尾言

什么是华为OD？

华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。

为什么刷题很重要？

  1. 机试是进入技术面的第一关：
    华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。

  2. 技术面试需要手撕代码：
    技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。

  3. 入职后的可信考试：
    入职华为后，还需要通过“可信考试”。可信考试分为三个等级：

    • 入门级：主要考察基础算法与编程能力。
    • 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
    • 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。

刷题策略与说明：

2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：

  1. 关注历年真题：

    • 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
    • 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。

  2. 适应新题目：

    • E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
    • 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。

  3. 掌握常见算法：
    华为OD考试通常涉及以下算法和数据结构：

    • 排序算法（快速排序、归并排序等）
    • 动态规划（背包问题、最长公共子序列等）
    • 贪心算法
    • 栈、队列、链表的操作
    • 图论（最短路径、最小生成树等）
    • 滑动窗口、双指针算法

  4. 保持编程规范：

    • 注重代码的可读性和注释的清晰度。
    • 熟练使用常见编程语言，如C++、Java、Python等。

如何获取资源？

  1. 官方参考：

    • 华为招聘官网或相关的招聘平台会有一些参考信息。
    • 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。

  2. 加入刷题社区：

    • 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
    • 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。

  3. 寻找系统性的教程：

    • 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
    • 完成系统的学习课程，例如数据结构与算法的在线课程。

积极心态与持续努力：

刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。

考试注意细节

  1. 本地编写代码

    • 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。

  2. 调整心态，保持冷静

    • 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。

  3. 输入输出完整性

    • 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。

  4. 快捷键使用

    • 删除行可用 Ctrl+D，复制、粘贴和撤销分别为 Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。
    • 避免使用 Ctrl+S，以免触发浏览器的保存功能。

  5. 浏览器要求

    • 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。

  6. 交卷相关

    • 答题前，务必仔细查看题目示例，避免遗漏要求。
    • 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
    • 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。

  7. 时间和分数安排

    • 总时间：150 分钟；总分：400 分。
    • 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。

  8. 考试环境准备

    • 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
    • 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。

  9. 技术问题处理

    • 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
    • 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。

祝你考试顺利，取得理想成绩！


http://www.kler.cn/a/507467.html

相关文章：

  • 微软开源AI Agent AutoGen 详解
  • 【Excel】【VBA】双列排序：坐标从Y从大到小排列之后相同Y坐标的行再对X从小到大排列
  • C++通透讲解设计模式：依赖倒转（1）
  • 我的年度总结
  • WEB 攻防-通用漏-XSS 跨站脚本攻击-反射型/存储型/DOMBEEF-XSS
  • Docker--Docker Compose(容器编排）
  • PE文件：节表-添加节
  • 记一次数据库连接 bug
  • RabbitMQ介绍以及基本使用
  • Python从0到100（八十四）：神经网络-卷积神经网络训练CIFAR-10数据集
  • 反转字符串中的单词 II：Swift 实现与详解
  • Qt之登录界面（splash）
  • PCL 计算点云的均值与标准差【2025最新版】
  • ASP.Net Identity + IODC 解析ReturnUrl
  • 【无线感知会议系列-21 】无线感知6G 研究愿景
  • 电气工程中的计算智能
  • Springboot（五十八）SpringBoot3使用Redisson实现接口的限流功能
  • .Net Core微服务入门全纪录（二）——Consul-服务注册与发现（上）
  • Spring boot学习文档
  • Linux 内核自旋锁spinlock（一）
  • 基于单片机的智能火灾报警系统设计
  • 远程桌面使用是TCP还是UDP？
  • LLM - 大模型 ScallingLaws 的迁移学习与混合训练(PLM) 教程(3)
  • Mysql常见问题处理集锦
  • PTA L1-039 古风排版
  • Bootstrap 下拉菜单