三亩地 三亩地SAN MU DI · CODE DIARY
交流投稿
ARTICLE DETAIL

日记详情

真实记录编程学习的某一天，欢迎挑你感兴趣的翻一翻。

首页/学习日记/日记详情

华为OD机考双机位C卷：寻找密码算法与Java实现

发布时间：2026/8/15 13:43:25 三亩地 编程学习日记
华为OD机考双机位C卷：寻找密码算法与Java实现

1. 华为OD机考双机位C卷解析：寻找密码（Java实现）

作为参加过多次华为OD机考的过来人，我深知双机位监考模式下的C卷编程题往往考察算法思维和编码规范的平衡。这次遇到的"寻找密码"题目看似简单，实则暗藏多个考察点。下面我将从题目解析、解题思路到完整Java实现，分享我的实战经验和避坑指南。

1.1 题目核心需求还原

根据机考回忆，题目大致描述为：给定一个由数字字符组成的字符串s和一个整数k，需要找到所有长度为k的子串中，第一个出现且出现次数最多的那个子串。如果存在多个满足条件的子串，返回字典序最小的那个。

示例输入：

s = "123456123" k = 3

示例输出：

"123"

解释：所有长度为3的子串为["123","234","345","456","561","612","123"]，其中"123"出现两次且是最先重复的子串。

1.2 双机位环境下的解题策略

在双机位监控环境下（前置摄像头+屏幕共享），解题时需要特别注意：

  1. 禁止切换IDE界面（建议提前熟悉Eclipse或考官指定的IDE）
  2. 代码规范比平时更重要（类名、方法名必须符合题目要求）
  3. 变量命名要有意义（避免使用temp1、a等模糊命名）
  4. 注释要适度（关键算法步骤需要简单说明）

注意：实际考试时题目描述区域会锁定，无法复制文本，建议先在草稿纸上理清题意再编码。

2. 算法设计与实现详解

2.1 暴力解法与优化思路

最直观的解法是遍历所有长度为k的子串，用HashMap统计出现次数：

public static String findPassword(String s, int k) { Map<String, Integer> map = new HashMap<>(); String result = null; int maxCount = 0; for (int i = 0; i <= s.length() - k; i++) { String sub = s.substring(i, i + k); int count = map.getOrDefault(sub, 0) + 1; map.put(sub, count); if (count > maxCount || (count == maxCount && sub.compareTo(result) < 0)) { maxCount = count; result = sub; } } return result; }

时间复杂度：O(n*k)，其中n是字符串长度。当k较大时（如k≈n/2），会退化为O(n²)。

2.2 滑动窗口优化

观察到子串是连续的，可以采用滑动窗口减少字符串操作：

public static String findPasswordOpt(String s, int k) { Map<String, Integer> map = new HashMap<>(); String result = null; int maxCount = 0; String window = s.substring(0, k); map.put(window, 1); maxCount = 1; result = window; for (int i = 1; i <= s.length() - k; i++) { window = window.substring(1) + s.charAt(i + k - 1); int count = map.getOrDefault(window, 0) + 1; map.put(window, count); if (count > maxCount || (count == maxCount && window.compareTo(result) < 0)) { maxCount = count; result = window; } } return result; }

优化后时间复杂度：O(n)，空间复杂度：O(n)（最坏情况下需要存储所有子串）

2.3 字典序处理技巧

当多个子串出现次数相同时，需要返回字典序最小的。这里有个易错点：

错误做法：

if (count > maxCount) { maxCount = count; result = sub; } else if (count == maxCount) { result = sub.compareTo(result) < 0 ? sub : result; // 可能漏掉首次出现的条件 }

正确做法应同时考虑首次出现和字典序：

if (count > maxCount || (count == maxCount && (result == null || sub.compareTo(result) < 0))) { maxCount = count; result = sub; }

3. 边界条件与测试用例设计

3.1 必须考虑的边界情况

  1. k > s.length()：应返回空字符串或抛出异常（根据题目要求）
  2. k == 0：同上处理
  3. 所有子串唯一：返回第一个子串
  4. 存在多个最大频率子串：取字典序最小
  5. 包含非数字字符：题目明确说数字字符可忽略此情况

3.2 测试用例示例

public static void main(String[] args) { System.out.println(findPassword("123456123", 3)); // "123" System.out.println(findPassword("111222111", 3)); // "111" System.out.println(findPassword("123456789", 3)); // "123" System.out.println(findPassword("121212", 2)); // "12" System.out.println(findPassword("1", 1)); // "1" System.out.println(findPassword("123", 4)); // "" }

4. 华为OD机考实战经验

4.1 双机位环境注意事项

  1. 提前测试IDE：

    • 确认代码自动补全功能是否可用
    • 练习在无代码提示情况下编写标准库方法
    • 熟悉调试快捷键（如Step Over, Resume等）

  2. 输入输出处理：

    • 题目通常要求从System.in读取输入
    • 输出必须严格匹配要求（包括大小写、空格等）

  3. 时间分配建议：

    • 5分钟阅读题目
    • 10分钟设计测试用例
    • 30分钟编码实现
    • 5分钟边界测试

4.2 代码规范得分点

华为OD评分标准中代码规范占20%权重，重点关注：

  1. 类名必须为Main（部分考场要求）
  2. 方法签名与题目要求完全一致
  3. 适当的空行分隔代码块
  4. 避免魔法数字（如直接使用3，应定义常量SUB_LEN=3）
  5. 异常处理（如对非法参数抛出IllegalArgumentException）

4.3 性能优化技巧

当遇到超长字符串时（如长度10^6级）：

  1. 避免使用substring频繁创建新字符串
  2. 考虑用字符数组+System.arraycopy
  3. 可以尝试Rolling Hash进一步优化
  4. 如果允许，用int代替字符串作为key（适用于固定k值）

5. 类似题目拓展练习

为准备华为OD机考，建议练习以下同类型题目：

  1. 最长不重复子串
  2. 最小覆盖子串
  3. 所有字母异位词
  4. 重复的DNA序列
  5. 滑动窗口最大值

以"重复的DNA序列"为例，对比解法：

public List<String> findRepeatedDnaSequences(String s) { Map<String, Integer> map = new HashMap<>(); List<String> result = new ArrayList<>(); for (int i = 0; i <= s.length() - 10; i++) { String sub = s.substring(i, i + 10); int count = map.getOrDefault(sub, 0) + 1; map.put(sub, count); if (count == 2) { // 只记录首次重复 result.add(sub); } } return result; }

6. Java实现中的常见陷阱

6.1 字符串拼接性能

在滑动窗口实现中，这样的写法会导致性能问题：

window = window.substring(1) + s.charAt(i + k - 1); // 创建临时字符串

更高效的实现：

char[] window = s.substring(0, k).toCharArray(); // 滑动时维护字符数组 System.arraycopy(window, 1, window, 0, k-1); window[k-1] = s.charAt(i + k - 1); String key = new String(window);

6.2 HashMap的负载因子

当处理超长字符串时，可以预先设置HashMap容量：

Map<String, Integer> map = new HashMap<>(s.length() - k + 1);

避免resize带来的性能损耗。

6.3 内存溢出处理

极端情况下可能出现OutOfMemoryError，可以：

  1. 使用更紧凑的数据结构
  2. 分批处理字符串
  3. 与考官沟通处理方案

7. 华为OD评分标准解析

根据参加过终面的同学反馈，这类题目的评分维度包括：

  1. 功能正确性（50%）：通过所有测试用例
  2. 代码规范（20%）：命名、注释、结构
  3. 性能优化（20%）：时间/空间复杂度
  4. 边界处理（10%）：异常输入处理

特别要注意的是，华为OD考试会运行隐藏的极端测试用例（如k=0, s=null等），必须做好防御性编程。

编程学习 学习日记 实战经验
← 返回列表