9.2华为OD机试真题 新系统 - 查找幸运数 (Java/Py/C/C++/Js/Go)

查找幸运数

2026 华为OD机试真题9月2日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

请在一个仅由数字组成的字符串中，找出只由 6 或 8 组成的最长的连续子串。

输入描述

输入一个仅由数字组成的字符串，字符串长度小于 256。

输出描述

请输出所有满足要求的最长子串，去重后按照字典序排序输出；当字符串为空或没有符合要求的子串时，输出空字符串。

示例1

输入

1688

输出

["688"]

说明

有 1 个子串 "688"。

示例2

输入

123

输出

[""]

说明

无符合要求子串。

示例3

输入

88612668

输出

["668","886"]

说明

有 "886"、"668" 两个最长的幸运子串，排序后输出。

解题思路

核心思想

幸运子串要求连续且每个字符都只能是 6 或 8。因此只需要线性扫描原字符串，把所有由 6/8 构成的极大连续段找出来，再筛选出长度最长的段，去重后按字典序升序输出。

如果没有任何合法连续段，或者输入为空，则输出只包含空字符串的数组 [""]。

算法步骤

1. 从左到右扫描字符串。
2. 遇到 6 或 8 时，继续向右扩展，截取这一段只含 6/8 的连续子串。
3. 记录当前最长长度，并维护所有长度等于最长长度的子串集合。
4. 扫描结束后，如果集合为空，输出 [""]。
5. 否则将集合中的字符串按字典序排序后输出。

复杂度分析

设字符串长度为 N。

• 时间复杂度：O(N + K log K)，其中 K 为最长幸运子串的去重数量。
• 空间复杂度：O(K)，用于保存最长候选集合。

Java

import 

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/banxia_frontend/article/details/164322347